oj.uz

Submission #605643

# Submission time Handle Problem Language Result Execution time Memory
605643 2022-07-25T20:49:59 Z 1ne Meteors (POI11_met) C++14
100 / 100
 1924 ms 31728 KB 
#include <stdio.h>
#include <iostream>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
const int maxN = 3 << 17;
const int maxK = 1 << 10;
const int INF = (int)1e9;
typedef long long ll;
 
int o[maxN];
 
ll add[maxN];
ll need[maxN];
int start[maxN];
ll startNeed[maxN];
 
int l[maxN];
int r[maxN];
ll a[maxN];
 
vector<int> pos[maxN];
 
int main() {
    ios_base::sync_with_stdio(0);
 
    for (int i = 0; i < maxN; i++) {
        start[i] = INF;
    }
 
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> o[i];
        pos[o[i]].push_back(i);
    }
 
    for (int i = 1; i <= n; i++) {
        cin >> need[i];
    }
 
    int q;
    cin >> q;
    for (int i = 1; i <= q; i++) { // O((m + n) * q / maxK)
        cin >> l[i] >> r[i] >> a[i];
        if (l[i] > r[i]) {
            add[1] += a[i];
            add[r[i] + 1] -= a[i];
 
            add[l[i]] += a[i];
            add[m + 1] -= a[i];
        } else {
            add[l[i]] += a[i];
            add[r[i] + 1] -= a[i];
        }
        if (i % maxK == 0 || i == q) {
            ll s = 0;
            for (int j = 1; j <= m; j++) {
                s += add[j];
                add[j] = 0;
                need[o[j]] -= s;
            }
            for (int j = 1; j <= n; j++) {
                if (start[j] == INF && need[j] <= 0) {
                    startNeed[j] = need[j];
                    start[j] = i;
                }
            }
        }
    }
 
    for (int i = 1; i <= n; i++) { // O((m + n) * maxK)
        if (start[i] == INF) {
            cout << "NIE" << endl;
            continue;
        }
        int j = start[i];
        ll s = startNeed[i];
        while (s <= 0 && j > 0) {
            for (int ii = 0; ii < (int)pos[i].size(); ii++) {
                int x = pos[i][ii];
                if (l[j] > r[j] && (x >= l[j] || x <= r[j])) {
                    s += a[j];
                }
                if (l[j] <= r[j] && (x >= l[j] && x <= r[j])) {
                    s += a[j];
                }
            }
            j--;
        }
        cout << j + 1 << endl;
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 11092 KB Output is correct
2 Correct 7 ms 11176 KB Output is correct
3 Correct 9 ms 11092 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 11200 KB Output is correct
2 Correct 12 ms 11188 KB Output is correct
3 Correct 8 ms 11092 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 12840 KB Output is correct
2 Correct 42 ms 13532 KB Output is correct
3 Correct 133 ms 13476 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 13008 KB Output is correct
2 Correct 125 ms 13140 KB Output is correct
3 Correct 301 ms 13612 KB Output is correct
4 Correct 50 ms 12640 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 12972 KB Output is correct
2 Correct 59 ms 13740 KB Output is correct
3 Correct 18 ms 11932 KB Output is correct
4 Correct 116 ms 13396 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 12868 KB Output is correct
2 Correct 110 ms 13212 KB Output is correct
3 Correct 67 ms 12852 KB Output is correct
4 Correct 151 ms 13736 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 759 ms 25268 KB Output is correct
2 Correct 695 ms 20664 KB Output is correct
3 Correct 51 ms 15008 KB Output is correct
4 Correct 1924 ms 30016 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1252 ms 24692 KB Output is correct
2 Correct 638 ms 20580 KB Output is correct
3 Correct 53 ms 14204 KB Output is correct
4 Correct 1317 ms 31728 KB Output is correct