oj.uz

Submission #876593

# Submission time Handle Problem Language Result Execution time Memory
876593 2023-11-22T03:53:08 Z CYhuang Meteors (POI11_met) C++17
74 / 100
 328 ms 29256 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])  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
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 12780 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15708 KB Output is correct
2 Correct 90 ms 18572 KB Output is correct
3 Correct 74 ms 15960 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 15956 KB Output is correct
2 Correct 107 ms 16988 KB Output is correct
3 Correct 58 ms 19564 KB Output is correct
4 Correct 20 ms 14428 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 15704 KB Output is correct
2 Correct 127 ms 19480 KB Output is correct
3 Correct 41 ms 15448 KB Output is correct
4 Correct 80 ms 17144 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 15316 KB Output is correct
2 Correct 117 ms 15832 KB Output is correct
3 Correct 49 ms 15632 KB Output is correct
4 Correct 126 ms 19592 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 29208 KB Output is correct
2 Incorrect 246 ms 29256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 324 ms 28668 KB Output is correct
2 Incorrect 262 ms 27848 KB Output isn't correct
3 Halted 0 ms 0 KB -