Submission #854599

#	Time	Username	Problem	Language	Result	Execution time	Memory
854599		dreamoon	Meteors (POI11_met)	C++17	100 / 100	1318 ms	41300 KiB

met

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
using LL = long long;
const int MAX_V = 300001;
int p[MAX_V];
int l[MAX_V], r[MAX_V], a[MAX_V];
vector<int> pos[MAX_V];
LL bit[MAX_V];
void bit_clear() {
    memset(bit, 0, sizeof(bit));
}
void bit_ins(int x, int v) {
    for(; x < MAX_V; x += x & -x) {
        bit[x] += v;
    }
}
LL bit_query(int x) {
    LL res = 0;
    for(; x; x -= x & -x) {
        res += bit[x];
    }
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int o;
        cin >> o;
        pos[o].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    int k;
    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> l[i] >> r[i] >> a[i];
    }
    queue<tuple<int, int, vector<int>>> queries;
    {
        vector<int> ids;
        for(int i = 1; i <= n; i++) {
            ids.push_back(i);
        }
        queries.push({1, k + 1, ids});
    }
    int ptr = 0;
    vector<int> ans(n + 1);
    while(!queries.empty()) {
        auto [low, hi, ids] = queries.front();
        queries.pop();
        if(low == hi) {
            for(int id: ids) {
                ans[id] = low;
            }
            continue;
        }
        int mid = low + (hi - low) / 2;
        if(mid < ptr) {
            bit_clear();
            ptr = 0;
        }
        while(ptr < mid) {
            ptr++;
            bit_ins(l[ptr], a[ptr]);
            bit_ins(r[ptr] + 1, -a[ptr]);
            if(r[ptr] < l[ptr]) {
                bit_ins(1, a[ptr]);
            }
        }
        vector<int> small_id, big_id;
        for(int id: ids) {
            long long need = p[id];
            for(int p: pos[id]) {
                need -= bit_query(p);
                if(need <= 0) break;
            }
            if(need <= 0) {
                small_id.push_back(id);
            } else {
                big_id.push_back(id);
            }
        }
        if(!small_id.empty()) {
            queries.push({low, mid, small_id});
        }
        if(!big_id.empty()) {
            queries.push({mid + 1, hi, big_id});
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ans[i] > k) {
            cout << "NIE\n";
        }
        else {
            cout << ans[i] << "\n";
        }
    }
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
}

• 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: 13 / 13
• Subtask 8: 13 / 13