Submission #1185511

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185511		nagorn_ph	Meteors (POI11_met)	C++20	74 / 100	3756 ms	64996 KiB

met

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ordered_set <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define ordered_multiset <int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update>

#define int long long
#define double long double
#define pii pair <int, int>
#define tiii tuple <int, int, int>
#define emb emplace_back
#define all(a) a.begin(), a.end()
#define iShowSpeed cin.tie(NULL)->sync_with_stdio(false)

const int mod = 1e9 + 7;
const int inf = 1e18;
const int N = 3e5 + 5;

int n, m, k, p[N], l[N], r[N], x[N], y[N], c[N], ans[N];
vector <int> a[N], que[N];

struct {
    int seg[4 * N], lazy[4 * N];
    void push(int l, int r, int i){
        seg[i] += lazy[i];
        if (l != r) lazy[2 * i] += lazy[i], lazy[2 * i + 1] += lazy[i];
        lazy[i] = 0;
    }
    void update(int l, int r, int i, int ll, int rr, int val) {
        push(l, r, i);
        if (r < ll || l > rr) return;
        if (l >= ll && r <= rr) return lazy[i] += val, push(l, r, i), void();
        int mid = (l + r) / 2;
        update(l, mid, 2 * i, ll, rr, val);
        update(mid + 1, r, 2 * i + 1, ll, rr, val);
        seg[i] += seg[2 * i] + seg[2 * i + 1];
    }
    int query(int l, int r, int i, int idx) {
        push(l, r, i);
        if (l == r) return seg[i];
        int mid = (l + r) / 2;
        if (idx <= mid) return query(l, mid, 2 * i, idx);
        else return query(mid + 1, r, 2 * i + 1, idx);
    }
} segtree;

int32_t main(){
    iShowSpeed;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int o; cin >> o;
        a[o].emb(i);
    }
    for (int i = 1; i <= n; i++) cin >> p[i];
    cin >> k;
    for (int i = 1; i <= k; i++) {
        cin >> x[i] >> y[i] >> c[i];
    }
    for (int i = 1; i <= n; i++) l[i] = 1, r[i] = k;
    // debug begin
    // for (int i = 1; i <= k; i++) {
    //     if (x[i] <= y[i]) {
    //         segtree.update(1, m, 1, x[i], y[i], c[i]);
    //         // cout << i << ": " << "UPDATE 1\n";
    //     }
    //     else {
    //         segtree.update(1, m, 1, x[i], m, c[i]), segtree.update(1, m, 1, 1, y[i], c[i]);
    //         // cout << i << ": " << "UPDATE 2\n";
    //         // cout << x[i] << ", " << m << " | " << 1 << ", " << y[i] << "\n";
    //     }
    //     cout << i << ": ";
    //     for (int j = 1; j <= m; j++) cout << segtree.query(1, m, 1, j) << " ";
    //     cout << "\n";
    // }
    // debug complete
    while (1) {
        bool can = true;
        for (int i = 0; i <= k; i++) que[i].clear();
        for (int i = 1; i <= n; i++) {
            if (l[i] <= r[i]) que[(l[i] + r[i]) / 2].emb(i), can = false;
            // cout << l[i] << " " << r[i] << "\n";
        }
        if (can) break;
        for (int i = 1; i <= k; i++) {
            if (x[i] <= y[i]) {
                segtree.update(1, m, 1, x[i], y[i], c[i]);
                // cout << i << ": " << "UPDATE 1\n";
            }
            else {
                segtree.update(1, m, 1, x[i], m, c[i]), segtree.update(1, m, 1, 1, y[i], c[i]);
                // cout << i << ": " << "UPDATE 2\n";
                // cout << x[i] << ", " << m << " | " << 1 << ", " << y[i] << "\n";
            }
            for (auto idx : que[i]) {
                // cout << i << ":: ";
                // cout << idx << ": | ";
                // cout << l[idx] << " " << r[idx] << ": " << i << ": ";
                int sum = 0;
                for (auto j : a[idx]) {
                    int cal = segtree.query(1, m, 1, j);
                    // cout << j << ", " << cal << " | ";
                    sum += cal;
                }
                // cout << sum << "\n";
                if (sum >= p[idx]) r[idx] = i - 1, ans[idx] = i;
                else l[idx] = i + 1;
                // cout << l[idx] << " " << r[idx] << "\n";
            }
        }
        for (int i = 0; i < 4 * N; i++) segtree.seg[i] = segtree.lazy[i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        if (ans[i] == 0) cout << "NIE\n";
        else cout << ans[i] << "\n";
    }
}

• 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