oj.uz

Submission #752061

# Submission time Handle Problem Language Result Execution time Memory
752061 2023-06-02T08:48:19 Z safaricola Meteors (POI11_met) C++17
74 / 100
 1847 ms 29504 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);
        fw[0]=0;fw2[0]=0;
        rep(i,300008)fw[i]=0;
        rep(i,300008)fw2[i]=0;
        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, 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
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 12116 KB Output is correct
2 Correct 17 ms 12112 KB Output is correct
3 Correct 15 ms 12096 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12108 KB Output is correct
2 Correct 14 ms 12116 KB Output is correct
3 Correct 15 ms 12116 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 14476 KB Output is correct
2 Correct 331 ms 15548 KB Output is correct
3 Correct 248 ms 15000 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 14724 KB Output is correct
2 Correct 242 ms 14784 KB Output is correct
3 Correct 349 ms 15588 KB Output is correct
4 Correct 88 ms 14020 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 14544 KB Output is correct
2 Correct 302 ms 15588 KB Output is correct
3 Correct 119 ms 13728 KB Output is correct
4 Correct 232 ms 15136 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 14224 KB Output is correct
2 Correct 273 ms 14728 KB Output is correct
3 Correct 159 ms 14356 KB Output is correct
4 Correct 288 ms 15744 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1847 ms 29504 KB Output is correct
2 Incorrect 1070 ms 22104 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1759 ms 28584 KB Output is correct
2 Incorrect 976 ms 22076 KB Output isn't correct
3 Halted 0 ms 0 KB -