oj.uz

Submission #869747

# Submission time Handle Problem Language Result Execution time Memory
869747 2023-11-05T13:28:17 Z riariti Meteors (POI11_met) C++17
24 / 100
 6 ms 5672 KB 
#include <bits/stdc++.h>

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

using i64 = long long;

const i64 MXN = 3E3 + 5;

i64 b[MXN] = {};

int z[MXN] = {};
int x[MXN] = {};
i64 c[MXN] = {};

std::array<int, 2> lohi[MXN];
std::set<int> wrk[MXN];
std::vector<int> rg[MXN];

i64 t[4 * MXN] = {};
void build(int v, int l, int r) {
    t[v] = 0;
    if (l == r) {
        t[v] = 0;
        return;
    }

    int mid = (l + r) / 2;

    build(v + v, l, mid);
    build(v + v + 1, mid + 1, r);
}
void upd(int v, int l, int r, int ql, int qr, i64 x) {
    if (ql <= l && r <= qr) {
        t[v] += x;
        return;
    }

    if (ql > r || qr < l) {
        return;
    }

    int mid = (l + r) / 2;

    upd(v + v, l, mid, ql, qr, x);
    upd(v + v + 1, mid + 1, r, ql, qr, x);
}
i64 get(int v, int l, int r, int pos, i64 sum) {
    sum += t[v];
    if (l == r) {
        return sum;
    }

    int mid = (l + r) / 2;

    if (pos <= mid) {
        return get(v + v, l, mid, pos, sum);
    } else {
        return get(v + v + 1, mid + 1, r, pos, sum);
    }
}

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

    int n, m;
    std::cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u;
        std::cin >> u;

        rg[u].push_back(i);
    }
    for (int i = 1; i <= n; i++) {
        auto &x = b[i];
        std::cin >> x;
    }
    int q;
    std::cin >> q;
    for (int i = 1; i <= q; i++) {
        auto &l = z[i];
        auto &r = x[i];
        auto &a = c[i];

        std::cin >> l >> r >> a;
    }

    for (int i = 1; i <= n; i++) {
        lohi[i] = {1, q + 1};
    }

    int tt = std::__lg(MXN) + 1;
    while (tt--) {
        build(1, 1, m);

        for (int i = 1; i <= n; i++) {
            int md = (lohi[i][0] + lohi[i][1]) / 2;
            wrk[md].insert(i);
        }

        for (int i = 1; i <= q; i++) {
            if (z[i] <= x[i]) {
                upd(1, 1, m, z[i], x[i], c[i]);
            } else {
                upd(1, 1, m, 1, x[i], c[i]);
                upd(1, 1, m, z[i], m, c[i]);
            }

            for (int to : wrk[i]) {
                i64 sum = 0;

                for (int d : rg[to]) {
                    sum += get(1, 1, m, d, 0);

                    if (sum >= b[to]) {
                        break;
                    }
                }

                if (sum >= b[to]) {
                    lohi[to][1] = i;
                } else {
                    lohi[to][0] = i + 1;
                }
            }
        }

        for (int i = 1; i <= q; i++) {
            wrk[i].clear();
        }
    }

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

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 5468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 5672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1628 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 856 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -