Submission #849969

#	Time	Username	Problem	Language	Result	Execution time	Memory
849969		nnin	Meteors (POI11_met)	C++14	24 / 100	6094 ms	42904 KiB

met

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
using namespace std;

struct P {
    int l, r, a;
};

struct C{
    int l, r;
};

int n, m, p[300003], q;
P predict[300003];
vector<int> own[300003];
C cur[300003];

int fenwick[600003];
void update(int idx, int val) {
    if(idx==0) return;
    while(idx<=2*m) {
        fenwick[idx] += val;
        idx += (idx & -idx);
    }
}
int query(int idx) {
    int ret = 0;
    while(idx>0) {
        ret += fenwick[idx];
        idx -= (idx & -idx);
    }
    return ret;
}

void makefenwick(int time) {
    for(int i=0;i<=m;i++) fenwick[i] = 0;
    for(int i=1;i<=time;i++) {
        update(predict[i].l, predict[i].a);
        update(predict[i].r+1, -predict[i].a);
        if(predict[i].r<predict[i].l) {
            update(1, predict[i].a);
        }
    }

}

vector<int> mid[300003];
queue<int> qu;
bool inq[300003];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int o;
        cin>>o;
        own[o].push_back(i);
    }
    for(int i=1;i<=n;i++) {
        cin>>p[i];
    }
    cin>>q;
    for(int i=1;i<=q;i++) {
        cin>>predict[i].l>>predict[i].r>>predict[i].a;
    }
    for(int i=1;i<=n;i++) {
        cur[i] = {1, q+1};
        mid[(2+q)/2].push_back(i);
        if(!inq[(2+q)/2]) {
            qu.push((2+q)/2);
            inq[(2+q)/2] = 1;
        }
    }
    while(!qu.empty()) {
        int md = qu.front();
        qu.pop();
        inq[md] = 0;
        makefenwick(md);
        for(int state:mid[md]) {
            int ct = 0;
            for(int station:own[state]) {
                ct += query(station);
            }
            if(ct<p[state]) {
                cur[state].l = md+1;
            } else {
                cur[state].r = md;
            }
            if(cur[state].l<cur[state].r) {
                mid[(cur[state].l+cur[state].r)/2].push_back(state);
                if(!inq[(cur[state].l+cur[state].r)/2]) {
                    qu.push((cur[state].l+cur[state].r)/2);
                    inq[(cur[state].l+cur[state].r)/2] = 1;
                }
            }
        }
        mid[md].clear();
    }
    for(int i=1;i<=n;i++) {
        if(cur[i].l==q+1) cout<<"NIE\n";
        else cout<<cur[i].l<<'\n';
    }
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 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