Submission #1095296

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095296		mohammad86	Meteors (POI11_met)	C++17	0 / 100	6047 ms	24352 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], 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) {
    ll 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 && l <= s && s <= r) || 
                (r < l && (s <= l || s >= r))) {
                val -= a;
                if (val <= 0) {
                    ans[x] = i;
                    mark[x] = true;
                    return;
                }
            }
        }
    }
}

void update(int last) {
    int gr = IndToGroup(last);
    fill(add + 1, add + m + 1, 0);
    copy(p + 1, p + n + 1, p1 + 1);

    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;
            if (r + 1 <= m) add[r + 1] -= a;
        } else {
            add[1] += a;
            if (r + 1 <= m) add[r + 1] -= a;
            add[l] += 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.tie(nullptr);

    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++) {
        cout << (ans[i] == 0 ? "NIE" : to_string(ans[i])) << endl;
    }

    return 0;
}

• 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