oj.uz

Submission #226642

# Submission time Handle Problem Language Result Execution time Memory
226642 2020-04-24T16:36:43 Z dolphingarlic Meteors (POI11_met) C++14
74 / 100
 1259 ms 43464 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]) l[nation] = i + 1;
                else r[nation] = i;
            }
        }
    }

    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 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 #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 17272 KB Output is correct
2 Correct 120 ms 19708 KB Output is correct
3 Correct 109 ms 19320 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 18680 KB Output is correct
2 Correct 109 ms 18656 KB Output is correct
3 Correct 131 ms 19960 KB Output is correct
4 Correct 46 ms 17272 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 17656 KB Output is correct
2 Correct 106 ms 20344 KB Output is correct
3 Correct 55 ms 15992 KB Output is correct
4 Correct 110 ms 19704 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 17148 KB Output is correct
2 Correct 118 ms 18808 KB Output is correct
3 Correct 86 ms 17400 KB Output is correct
4 Correct 129 ms 21112 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1176 ms 43464 KB Output is correct
2 Incorrect 738 ms 30588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1259 ms 42092 KB Output is correct
2 Incorrect 771 ms 29300 KB Output isn't correct
3 Halted 0 ms 0 KB -