oj.uz

Submission #869728

# Submission time Handle Problem Language Result Execution time Memory
869728 2023-11-05T12:54:51 Z riariti Meteors (POI11_met) C++17
74 / 100
 2392 ms 58928 KB 
#include <bits/stdc++.h>

#ifdef local
#include "../../local.hpp"
#else
#define dbg(...)
#endif

using i64 = long long;

int n, m;

std::vector<int> tree;
void add(int x, i64 val) {
    while (x <= m) {
        tree[x] += val;
        x += (x & -x);
    }
}
i64 sum(int x) {
    i64 s = 0;
    while (x > 0) {
        s += tree[x];
        x -= (x & -x);
    }
    return s;
}

int32_t main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);

#ifdef local
    freopen("program.in", "r", stdin);
    freopen("program.out", "w", stdout);
    freopen("program.err", "w", stderr);
#endif

    std::cin >> n >> m;
    std::vector<int> o(m + 1);
    for (int i = 1; i <= m; i++) {
        std::cin >> o[i];
    }
    std::vector<int> p(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> p[i];
    }
    int k;
    std::cin >> k;
    std::vector<int> l(k + 1), r(k + 1), a(k + 1);
    for (int i = 1; i <= k; i++) {
        std::cin >> l[i] >> r[i] >> a[i];
    }

    dbg(n, m);
    dbg(o);
    dbg(p);
    dbg(k);
    dbg(l, r, a);

    std::map<int, std::vector<int>> ow;
    for (int i = 1; i <= m; i++) {
        ow[o[i]].push_back(i);
    }
    std::vector<int> lo(n + 1, 0 + 1), hi(n + 1, k + 1);
    dbg(lo, hi);

    tree.assign(m + 1, 0);
    dbg(tree);

    bool chk = true;
    std::map<int, std::vector<int>> wrk;
    while (chk) {
        chk = false;

        tree.assign(m + 1, 0);
        dbg(tree);

        for (int i = 1; i <= n; i++) {
            if (lo[i] == hi[i]) {
                continue;
            }

            int m = lo[i] + (hi[i] - lo[i]) / 2;
            dbg(m);
            wrk[m].push_back(i);
        }

        for (int q = 1; q <= k; q++) {
            if (l[q] <= r[q]) {
                add(l[q], a[q]);
                add(r[q] + 1, -a[q]);
            } else {
                add(1, a[q]);
                add(r[q] + 1, -a[q]);
                add(l[q], a[q]);
            }

            dbg(tree);

            while (!wrk[q].empty()) {
                chk = true;

                auto x = wrk[q].back();
                wrk[q].pop_back();

                i64 su = 0;
                for (auto pls : ow[x]) {
                    su += sum(pls);

                    if (su >= p[x]) {
                        break;
                    }
                }
                dbg(su);

                if (su >= p[x]) {
                    hi[x] = q;
                } else {
                    lo[x] = q + 1;
                }
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        if (lo[i] <= k) {
            std::cout << lo[i] << "\n";
        } else {
            std::cout << "NIE\n";
        }
    }

    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 7508 KB Output is correct
2 Correct 246 ms 11044 KB Output is correct
3 Correct 199 ms 9808 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 9004 KB Output is correct
2 Correct 177 ms 8920 KB Output is correct
3 Correct 209 ms 11348 KB Output is correct
4 Correct 51 ms 4548 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 7504 KB Output is correct
2 Correct 225 ms 11604 KB Output is correct
3 Correct 84 ms 5464 KB Output is correct
4 Correct 214 ms 10700 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 6480 KB Output is correct
2 Correct 171 ms 9040 KB Output is correct
3 Correct 120 ms 7404 KB Output is correct
4 Correct 261 ms 12376 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2392 ms 58928 KB Output is correct
2 Incorrect 1012 ms 38800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2310 ms 56632 KB Output is correct
2 Incorrect 1018 ms 37340 KB Output isn't correct
3 Halted 0 ms 0 KB -