oj.uz

Submission #738602

# Submission time Handle Problem Language Result Execution time Memory
738602 2023-05-09T07:29:25 Z boyliguanhan Meteors (POI11_met) C++17
100 / 100
 1247 ms 46568 KB 
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define N 300100
#define V vector
#define rep(i,j,k) for(I i=j;i<=k;i++)
using namespace std;
#define I long long
I bit[N],ans[N],L[N],R[N],a[N];
struct c{I g, id;V<I>st;};
void u(I x, I y) {
    for(;x<N;x+=x&-x)
        bit[x]+=y;
}
void upd(I l, I r, I x) {
    u(l,x),u(r+1,-x);
    if(l>r)u(1,x);
}
I q(I x) {
    I r = 0;
    while(x)r+=bit[x],x-=x&-x;
    return r;
}
c X[N];
void solve(I l, I r, V<int> cs){
    if(l==r) {
        for(auto i: cs) ans[X[i].id] = l;
        l++;
    }
    if(cs.empty()||l>r) return;
    I m=l+r>>1;
    rep(i,l,m)
        upd(L[i],R[i],a[i]);
    V<int>c1,c2;
    for(auto i: cs) {
        I x=0;
        for(auto j:X[i].st)x=min((I)1e10,x+q(j));
        if(x<X[i].g) X[i].g-=x,c2.push_back(i);
        else c1.push_back(i);
    }
    cs.clear();
    rep(i,l,m) upd(L[i],R[i],-a[i]);
    solve(l,m,c1);
    solve(m+1,r,c2);
}
int main() {
    cin.sync_with_stdio(false);cin.tie(nullptr);
    I n,m,k;
    cin>>n>>m;
    V<int> v(n);
    iota(v.begin(),v.end(),0);
    rep(i,1,m){
        I x;
        cin>>x;
        X[x-1].st.push_back(i);
    }
    rep(i,0,n-1)cin>>X[i].g,X[i].id=i+1;
    cin>>k;
    rep(i,1,k)cin>>L[i]>>R[i]>>a[i];
    L[k+1]=1,R[k+1]=m,a[k+1]=1e18;
    solve(1,k+1,v);
    rep(i,1,n)
        if(ans[i]<=k) cout << ans[i] <<'\n';
        else cout << "NIE\n";
}

Compilation message

met.cpp: In function 'void solve(long long int, long long int, std::vector<int>)':
met.cpp:30:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |     I m=l+r>>1;
      |         ~^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12116 KB Output is correct
2 Correct 7 ms 12116 KB Output is correct
3 Correct 8 ms 12116 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 12116 KB Output is correct
2 Correct 6 ms 12136 KB Output is correct
3 Correct 8 ms 12244 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 14996 KB Output is correct
2 Correct 86 ms 17888 KB Output is correct
3 Correct 90 ms 14964 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 14780 KB Output is correct
2 Correct 107 ms 14688 KB Output is correct
3 Correct 71 ms 16724 KB Output is correct
4 Correct 29 ms 14544 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 14820 KB Output is correct
2 Correct 150 ms 16916 KB Output is correct
3 Correct 51 ms 13256 KB Output is correct
4 Correct 89 ms 15128 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 14212 KB Output is correct
2 Correct 125 ms 14792 KB Output is correct
3 Correct 58 ms 14372 KB Output is correct
4 Correct 121 ms 15944 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 37904 KB Output is correct
2 Correct 222 ms 22828 KB Output is correct
3 Correct 252 ms 20364 KB Output is correct
4 Correct 1035 ms 42092 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 34316 KB Output is correct
2 Correct 253 ms 23388 KB Output is correct
3 Correct 92 ms 20252 KB Output is correct
4 Correct 1247 ms 46568 KB Output is correct