Submission #1281537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281537		nanj0178	Meteors (POI11_met)	C++20	74 / 100	619 ms	16112 KiB

met

#include <bitset>
#include<iostream>
// #include<fstream>
#include<vector>
#include<array>
#include<algorithm>
#include<set>
#include<cmath>
#include<unordered_map>
#include<iomanip>
#include <map>
#include <queue>
#include <stack>
#include <cstring>
#include <climits>
#include <chrono>
#include <random>
#include <cassert>
using namespace std;
#define PRINTARRAY(st, en, a) for(int _i = st; _i <= en; _i++) {cout << a[_i] << (_i != en ? " " : "\n");}
#define SZ(A) (int)A.size()
using LL = long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MAXK = 300000;
void bit_update(int x, int v, vector<LL> &bit) {
    for(; x <= MAXK; x += x & -x) {
        bit[x] += v;
    }
}
LL bit_query(int x, vector<LL> &bit) {
    LL sum = 0;
    for(; x > 0; x -= x & -x) {
        sum += bit[x];
    }
    return sum;
}
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> station(m + 1, 0);
    vector<int> target(n + 1, 0);
    vector<vector<int>> stationList(n + 1);
    for(int i = 1; i <= m; i++) {
        cin >> station[i];
        stationList[station[i]].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        cin >> target[i];
    }
    int k;
    cin >> k;
    vector<array<int,3>> meteor(k + 1, {0,0,0});
    for(int i = 1; i <= k; i++) {
        cin >> meteor[i][0] >> meteor[i][1] >> meteor[i][2];
    }
    queue<tuple<int, int, vector<int>>> q;
    {
        vector<int> list;
        for(int i = 1; i <= n; i++) {
            list.push_back(i);
        }
        q.push({1, k + 1, list});
    }
    vector<LL> bit(MAXK + 2, 0);
    int ptr = 0;
    vector<int> ans(n + 1, 0);
    while(!q.empty()) {
        auto [l, r, list] = q.front(); q.pop();
        // cout << l << " " << r << endl;
        if (l == r) {
            for(auto v : list) {
                ans[v] = l;
            }
            continue;
        }
        int mid = l + (r - l) / 2;
        if (ptr > mid) {
            ptr = 0;
            bit.assign(MAXK + 2, 0);
        }
        while(ptr < mid) {
            auto [ml, mr, t] = meteor[ptr + 1];
            ptr++;
            bit_update(ml, t, bit);
            bit_update(mr + 1, -t, bit);
            if (ml > mr) {
                bit_update(1, t, bit);
                // bit_update(m + 1, -t, bit);
            }
        }
        vector<int> small;
        vector<int> bigger;
        for(auto v : list) {
            LL need = target[v];
            for(auto p : stationList[v]) {
                need -= bit_query(p, bit);
            }
            if (need <= 0) {
                small.push_back(v);
            } else {
                bigger.push_back(v);
            }
        }
        if (!small.empty()) {
            q.push({l, mid, small});
        }        
        if (!bigger.empty()) {
            q.push({mid + 1, r, bigger});
        }
    }
    for(int i = 1; i <= n; i++) {
        if (ans[i] <= k) {
            cout << ans[i] << "\n";
        } else {
            cout << "NIE" << "\n";
        }
    }
}
    
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int testcase = 1;
    // cin >> testcase;
    while(testcase--) {
        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: 0 / 13
• Subtask 8: 0 / 13