Submission #1109727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109727		GasmaskChan	Meteors (POI11_met)	C++17	100 / 100	1667 ms	56048 KiB

met

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAX = 3e5 + 5;

struct wifi {
    int n;
    vector<int> BIT;

    wifi(int n) : n(n) {
        BIT.assign(n + 5, 0);
    }

    void update(int i, const int &val) {
        for (; i <= n; i += -i & i) BIT[i] += val;
    }

    void update(const int &l, const int &r, const int &val) {
        update(l, val);
        update(r + 1, -val);
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= -i & i) res += BIT[i];
        return res;
    }
};

int a[MAX], p[MAX];
array<int, 3> query[MAX];
pair<int, int> range[MAX];
vector<int> own[MAX];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        own[a[i]].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 >> query[i][0] >> query[i][1] >> query[i][2];

    for (int i = 1; i <= n; i++) range[i] = {0, k + 1};

    while (true) {
        bool ok = false;
        unordered_map<int ,vector<int>> q;
        wifi waifu(m);

        for (int i = 1; i <= n; i++) {
            if (range[i].first >= range[i].second) continue;
            ok = true;
            q[(range[i].first + range[i].second) >> 1].push_back(i);
        }

        if (!ok) break;

        for (int l, r, v, i = 0; i <= k; i++) {
            l = query[i][0], r = query[i][1], v = query[i][2];
            if (i) {
                if (l <= r) {
                    waifu.update(l, r, v);
                }
                else {
                    waifu.update(l, m, v);
                    waifu.update(1, r, v);
                }
            }

            for (auto &id : q[i]) {
                int cnt = 0;
                for (auto &j : own[id]) {
                    cnt += waifu.get(j);
                    cnt = min(cnt, p[id] + 1);
                }
                if (cnt >= p[id]) range[id].second = i;
                else range[id].first = i + 1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (range[i].second <= k) cout << range[i].second << '\n';
        else cout << "NIE\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