Submission #1095277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095277		mohammad86	Meteors (POI11_met)	C++14	0 / 100	6063 ms	20048 KiB

met

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int maxn = 3e5 +100;
const int k = 550;

int n, m, q;
pair<pii, int> queries[maxn];
vector<int> segments[maxn];
int o[maxn];
ll p[maxn];
ll p1[maxn];
bool mark[maxn];
int ans[maxn];
ll add[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) {
    int val = p1[x];
    int start = Sgroup(gr);
    int finish = Fgroup(gr);

    for (int s : segments[x]) {
        for (int i = start; i <= finish; i++) {
            int l = queries[i].first.first;
            int r = queries[i].first.second;
            int a = queries[i].second;

            if (l <= r) {
                if (l <= s && s <= r) {
                    val -= a;
                    if (val <= 0) {
                        ans[x] = i;
                        mark[x] = true;
                        return;
                    }
                }
            } else {
                if (s <= l) {
                    val -= a;
                    if (val <= 0) {
                        ans[x] = i;
                        mark[x] = true;
                        return;
                    }
                } else if (s >= r) {
                    val -= a;
                    if (val <= 0) {
                        ans[x] = i;
                        mark[x] = true;
                        return;
                    }
                }
            }
        }
    }
}

void update(int last) {
    int gr = IndToGroup(last);

    for (int i = 1; i <= m; i++) {
        add[i] = 0;
    }

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

    for (int i = Sgroup(gr); i <= last; i++) {
        int l = queries[i].first.first;
        int r = queries[i].first.second;
        int a = queries[i].second;

        if (r >= l) {
            add[l] += a;
            add[r+1] -= a;
        } else {
            add[1] += a;
            add[r+1] -= a;
            add[l] += a;
            add[m+1] -= a;
        }
    }

    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_gr = 1;

    for (int i = 1; i <= q; i++) {
        int gr = IndToGroup(i);
        if (last_gr != gr) {
            update(i -1);
        }
        int l, r, a;
        cin >> l >> r >> a;
        queries[i] = {{l, r}, a};
    }
    update(q);

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

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13