Submission #1243393

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243393		t6stks	Meteors (POI11_met)	C++20	100 / 100	802 ms	31788 KiB

met

#include <bits/stdc++.h>
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) x.begin(), x.end()

using namespace std;
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vii = vector<pii>;
using vll = vector<pll>;

struct BIT {
    int n;
    vl b;
    BIT(int _n) : n(_n) {
        b.resize(n + 1);
    }

    void reset() {
        b.assign(n + 1, 0);
    }

    void upd(int x, int v) {
        for (; x <= n; x += x & -x) b[x] += v;
    }

    ll qq(int x) {
        ll res = 0;
        for (; x; x &= x - 1) res += b[x];
        return res;
    }
};

struct Data {
    int l, r;
    vi ids;
};

void sol() {
    int n, m;
    cin >> n >> m;

    BIT bit(m + 1);
    vvi pos(n + 1);
    vi req(n + 1);

    for (int i = 1; i <= m; i++) {
        int x;
        cin >> x;
        pos[x].push_back(i);
    }

    for (int i = 1; i <= n; i++) cin >> req[i];

    int k;
    cin >> k;
    vi l(k + 1), r(k + 1), w(k + 1);
    for (int i = 1; i <= k; i++) cin >> l[i] >> r[i] >> w[i];

    queue<Data> qq;
    {
        vi ids;
        for (int i = 1; i <= n; i++) ids.push_back(i);
        qq.push({1, k + 1, ids});
    }

    int ptr = 0;
    vi ans(n + 1);
    while (SZ(qq)) {
        auto [lo, hi, ids] = qq.front();
        qq.pop();

        if (lo == hi) {
            for (int id: ids) ans[id] = lo;
            continue;
        }

        int mid = lo + (hi - lo) / 2;
        if (ptr > mid) {
            bit.reset();
            ptr = 0;
        }

        while (ptr < mid) {
            ++ptr;
            bit.upd(l[ptr], w[ptr]);
            bit.upd(r[ptr] + 1, -w[ptr]);
            if (l[ptr] > r[ptr]) bit.upd(1, w[ptr]);
        }

        vi id_l, id_r;
        for (int id: ids) {
            ll sum = 0;
            for (int p: pos[id]) {
                sum += bit.qq(p);
                if (sum >= req[id]) {
                    id_l.push_back(id);
                    break;
                }
            }
            if (sum < req[id])
                id_r.push_back(id);
        }
        if (SZ(id_l))
            qq.push({lo, mid, id_l});

        if (SZ(id_r))
            qq.push({mid + 1, hi, id_r});
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i] == k + 1) cout << "NIE\n";
        else cout << ans[i] << '\n';
    }
}

signed main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    sol();
}

• 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