제출 #850082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
850082		nnin	새로운 문제 (POI11_met)	C++14	74 / 100	640 ms	39780 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;
}

vector<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_back(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);
            for(int state:mid[i]) {
                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_back(state);
                }
            }
            mid[i].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: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13