제출 #752066

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
752066		safaricola	Meteors (POI11_met)	C++17	0 / 100	1794 ms	29004 KiB

met

#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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13