Submission #850081

#	Time	Username	Problem	Language	Result	Execution time	Memory
850081		nnin	Meteors (POI11_met)	C++14	0 / 100	27 ms	65536 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;
    ll a;
};

struct C{
    int l, r;
};

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

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

queue<int> mid[300003];

int32_t 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(i);
    }
    int fin = 0;
    while(fin<n) {
        for(int i=0;i<=m;i++) fenwick[i] = 0;
        for(int i=1;i<=q;i++) {
            update(predict[i].l, predict[i].a);
            update(predict[i].r+1, -predict[i].a);
            if(predict[i].l>predict[i].r)
                update(1, predict[i].a);
            while(!mid[i].empty()) {
                int state = mid[i].front();
                mid[i].pop();
                ll ct = 0;
                for(int station:own[state]) {
                    ct += query(station);
                }
                if(ct>=p[state]) {
                    cur[state].r = i;
                } else {
                    cur[state].l = i+1;
                }
                if(cur[state].l==cur[state].r) {
                    fin++;
                } else {
                    int md = (cur[state].l+cur[state].r)/2;
                    mid[md].push(state);
                }
            }
        }
    }
    for(int i=1;i<=n;i++) {
        if(cur[i].l==q+1) cout<<"NIE\n";
        else cout<<cur[i].l<<'\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