oj.uz

답안 #869742

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
869742 2023-11-05T13:12:30 Z riariti Meteors (POI11_met) C++17
74 / 100
 563 ms 65536 KB 
#include <bits/stdc++.h>

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

using i64 = long long;
#define int i64

constexpr int MXN = 3E5 + 9;
constexpr int MXM = 3E5 + 9;

int n, m;
int o[MXM] = {};
int p[MXN] = {};

int k;
int l[MXM] = {};
int r[MXM] = {};
int a[MXM] = {};

int lo[MXN] = {};
int hi[MXN] = {};

i64 t[MXN * 4] = {};

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

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

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

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

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

        build(1, 1, m);

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

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

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

            for (auto x : wrk[q]) {
                chk = true;

                i64 su = 0;
                for (auto pls : ow[x]) {
                    su += get(1, 1, m, pls, 0);

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

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

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

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 14936 KB Output is correct
2 Correct 6 ms 14940 KB Output is correct
3 Correct 6 ms 14988 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 15092 KB Output is correct
2 Correct 5 ms 14832 KB Output is correct
3 Correct 7 ms 14940 KB Output is correct

Subtask #3
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 366 ms 24816 KB Output is correct
2 Correct 516 ms 27792 KB Output is correct
3 Correct 505 ms 26168 KB Output is correct

Subtask #4
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 447 ms 25536 KB Output is correct
2 Correct 459 ms 25628 KB Output is correct
3 Correct 532 ms 27784 KB Output is correct
4 Correct 102 ms 20308 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 268 ms 25052 KB Output is correct
2 Correct 415 ms 27664 KB Output is correct
3 Correct 230 ms 21596 KB Output is correct
4 Correct 504 ms 26676 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 381 ms 24272 KB Output is correct
2 Correct 415 ms 25844 KB Output is correct
3 Correct 382 ms 24612 KB Output is correct
4 Correct 563 ms 27844 KB Output is correct

Subtask #7
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 356 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 359 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -