oj.uz

Submission #876594

# Submission time Handle Problem Language Result Execution time Memory
876594 2023-11-22T03:54:16 Z CYhuang Meteors (POI11_met) C++17
100 / 100
 1211 ms 41836 KB 
#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])  if((tot+=query(j))>=p[i])   break;
        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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12636 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 3 ms 12636 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12632 KB Output is correct
2 Correct 3 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 15708 KB Output is correct
2 Correct 93 ms 18504 KB Output is correct
3 Correct 73 ms 16072 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 16220 KB Output is correct
2 Correct 97 ms 15964 KB Output is correct
3 Correct 53 ms 18388 KB Output is correct
4 Correct 18 ms 13916 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 15708 KB Output is correct
2 Correct 122 ms 18348 KB Output is correct
3 Correct 43 ms 14936 KB Output is correct
4 Correct 78 ms 16096 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 15512 KB Output is correct
2 Correct 101 ms 16036 KB Output is correct
3 Correct 45 ms 15452 KB Output is correct
4 Correct 131 ms 18324 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 325 ms 29204 KB Output is correct
2 Correct 144 ms 21592 KB Output is correct
3 Correct 254 ms 21468 KB Output is correct
4 Correct 1103 ms 40252 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 302 ms 28604 KB Output is correct
2 Correct 215 ms 21588 KB Output is correct
3 Correct 86 ms 22732 KB Output is correct
4 Correct 1211 ms 41836 KB Output is correct