Submission #1209403

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209403		boss_zz	Meteors (POI11_met)	C++20	0 / 100	626 ms	28656 KiB

met

#include<bits/stdc++.h>
#define rep(a,b,c) for(ll a=b;a<=c;++a)
#define ll long long 
#define ff first 
#define ss second 
#define mp make_pair 
using namespace std;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll N=3e5+5,inf=1e18;
ll n,m,q,O[N],tar[N],L[N],R[N],A[N],ans[N],BIT[N];
vector<ll> T[N];
ll lowbit(ll x){return x&(-x);}
void modify(ll l,ll r,ll v){
    for(ll i=l;i<=m;i+=lowbit(i)) BIT[i]+=v;
    for(ll i=r+1;i<=m;i+=lowbit(i)) BIT[i]-=v;
}
ll query(ll pos){
    ll res=0;
    for(ll i=pos;i>=1;i-=lowbit(i)) res+=BIT[i];
    return res;
}
void Do(ll l,ll r){
    rep(i,l,r){
        if(L[i]<=R[i]) modify(L[i],R[i],A[i]);
        else{
            modify(1,R[i],A[i]);
            modify(L[i],m,A[i]);
        }
    }
}
void Undo(ll l,ll r){
    rep(i,l,r){
        if(L[i]<R[i]) modify(L[i],R[i],-A[i]);
        else{
            modify(1,R[i],-A[i]);
            modify(L[i],m,-A[i]);
        }
    }
}
void Split(vector<ll> &qry,vector<ll> &lft,vector<ll> &rgt){
    for(ll i:qry){
        ll cur=0;
        for(ll j:T[i]){
            cur+=query(j);
            if(cur>=tar[i]) break;
        }
        if(cur>=tar[i]) lft.push_back(i);
        else rgt.push_back(i);
    }
    vector<ll>().swap(qry);
}
void TBS(ll l,ll r,vector<ll> &qry){
    if(l==r){
        for(ll i:qry) ans[i]=l;
        return ;
    }
    ll mid=(l+r)>>1;
    Do(l,mid);
    vector<ll> lft,rgt;
    Split(qry,lft,rgt);
    TBS(mid+1,r,rgt);
    Undo(l,mid);
    TBS(l,mid,lft);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    rep(i,1,m) cin>>O[i],T[O[i]].push_back(i);
    rep(i,1,n) cin>>tar[i];
    cin>>q;
    rep(i,1,q) cin>>L[i]>>R[i]>>A[i];
    L[q+1]=R[q+1]=m;
    vector<ll> Q;
    rep(i,1,n) Q.push_back(i);
    TBS(1,q+1,Q);
    rep(i,1,n){
        if(ans[i]<=q) cout<<ans[i]<<'\n';
        else cout<<"NIE"<<'\n';
    }
    return 0;
}

• 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