Submission #1304794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304794		dreamoon	Meteors (POI11_met)	C++17	100 / 100	946 ms	50156 KiB

met

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 3e5 + 5;
int meteor[maxn];
int want[maxn];
int L[maxn], R[maxn], ans[maxn];
int N, M;
vector<array<int, 3>> events;
vector<int> stations[maxn];
bool check() {
    for (int i = 1; i <= N; i++) {
        if (L[i] <= R[i]) return false;
    }
    return true;
}
struct BIT {
    vector<int> bit;
    int n;
    BIT(int n) {
        bit.resize(n, 0);
    }

    void upd(int x, int v) {
        for (; x < bit.size(); x += (x & -x)) bit[x] += v;
    }
    int qry(int x) {
        int sum = 0;
        for (; x; x -= (x & -x)) sum += bit[x];
        return sum;
    }
    void upd_range(int l, int r, int v) {
        if (l <= r) {
            upd(l, v);
            upd(r + 1, -v);
        } else {
            upd(l, v);
            upd(M + 1, -v);
            upd(1, v);
            upd(r + 1, -v);
        }
    }
};
main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 1; i <= M; i++) {
        cin >> meteor[i];
        stations[meteor[i]].push_back(i);
    }
    for (int i = 1; i <= N; i++) {
        cin >> want[i];
        ans[i] = -1;
    }

    int Q;
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        int l, r, v;
        cin >> l >> r >> v;
        events.push_back({l, r, v});
    }
    for (int i = 1; i <= N; i++) {
        L[i] = 1;
        R[i] = Q;
    }
    while (!check()) {
        vector<int> num(N + 1, 0), mid(N + 1, 0);
        vector<vector<int>> query(Q + 5);
        BIT bit(maxn);
        for (int i = 1; i <= N; i++) {
            if (L[i] > R[i]) continue;
            mid[i] = (L[i] + R[i]) / 2;
            query[mid[i]].push_back(i);
        }
        for (int i = 1; i <= Q; i++) {
            int l = events[i - 1][0], r = events[i - 1][1], v = events[i - 1][2];
            bit.upd_range(l, r, v);

            for (auto j : query[i]) {
                for (auto k : stations[j]) {
                    num[j] += bit.qry(k);
                    num[j] = min(num[j], (long long)4e18);
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            if (L[i] > R[i]) continue;
            if (num[i] < want[i]) {
                L[i] = mid[i] + 1;
            } else {
                R[i] = mid[i] - 1;
                ans[i] = mid[i];
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        if (ans[i] != -1) cout << ans[i] << "\n";
        else cout << "NIE" << "\n";
    }

    return 0;
}

Compilation message (stderr)

met.cpp:44:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   44 | main() {
      | ^~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13