oj.uz

Submission #752066

# Submission time Handle Problem Language Result Execution time Memory
752066 2023-06-02T09:01:34 Z safaricola Meteors (POI11_met) C++17
0 / 100
 1794 ms 29004 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define rep(i,n) for(int i=1; i<=n; i++)
int fw[300010],fw2[300010];
void update(int x, int y, int v) { 
    for (int tx=x; tx <= 300010; tx += tx&(-tx)) 
        fw[tx] += v, fw2[tx] -=v*(x-1);
    for (int ty=y+1; ty <= 300010; ty += ty&(-ty)) 
        fw[ty] -= v, fw2[ty] += v*y;
}
int sum (int x) {
  if(x==0)return 0;
    long long res = 0;
    for (int tx=x; tx; tx -= tx&(-tx)) res += fw[tx]*x + fw2[tx];
    return res; 
}
int range_sum(int x, int y) {
    return sum(y)-sum(x-1);
}
int p,need[300010],Q,s[300010],e[300010],n,m;
vector<int> sons[300010];
pair<ii,int> q[300010];
ii pos[300010];
signed main(){
    cin>>n>>m;
    rep(i,m){
        cin>>p;
        sons[p].pb(i);
    }
    rep(i,n)cin>>need[i];
    cin>>Q;
    rep(i,Q)cin>>q[i].f.f>>q[i].f.s>>q[i].s;
    rep(i,n){s[i]=-1,e[i]=Q+1;}
    rep(re,20){
        rep(i,n){
            pos[i].f=(s[i]+e[i])/2;
            pos[i].s=i;
        }
        sort(pos+1,pos+n+1);
        memset(fw,0,sizeof(fw));
        memset(fw2,0,sizeof(fw2));
        int ind=1;
        rep(i,n){
            if(s[pos[i].s]==e[pos[i].s])continue;
            while(ind<=min(pos[i].f,Q)){
                if(q[ind].f.f<=q[ind].f.s)update(q[ind].f.f,q[ind].f.s,q[ind].s);
                else{
                    update(1,q[ind].f.s,q[ind].s);
                    update(q[ind].f.f, m+1, q[ind].s);
                }
                ind++;
            }
            int cur=0;
            for(auto it: sons[pos[i].s]){
                cur+=range_sum(it,it);
            }
            //cout<<'>'<<pos[i].f<<' '<<pos[i].s<<' '<<cur<<endl;
            if(cur<=need[pos[i].s]){
                s[pos[i].s]=pos[i].f;
            }else{
                e[pos[i].s]=pos[i].f;
            }
        }
        //for(int i=1; i<=5; i++)cout<<range_sum(i,i)<<endl;
        //rep(i,n)cout<<i<<' '<<s[i]<<' '<<e[i]<<endl;
    }
    rep(i,n){
        if(e[i]==Q+1)cout<<"NIE\n";
        else cout<<e[i]<<'\n';
    }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 12116 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12116 KB Output is correct
2 Correct 13 ms 12116 KB Output is correct
3 Incorrect 13 ms 12044 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 13936 KB Output is correct
2 Incorrect 318 ms 15068 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 239 ms 14360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 14028 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 13732 KB Output is correct
2 Correct 281 ms 14288 KB Output is correct
3 Correct 172 ms 13912 KB Output is correct
4 Incorrect 290 ms 15284 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1794 ms 29004 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1784 ms 28044 KB Output isn't correct
2 Halted 0 ms 0 KB -