QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#652852#6135. Booksucup-team5217#WA 77ms13052kbC++232.0kb2024-10-18 19:13:212024-10-18 19:13:21

Judging History

This is the latest submission verdict.

  • [2024-10-18 19:13:21]
  • Judged
  • Verdict: WA
  • Time: 77ms
  • Memory: 13052kb
  • [2024-10-18 19:13:21]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
struct seg{
    pair<ll,ll> minn[400010];
    ll tag[400010];
    void pushup(int p){
        minn[p]=min(minn[p<<1],minn[p<<1|1]);
    }
    int n;
    void intt(vector<int> ve){
        n=(int)ve.size()-1;
        build(1,1,n,ve);
    }
    void spread(int p){
        minn[p<<1].first-=tag[p];
        minn[p<<1|1].first-=tag[p];
        tag[p<<1]+=tag[p],tag[p<<1|1]+=tag[p];
        tag[p]=0;
    }
    void build(int p,int l,int r,vector<int>& ve){
        tag[p]=0;minn[p]={0,0};
        if(l==r)    {minn[p]={ve[l],l};return ;}
        int mid=(l+r)>>1;
        build(p<<1,l,mid,ve);
        build(p<<1|1,mid+1,r,ve);
        pushup(p);
    }
    ll query(){
        return minn[1].second;
    }
    void modify(int p,int l,int r,int L,int R,ll nz){
        if(L<=l&&r<=R){
            tag[p]+=nz;
            minn[p].first-=nz;
            return ;
        }
        spread(p);
        int mid=(l+r)>>1;
        if(mid>=L)  modify(p<<1,l,mid,L,R,nz);
        if(mid<R)   modify(p<<1|1,mid+1,r,L,R,nz);
        pushup(p);
    }
    void modify(int l,int r,int nz){
        modify(1,1,n,l,r,nz);
    }
};
seg sg;
void solve(void) {
    int n,m;
    cin>>n>>m;
    vector<int> a(1);
    for(int i=1;i<=n;i++)   {
        int nz;
        cin>>nz;
        if(nz==0) m--;  
        else a.push_back(nz);
    }
    if(m<0) {cout<<"Impossible\n";return ;}
    int sz=(int)a.size()-1;
    if(m==sz)   {cout<<"Richman\n";return ;}
    sg.intt(a);
    ll ans=0;
    const ll mx=1e16;
    for(int i=1;i<=m+1;i++){
        int w=sg.query();
        ans+=a[w];
        sg.modify(w,w,-mx);
        if(w!=1)    sg.modify(1,w-1,a[w]);
    }
    cout<<ans-1<<'\n';

}

signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int _ = 1;
    cin >> _;
    while (_--) solve();
    return 0;
}
/*
4
4 2
1 2 4 8
4 0
100 99 98 97
2 2
10000 10000
5 3
0 0 0 0 0
*/
/*
1
5 5
0 0 0 0 0
*/

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9752kb

input:

4
4 2
1 2 4 8
4 0
100 99 98 97
2 2
10000 10000
5 3
0 0 0 0 1

output:

6
96
Richman
Impossible

result:

ok 4 lines

Test #2:

score: -100
Wrong Answer
time: 77ms
memory: 13052kb

input:

10012
1 0
2
3 2
0 1 0
2 1
0 0
100000 99999
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000...

output:

1
0
Impossible
99999999999999
38
56
Richman
97
438
Richman
24
50
98
30
15
Richman
Richman
Richman
36
Richman
Richman
450
24
44
349
34
513
28
33
238
Richman
Richman
Richman
56
274
2
160
76
47
91
71
3
Richman
125
32
15
Richman
21
26
Richman
7
Richman
206
282
Richman
Richman
60
312
62
257
Richman
67
Ri...

result:

wrong answer 5th lines differ - expected: '192', found: '38'