oj.uz

Submission #1109727

# Submission time Handle Problem Language Result Execution time Memory
1109727 2024-11-07T11:42:58 Z GasmaskChan Meteors (POI11_met) C++17
100 / 100
 1667 ms 56048 KB 
#include <bits/stdc++.h>

using namespace std;
#define int long long

const int MAX = 3e5 + 5;

struct wifi {
    int n;
    vector<int> BIT;

    wifi(int n) : n(n) {
        BIT.assign(n + 5, 0);
    }

    void update(int i, const int &val) {
        for (; i <= n; i += -i & i) BIT[i] += val;
    }

    void update(const int &l, const int &r, const int &val) {
        update(l, val);
        update(r + 1, -val);
    }

    int get(int i) {
        int res = 0;
        for (; i > 0; i -= -i & i) res += BIT[i];
        return res;
    }
};

int a[MAX], p[MAX];
array<int, 3> query[MAX];
pair<int, int> range[MAX];
vector<int> own[MAX];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    freopen("test.inp", "r", stdin); freopen("test.out", "w", stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        own[a[i]].push_back(i);
    }

    for (int i = 1; i <= n; i++) cin >> p[i];

    int k;
    cin >> k;
    for (int i = 1; i <= k; i++) cin >> query[i][0] >> query[i][1] >> query[i][2];

    for (int i = 1; i <= n; i++) range[i] = {0, k + 1};

    while (true) {
        bool ok = false;
        unordered_map<int ,vector<int>> q;
        wifi waifu(m);

        for (int i = 1; i <= n; i++) {
            if (range[i].first >= range[i].second) continue;
            ok = true;
            q[(range[i].first + range[i].second) >> 1].push_back(i);
        }

        if (!ok) break;

        for (int l, r, v, i = 0; i <= k; i++) {
            l = query[i][0], r = query[i][1], v = query[i][2];
            if (i) {
                if (l <= r) {
                    waifu.update(l, r, v);
                }
                else {
                    waifu.update(l, m, v);
                    waifu.update(1, r, v);
                }
            }

            for (auto &id : q[i]) {
                int cnt = 0;
                for (auto &j : own[id]) {
                    cnt += waifu.get(j);
                    cnt = min(cnt, p[id] + 1);
                }
                if (cnt >= p[id]) range[id].second = i;
                else range[id].first = i + 1;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (range[i].second <= k) cout << range[i].second << '\n';
        else cout << "NIE\n";
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 21044 KB Output is correct
2 Correct 136 ms 21572 KB Output is correct
3 Correct 116 ms 22020 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 21164 KB Output is correct
2 Correct 123 ms 21292 KB Output is correct
3 Correct 123 ms 22096 KB Output is correct
4 Correct 28 ms 16584 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 21812 KB Output is correct
2 Correct 105 ms 21960 KB Output is correct
3 Correct 70 ms 20064 KB Output is correct
4 Correct 115 ms 22104 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 21692 KB Output is correct
2 Correct 117 ms 21180 KB Output is correct
3 Correct 95 ms 21804 KB Output is correct
4 Correct 137 ms 22368 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1117 ms 49892 KB Output is correct
2 Correct 752 ms 43436 KB Output is correct
3 Correct 408 ms 35584 KB Output is correct
4 Correct 1667 ms 54620 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1198 ms 49756 KB Output is correct
2 Correct 798 ms 43264 KB Output is correct
3 Correct 326 ms 31164 KB Output is correct
4 Correct 1628 ms 56048 KB Output is correct