제출 #660932

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
660932		bruteforce	새로운 문제 (POI11_met)	C++14	0 / 100	37 ms	65536 KiB

met

// 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
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13