oj.uz

Submission #660932

# Submission time Handle Problem Language Result Execution time Memory
660932 2022-11-23T14:42:02 Z bruteforce Meteors (POI11_met) C++14
0 / 100
 37 ms 65536 KB 
// Author: __BruteForce__
#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

#define MAX_N 300005

int n, m, k;
vector<int> state[MAX_N];
int64 reqd[MAX_N];
int lo[MAX_N], hi[MAX_N], ql[MAX_N], qr[MAX_N];
int64 qa[MAX_N];
int64 bit[MAX_N];
stack<int> to_check[MAX_N];

void init() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int o;
        cin >> o;
        state[o].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> reqd[i];
    cin >> k;
    for (int i = 1; i <= k; i++) cin >> ql[i] >> qr[i] >> qa[i];
    for (int i = 1; i <= n; i++) lo[i] = 1, hi[i] = k + 1;
}

void update_bit(int p, int64 v) {
    for (; p <= m; p += p & -p) bit[p] += v;
}

int64 get_bit(int p) {
    int64 sum = 0;
    for (; p; p -= p & -p) sum += bit[p];
    return sum;
}

void update(int idx) {
    update_bit(ql[idx], qa[idx]);
    update_bit(qr[idx] + 1, -qa[idx]);
    if (ql[idx] > qr[idx]) update_bit(1, qa[idx]);
}

void solve() {
    bool changed = true;
    // Parallel Binary Search
    while (changed) {
        changed = false;

        // Reset
        memset(bit, 0, sizeof(bit));
        for (int i = 1; i <= n; i++)
            if (lo[i] != hi[i]) to_check[(lo[i] + hi[i]) >> 1].push(i);

        // Update
        for (int i = 1; i <= k; i++) {
            update(i);
            while (to_check[i].size()) {
                changed = true;
                int idx = to_check[i].top();
                to_check[i].pop();

                int64 sum = 0;
                for (auto sector : state[idx]) {
                    sum += get_bit(sector);
                    if (sum >= reqd[idx]) break;
                }
                if (sum >= reqd[idx])
                    hi[idx] = i;
                else
                    lo[idx] = i + 1;
            }
        }
    }

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

int main() {
    cin.tie(0)->sync_with_stdio(false);

    init();
    solve();
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 33 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 37 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 34 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -