Submission #1320581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1320581		orzorzorz	Meteors (POI11_met)	C++20	100 / 100	720 ms	30676 KiB

met

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 300005;
int n, m, k;
int owner[MAXN];
long long goal[MAXN];
vector<int> stations[MAXN];
int ans[MAXN];

struct Shower {
    int l, r;
    long long a;
} showers[MAXN];

long long bit[MAXN];

void update(int idx, long long val) {
    for (; idx <= m; idx += idx & -idx)
        bit[idx] += val;
}

void range_update(int l, int r, long long v) {
    if (l <= r) {
        update(l, v);
        update(r + 1, -v);
    } else {
        update(l, v);
        update(m + 1, -v);
        update(1, v);
        update(r + 1, -v);
    }
}

long long point_query(int idx) {
    long long res = 0;
    for (; idx > 0; idx -= idx & -idx)
        res += bit[idx];
    return res;
}

void solve(vector<int> states, int L, int R) {
    if (states.empty()) return;
    if (L == R) {
        for (int s : states) ans[s] = L;
        return;
    }

    int mid = L + (R - L) / 2;
    for (int i = L; i <= mid; ++i) {
        range_update(showers[i].l, showers[i].r, showers[i].a);
    }

    vector<int> left, right;
    for (int s : states) {
        long long total = 0;
        for (int pos : stations[s]) {
            total += point_query(pos);
            if (total >= goal[s]) break; 
        }

        if (total >= goal[s]) {
            left.push_back(s);
        } else {
            goal[s] -= total;
            right.push_back(s);
        }
    }

    // Rollback BIT
    for (int i = L; i <= mid; ++i) {
        range_update(showers[i].l, showers[i].r, -showers[i].a);
    }

    solve(left, L, mid);
    solve(right, mid + 1, R);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m)) return 0;
    for (int i = 1; i <= m; ++i) {
        int o;
        cin >> o;
        stations[o].push_back(i);
    }
    for (int i = 1; i <= n; ++i) cin >> goal[i];
    cin >> k;
    for (int i = 1; i <= k; ++i) {
        cin >> showers[i].l >> showers[i].r >> showers[i].a;
    }

    vector<int> initial_states;
    for (int i = 1; i <= n; ++i) initial_states.push_back(i);

    // Range is 1 to k+1, where k+1 indicates NIE
    solve(initial_states, 1, k + 1);

    for (int i = 1; i <= n; ++i) {
        if (ans[i] > k) cout << "NIE\n";
        else cout << ans[i] << "\n";
    }

    return 0;
}

• 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