Submission #1095504

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095504		mohammad86	Meteors (POI11_met)	C++17	100 / 100	1438 ms	36180 KiB

met

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 3e5 + 100;
const int k = 550;
int n, m, q;
int o[maxn];
ll p[maxn];
ll pc[maxn];
int lc[maxn];
int rc[maxn];
int ac[maxn];
int ans[maxn];
ll add[maxn];
bool mark[maxn];
vector<int> segments[maxn];

int IndToGroup(int index) {
    return (index -1) /k +1;
}

int Sgroup(int gr) {
    return (gr -1) *k +1;
}

int Fgroup(int gr) {
    return min(gr * k, q);
}

void calAns(int x, int gr) {
    for (int i = Sgroup(gr); i <= Fgroup(gr); i++) {
        for (int s : segments[x]) {
            if ((lc[i] <= rc[i] && (lc[i] <= s && s <= rc[i]))
                || (lc[i] > rc[i] && (s <= rc[i] || s >= lc[i]))) {
                    pc[x] -= ac[i];
                    if (pc[x] <= 0) {
                        mark[x] = true;
                        ans[x] = i;
                        return;
                    }
            }
        }
    }
}

void update(int gr) {
    fill(add +1, add+m+1, 0);
    copy(p +1, p + n+1, pc +1);

    for (int i = Sgroup(gr); i <= Fgroup(gr); i++) {
        if (lc[i] <= rc[i]) {
            add[lc[i]] += ac[i];
            add[rc[i]+1] -= ac[i];
        } else {
            add[1] += ac[i];
            add[rc[i]+1] -= ac[i];
            add[lc[i]] += ac[i];
        }
    }

    ll cnt = 0;

    for (int i = 1; i <= m; i++) {
        cnt += add[i];
        p[o[i]] -= cnt;
    }

    for (int i = 1; i <= n; i++) {
        if (p[i] <= 0 && !mark[i]) {
            calAns(i, gr);
        }
    }
}

int main () {
    ios_base::sync_with_stdio(false);

    cin >> n >> m;

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

    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }

    cin >> q;

    int last_group = 1;

    for (int i = 1; i <= q; i++) {
        int gr = IndToGroup(i);
        if (last_group != gr) {
            update(last_group);
        }
        last_group = gr;
        cin >> lc[i] >> rc[i] >> ac[i];
    }
    update(IndToGroup(q));

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

• 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