oj.uz

Submission #226645

# Submission time Handle Problem Language Result Execution time Memory
226645 2020-04-24T16:46:09 Z dolphingarlic Meteors (POI11_met) C++14
100 / 100
 2301 ms 65536 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int n, m, l[300002], r[300002];
ll bit[300002], req[300002], num[300002];
pair<int, int> event[300002];
vector<int> owned[300002], to_check[300002];

void update(int pos, ll val) {
    for (; pos <= m; pos += (pos & (-pos))) bit[pos] += val;
}

ll query(int pos) {
    ll ans = 0;
    for (; pos; pos -= (pos & (-pos))) ans += bit[pos];
    return ans;
}

void update(pair<int, int> range, ll val) {
    if (range.first > range.second) update(1, val);
    update(range.first, val), update(range.second + 1, -val);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    FOR(i, 1, m + 1) {
        int x;
        cin >> x;
        owned[x].push_back(i);
    }
    FOR(i, 1, n + 1) cin >> req[i];

    int k;
    cin >> k;
    FOR(i, 1, k + 1) cin >> event[i].first >> event[i].second >> num[i];

    FOR(i, 1, n + 1) l[i] = 1, r[i] = k + 1;
    bool done = false;
    while (!done) {
        done = true;

        fill(bit + 1, bit + m + 1, 0);
        FOR(i, 1, n + 1) if (l[i] != r[i]) to_check[(l[i] + r[i]) / 2].push_back(i);

        FOR(i, 1, k + 1) {
            update(event[i], num[i]);
            while (to_check[i].size()) {
                done = false;
                int nation = to_check[i].back();
                to_check[i].pop_back();

                ll tot = 0;
                for (int j : owned[nation]) {
                    tot += query(j);
                    if (tot >= req[nation]) break;
                }
                if (tot >= req[nation]) r[nation] = i;
                else l[nation] = i + 1;
            }
        }
    }

    FOR(i, 1, n + 1) {
        if (l[i] == k + 1) cout << "NIE\n";
        else cout << l[i] << '\n';
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 14464 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Correct 13 ms 14592 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 14592 KB Output is correct
2 Correct 13 ms 14592 KB Output is correct
3 Correct 14 ms 14592 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 16632 KB Output is correct
2 Correct 121 ms 18552 KB Output is correct
3 Correct 108 ms 18272 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 17656 KB Output is correct
2 Correct 111 ms 17784 KB Output is correct
3 Correct 119 ms 18808 KB Output is correct
4 Correct 42 ms 16856 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 17144 KB Output is correct
2 Correct 107 ms 19320 KB Output is correct
3 Correct 55 ms 15480 KB Output is correct
4 Correct 128 ms 18708 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 16120 KB Output is correct
2 Correct 115 ms 17784 KB Output is correct
3 Correct 86 ms 16376 KB Output is correct
4 Correct 130 ms 19960 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1119 ms 35540 KB Output is correct
2 Correct 721 ms 22900 KB Output is correct
3 Correct 253 ms 21112 KB Output is correct
4 Correct 1791 ms 63464 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1150 ms 34276 KB Output is correct
2 Correct 743 ms 23024 KB Output is correct
3 Correct 214 ms 21128 KB Output is correct
4 Correct 2301 ms 65536 KB Output is correct