oj.uz

Submission #1095504

# Submission time Handle Problem Language Result Execution time Memory
1095504 2024-10-02T12:41:03 Z mohammad86 Meteors (POI11_met) C++17
100 / 100
 1438 ms 36180 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 4 ms 7516 KB Output is correct
3 Correct 5 ms 7516 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7516 KB Output is correct
2 Correct 4 ms 7524 KB Output is correct
3 Correct 5 ms 7512 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 9812 KB Output is correct
2 Correct 54 ms 11092 KB Output is correct
3 Correct 83 ms 10576 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 10216 KB Output is correct
2 Correct 73 ms 10404 KB Output is correct
3 Correct 70 ms 11088 KB Output is correct
4 Correct 35 ms 9308 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 9820 KB Output is correct
2 Correct 60 ms 11184 KB Output is correct
3 Correct 13 ms 8536 KB Output is correct
4 Correct 79 ms 10856 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 9812 KB Output is correct
2 Correct 64 ms 10492 KB Output is correct
3 Correct 44 ms 10004 KB Output is correct
4 Correct 98 ms 11288 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 28776 KB Output is correct
2 Correct 208 ms 23640 KB Output is correct
3 Correct 40 ms 12768 KB Output is correct
4 Correct 1438 ms 34076 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 907 ms 27864 KB Output is correct
2 Correct 258 ms 22388 KB Output is correct
3 Correct 40 ms 13136 KB Output is correct
4 Correct 1262 ms 36180 KB Output is correct