oj.uz

Submission #752060

# Submission time Handle Problem Language Result Execution time Memory
752060 2023-06-02T08:43:33 Z safaricola Meteors (POI11_met) C++17
74 / 100
 1808 ms 36808 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);
        rep(i,300005)fw[i]=0;
        rep(i,300005)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 12 ms 12116 KB Output is correct
2 Correct 12 ms 12164 KB Output is correct
3 Correct 13 ms 12116 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 14808 KB Output is correct
2 Correct 293 ms 16404 KB Output is correct
3 Correct 200 ms 15564 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 15368 KB Output is correct
2 Correct 236 ms 15400 KB Output is correct
3 Correct 318 ms 16448 KB Output is correct
4 Correct 85 ms 13972 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 14916 KB Output is correct
2 Correct 288 ms 16172 KB Output is correct
3 Correct 107 ms 13944 KB Output is correct
4 Correct 200 ms 15816 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 14744 KB Output is correct
2 Correct 276 ms 15608 KB Output is correct
3 Correct 157 ms 14844 KB Output is correct
4 Correct 284 ms 16484 KB Output is correct

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1808 ms 35744 KB Output is correct
2 Incorrect 946 ms 28092 KB Output isn't correct
3 Halted 0 ms 0 KB -