Submission #1244904

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244904		dreamoon	Meteors (POI11_met)	C++17	74 / 100	6090 ms	30680 KiB

met

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll zero = 0;
const ll mod = 998244353;
// const ll C=131;
// const ll inf=1e17;
const int len = 300;
const int t = 4;
#define Fi first
#define Se second
#define PB push_back
#define P pair<ll, ll>
#define ppl pair<P, ll>
#define LB lower_bound
#define UB upper_bound
#define SZ size()
#define BE begin()
#define EN end()
#define CON continue
#define RB rbegin()
#define EM empty()
struct BIT {
    vector<ll> bit;
    int sz;
    void init(int N) {
        bit.resize(N + 3);
        sz = N + 2;
        for (int i = 0; i <= sz; i++) {
            bit[i] = 0;
        }
    }
    void ins(int p, ll x) {
        for (; p <= sz; p += p & -p) {
            bit[p] += x;
        }
    }
    ll prS(int p) {
        ll out = 0;
        for (; p; p -= p & -p) {
            out += bit[p];
        }
        return out;
    }
} Bit;
struct QQ {
    int L, R;
    vector<int> num;
};
int M, K, Q, Y, X, big, N, T, now, H, S = 0;
// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<ll>> sta;
queue<QQ> pool;
vector<ll> need;
int l[300005], r[300005];
ll v[300005];
int ans[300005] = {};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    need.resize(N + 1);
    sta.resize(N + 1);
    for (int i = 1; i <= M; i++) {
        int x;
        cin >> x;
        sta[x].PB(i);
    }
    for (int i = 1; i <= N; i++) {
        cin >> need[i];
    }
    cin >> Q;
    for (int i = 1; i <= Q; i++) {
        cin >> l[i] >> r[i] >> v[i];
    }
    QQ ini;
    ini.L = 1;
    ini.R = Q + 1;
    for (int i = 1; i <= N; i++) {
        ini.num.PB(i);
    }
    int nd = 0;
    pool.push(ini);
    Bit.init(M);
    while (pool.SZ) {
        QQ A = pool.front();
        pool.pop();
        if (A.L >= A.R) {
            for (int x : A.num) {
                ans[x] = A.L;
            }
            CON;
        }
        int mm = A.L + A.R >> 1;

        if (mm < nd) {
            nd = 0;
            Bit.init(M);
        }
        for (; nd < mm; nd++) {
            if (l[nd + 1] <= r[nd + 1]) {
                Bit.ins(l[nd + 1], v[nd + 1]);
                Bit.ins(r[nd + 1] + 1, -v[nd + 1]);
            } else {
                Bit.ins(1, v[nd + 1]);
                Bit.ins(l[nd + 1], v[nd + 1]);
                Bit.ins(r[nd + 1] + 1, -v[nd + 1]);
            }
        }
        QQ small, big;
        small.L = A.L;
        small.R = mm;
        big.L = mm + 1;
        big.R = A.R;
        vector<ll> cnt;
        cnt.resize(N + 1);
        for (int x : A.num) {
            cnt[x] = 0;
            for (int p : sta[x]) {
                if (cnt[x] < need[x])
                    cnt[x] += Bit.prS(p);
            }
        }
        for (int x : A.num) {
            if (cnt[x] >= need[x]) {
                small.num.PB(x);
            } else {
                big.num.PB(x);
            }
        }
        /*
                cout<<endl<<mm<<":"<<endl<<endl;
                for(int x:A.num){
                    cout<<x<<" ";
                }
                cout<<endl;
                for(int x:A.num){
                    cout<<cnt[x]<<" ";
                }
                cout<<endl;
        */
        pool.push(small);
        pool.push(big);
    }
    for (int i = 1; i <= N; i++) {

        if (ans[i] > Q) {
            cout << "NIE";
        } else
            cout << ans[i];
        if (i < N) {
            cout << '\n';
        }
    }
}
/*
3 5
1 3 2 1 3
10 5 7
3
4 2 4
1 3 1
3 5 2
*/

• 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: 0 / 13
• Subtask 8: 0 / 13