Submission #738554

#	Time	Username	Problem	Language	Result	Execution time	Memory
738554		boyliguanhan	Meteors (POI11_met)	C++17	0 / 100	575 ms	65536 KiB

met

#include<bits/stdc++.h>
#define N 300100
#define rep(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
#define int long long
int bit[N],ans[N],L[N],R[N],a[N];
struct c{int g, id;vector<int>st;};
void u(int x, int y) {
    for(;x<N;x+=x&-x)
        bit[x]+=y;
}
void upd(int l, int r, int x) {
    u(l,x),u(r+1,-x);
    if(l>r)u(1,x);
}
int q(int x) {
    int r = 0;
    while(x)r+=bit[x],x-=x&-x;
    return r;
}
void solve(int l, int r, vector<c> cs){
    if(l==r) {
        for(auto i: cs) ans[i.id] = l;
        l++;
    }
    if(cs.empty()||l>r) return;
    int m=l+r>>1;
    rep(i,l,m)
        upd(L[i],R[i],a[i]);
    vector<c>c1,c2;
    for(auto i: cs) {
        int x=0;
        for(auto j:i.st)x+=q(j);
        if(x<=i.g) 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);
}
signed main() {
    int n,m,k;
    cin>>n>>m;
    vector<c> v(n);
    rep(i,1,m){
        int x;
        cin>>x;
        v[x-1].st.push_back(i);
    }
    rep(i,0,n-1)cin>>v[i].g,v[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,k)
        if(ans[i]<=k)
            cout << ans[i] <<'\n';
        else
            cout << "NIE\n";
}

Compilation message (stderr)

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

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13