Submission #876591

#	Time	Username	Problem	Language	Result	Execution time	Memory
876591		CYhuang	Meteors (POI11_met)	C++17	0 / 100	370 ms	29180 KiB

met

#include<bits/stdc++.h>
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long

#define For(i,a,b) for(int i=a;i<=b;i++)
#define Rof(i,a,b) for(int i=a;i>=b;i--)

typedef pair<int,int> pii;
#define F first
#define S second

typedef vector<int> vi;
#define pb push_back
#define ft front()
#define bk back()
#define tp top()
#define lb lower_bound
#define ub upper_bound
#define sz(a) (int)a.size()
#define ms(a,x) memset(a,x,sizeof(a))
const int Size=3e5;
int m;
int p[Size+20],ans[Size+20],bit[Size+20];
vi own[Size+20];
struct Query{
    int l,r,val;
}qq[Size+20];
int lowbit(int x){
    return x&(-x);
}
void modify(int x,int val){
    while(x<=Size){
        bit[x]+=val;
        x+=lowbit(x);
    }
}
int query(int x){
    int tot=0;
    while(x){
        tot+=bit[x];
        x-=lowbit(x);
    }
    return tot;
}
void range_modify(int l,int r,int val){
    if(l<r) modify(l,val),modify(r+1,-val);
    else{
        modify(l,val),modify(m+1,-val);
        modify(1,val),modify(r+1,-val);
    }
}
void check(vi &qry,vi &ok,vi &fail){
    for(auto i:qry){
        int tot=0;
        for(auto j:own[i])  tot+=query(j);
        if(p[i]<=tot)   ok.pb(i);
        else{
            p[i]-=tot;
            fail.pb(i);
        }
    }
    vi().swap(qry);
}
void total_bs(vi &qry,int ll,int rr){
    if(!sz(qry))    return ;
    if(ll==rr){
        for(auto i:qry) ans[i]=ll;
        return ;
    }
    int mm=ll+((rr-ll)>>1);
    For(i,ll,mm)    range_modify(qq[i].l,qq[i].r,qq[i].val);
    vi ok,fail;
    check(qry,ok,fail);
    For(i,ll,mm)    range_modify(qq[i].l,qq[i].r,-qq[i].val);
    total_bs(ok,ll,mm);
    total_bs(fail,mm+1,rr);
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n>>m;
    vi vec;
    For(i,1,m){
        int o;
        cin>>o;
        own[o].pb(i);
    }
    For(i,1,n){
        cin>>p[i];
        vec.pb(i);
    }
    int k;
    cin>>k;
    For(i,1,k)  cin>>qq[i].l>>qq[i].r>>qq[i].val;
    total_bs(vec,1,k+1);
    For(i,1,n){
        if(ans[i]<=k)  cout<<ans[i]<<"\n";
        else    cout<<"NIE\n";
    }
    return 0;
}
/*
check:
1.read problem statement correctly
2.int overflow
3.array out of bound
4.special case(0 or 1)
5.time complexity
6.try to change dimension in array!!!
*/

• 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