Submission #1226879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226879		nh0902	Meteors (POI11_met)	C++20	74 / 100	3163 ms	53676 KiB

met

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 3e5 + 10;

const int M = 1e3 + 100;

int n, m, k, p[N], l[N], r[N], a[N];

vector<int> stations[N];

int cur_l[N], cur_r[N], ans[N];

vector<int> cur[N]; // cur[i] : index k that had (cur_l + cur_r) / 2 = mid;

//segment tree
int st[4 * N];

void build(int id, int l, int r) {
    st[id] = 0;
    if (l == r) return;

    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
}

void update(int id, int l, int r, int u, int v, int val) {
    if (r < u || v < l) return;

    if (u <= l && r <= v) {
        st[id] += val;
        return;
    }

    int mid = (l + r) / 2;
    update(id * 2, l, mid, u, v, val);
    update(id * 2 + 1, mid + 1, r, u, v, val);
}

void update(int l, int r, int val) {
    if (l <= r) update(1, 1, m, l, r, val);
    else {
        update(1, 1, m, l, m, val);
        update(1, 1, m, 1, r, val);
    }
}

int get(int id, int l, int r, int p) {
    if (l == r) return st[id];

    int mid = (l + r) / 2;

    if (p <= mid) return st[id] + get(id * 2, l, mid, p);
    else return st[id] + get(id * 2 + 1, mid + 1, r, p);
}

int get(int i) {
    return get(1, 1, m, i);
}

void prep() {
    cin >> n >> m;
    int x;
    for (int i = 1; i <= m; i ++) {
        cin >> x;
        stations[x].push_back(i);
    }
    for (int i = 1; i <= n; i ++) {
        cin >> p[i];
    }
    cin >> k;
    for (int i = 1; i <= k; i ++) {
        cin >> l[i] >> r[i] >> a[i];
    }

    for (int i = 1; i <= n; i ++) {
        cur_l[i] = 1;
        cur_r[i] = k;
    }
}

void process() {
    build(1, 1, m);
    
    for (int i = 1; i <= k; i ++) cur[i].clear();
    for (int i = 1; i <= n; i ++) cur[(cur_l[i] + cur_r[i]) / 2].push_back(i);

    for (int i = 1; i <= k; i ++) {
        update(l[i], r[i], a[i]);

        for (int j : cur[i]) {
            if (cur_l[j] > cur_r[j]) continue;
            int cnt = 0;
            for (int s : stations[j]) cnt += get(s);
            if (cnt >= p[j]) cur_r[j] = i;
            else cur_l[j] = i + 1;
        }
    }
}

void solve() {

    for (int i = 1; i <= log2(k) + 3; i ++) process();

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

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    prep();
    solve();

    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: 0 / 13
• Subtask 8: 0 / 13