Submission #1149660

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149660		Persia	Meteors (POI11_met)	C++17	100 / 100	902 ms	61024 KiB

met

#include <bits/stdc++.h>

using namespace std;

#define bit(i, x) (x >> i & 1)
#define ll long long
#define sz(x) (int)x.size()

const int N = 3e5 + 5;
const int mod = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}

int n, m;
int o[N], p[N];
int k;
array<int, 3> q[N];

vector<int> adj[N];
int L[N], R[N], res[N];
ll sum[N];
vector<int> qq[N];

struct BIT{
    vector<ll> bit;
    int n;

    BIT(int _n = 0) {
        n = _n;
        bit.assign(n + 3, 0);
    }

    void reset() {
        for(int i = 1; i <= n; i++) bit[i] = 0;
    }

    void update(int u, ll x) {
        if(u < 1 || u > n) return;
        for(int i = u; i <= n; i += i & -i) bit[i] += x;
    }

    void rangeupdate(int u, int v, ll x) {
        if(u <= v) {
            update(u, x);
            update(v + 1, -x);
        }
        else {
            update(1, x);
            update(v + 1, -x);
            update(u, x);
            update(n + 1, -x);
        }
    }

    ll get(int u) {
        ll s = 0;
        for(int i = u; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
};

signed main(int argc, char* argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        cin >> o[i];
    }
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    cin >> k;
    for(int i = 1; i <= k; i++) {
        int l, r, x; cin >> l >> r >> x;
        q[i] = {l, r, x};
    }

    for(int i = 1; i <= n; i++) {
        L[i] = 1;
        R[i] = k;
        res[i] = -1;
    }
    for(int i = 1; i <= m; i++) {
        adj[o[i]].push_back(i);
    }

    BIT t(m);
    bool flag = 1;
    while(flag) {
        flag = 0;
        for(int i = 1; i <= n; i++) if(L[i] <= R[i]) {
            int mid = (L[i] + R[i]) / 2;
            qq[mid].push_back(i);
            flag = 1;
        }
        if(!flag) break;
        for(int i = 1; i <= k; i++) {
            auto [l, r, x] = q[i];
            t.rangeupdate(l, r, x);
            while(!qq[i].empty()) {
                int u = qq[i].back();
                qq[i].pop_back();
                for(int j : adj[u]) {
                    sum[u] += t.get(j);
                    if(sum[u] >= p[u]) break;
                }
                if(sum[u] >= p[u]) {
                    res[u] = i;
                    R[u] = i - 1;
                }
                else L[u] = i + 1;
            }
        }
        t.reset();
        for(int i = 1; i <= n; i++) sum[i] = 0;
    }

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

    return 0 ^ 0;
}

• 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