oj.uz

Submission #944095

# Submission time Handle Problem Language Result Execution time Memory
944095 2024-03-12T08:26:52 Z Warinchai Meteors (POI11_met) C++14
74 / 100
 3603 ms 65536 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
int own[300005];
vector<int>states[300005];
int least[300005];
struct segtree{
    int info[1200005];
    int lz[1200005];
    void push(int st,int en,int i){
        if(lz[i]!=0){
            if(st==en)info[i]+=lz[i];
            else {
                lz[i*2+1]+=lz[i];
                lz[i*2]+=lz[i];
            }
            lz[i]=0;
        }
    }
    void upd(int st,int en,int i,int l,int r,int val){
        push(st,en,i);
        if(st>r||en<l)return;
        if(st>=l&&en<=r)return lz[i]+=val,push(st,en,i),void();
        int m=(st+en)/2;
        upd(st,m,i*2,l,r,val);
        upd(m+1,en,i*2+1,l,r,val);
    }
    int fval(int st,int en,int i,int pos){
        push(st,en,i);
        if(st==en)return info[i];
        int m=(st+en)/2;
        if(pos<=m)return fval(st,m,i*2,pos);
        else return fval(m+1,en,i*2+1,pos);
    }
    void clear(int st,int en,int i){
        lz[i]=0;
        if(st==en)return info[i]=0,void();
        int m=(st+en)/2;
        clear(st,m,i*2);
        clear(m+1,en,i*2+1);
    }
}tr;
int st[300005];
int en[300005];
struct meteor{
    int l,r,a;
    meteor(int x,int y,int z){
        l=x,r=y,a=z;
    }
};
vector<meteor>events;
vector<int>query[300005];
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>own[i];
        states[own[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        cin>>least[i];
    }
    int k;cin>>k;
    for(int i=1;i<=k;i++){
        int a,b,c;cin>>a>>b>>c;
        events.push_back(meteor(a,b,c));
    }
    for(int i=1;i<=n;i++){
        st[i]=1;en[i]=k+1;
        int m=(st[i]+en[i])/2;
        query[m].push_back(i);
    }
    //cout<<"work\n";
    while(1){
        int cur=0;
        for(auto x:events){
            cur++;
            //cout<<"EVENT:"<<cur<<"\n";
            int l=x.l;
            int r=x.r;
            if(l<=r)tr.upd(1,m,1,l,r,x.a);
            else tr.upd(1,m,1,l,m,x.a),tr.upd(1,m,1,1,r,x.a);
            for(auto y:query[cur]){
                //cerr<<"STATE:"<<y<<"\n";
                int sum=0;
                for(auto z:states[y]){
                    //cerr<<"STATION:"<<z<<" "<<tr.fval(1,m,1,z)<<"\n";
                    sum+=tr.fval(1,m,1,z);
                }
                if(sum>=least[y]){
                    //cerr<<"ENOUGH\n";
                    en[y]=cur;
                }else{
                    //cerr<<"NOT ENOUGH\n";
                    st[y]=cur+1;
                }
            }
            query[cur].clear();
        }
        tr.clear(1,m,1);
        int check=1;
        for(int i=1;i<=n;i++){
            if(st[i]!=en[i]){
                check=0;
                int m=(st[i]+en[i])/2;
                query[m].push_back(i);
            }
        }
        if(check)break;
    }
    for(int i=1;i<=n;i++){
        int x=st[i];
        if(x==k+1)cout<<"NIE\n";
        else cout<<x<<"\n";
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25176 KB Output is correct
2 Correct 8 ms 25180 KB Output is correct
3 Correct 9 ms 25180 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 8 ms 25180 KB Output is correct
3 Correct 8 ms 25436 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 333 ms 31708 KB Output is correct
2 Correct 408 ms 35088 KB Output is correct
3 Correct 403 ms 33872 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 33296 KB Output is correct
2 Correct 387 ms 33224 KB Output is correct
3 Correct 438 ms 35108 KB Output is correct
4 Correct 78 ms 31252 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 31948 KB Output is correct
2 Correct 211 ms 35268 KB Output is correct
3 Correct 166 ms 27156 KB Output is correct
4 Correct 396 ms 34388 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 31052 KB Output is correct
2 Correct 321 ms 33104 KB Output is correct
3 Correct 340 ms 31536 KB Output is correct
4 Correct 397 ms 36544 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3097 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 3603 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -