Submission #532714

#	Time	Username	Problem	Language	Result	Execution time	Memory
532714		Ai7081	Meteors (POI11_met)	C++17	100 / 100	2476 ms	65536 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define long long long

const int N = 300005;

int n, m, q, l[N], r[N], a[N], b[N];
long want[N], fen[N], val[N];
vector<int> own[N], check[N];

void add(int i, int val) {
    for (; i<=m; i+=i&(-i)) fen[i] += val;
    return;
}

long sum(int i) {
    long ret = 0;
    for (; i>0; i-=i&(-i)) ret += fen[i];
    return ret;
}

int main() {
    cin >> n >> m;
    for (int i=1; i<=m; i++) {
        int x;
        cin >> x;
        own[x].push_back(i);
    }
    for (int i=1; i<=n; i++) cin >> want[i];
    cin >> q;
    for (int i=1; i<=q; i++) cin >> a[i] >> b[i] >> val[i];
    fill_n(l, N, 1);
    fill_n(r, N, q+1);
    int time = 20;
    while (time--) {
        fill_n(check, N, vector<int>());
        for (int i=1; i<=n; i++) {
            if (l[i] < r[i]) check[(l[i]+r[i])/2].push_back(i);
        }
        fill_n(fen, N, 0);
        for (int i=1; i<=q; i++) {
            if (a[i] <= b[i]) add(a[i], val[i]), add(b[i]+1, -val[i]);
            else add(1, val[i]), add(b[i]+1, -val[i]), add(a[i], val[i]);
            for (auto j : check[i]) {
                long nowsum = 0;
                for (auto area : own[j]) nowsum += sum(area), nowsum = min(nowsum, (long)1e9);
                if (nowsum >= want[j]) r[j] = i;
                else l[j] = i+1;
            }
        }
    }
    for (int i=1; i<=n; i++) {
        if (l[i] == q+1) cout << "NIE" << endl;
        else cout << l[i] << endl;
    }
    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