Submission #1185517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185517		nagorn_ph	Meteors (POI11_met)	C++20	74 / 100	3846 ms	51744 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 lll 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 N = 3e5 + 5;

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

struct {
    lll 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;

int 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 << ": ";
                lll sum = 0;
                for (auto j : a[idx]) {
                    lll cal = segtree.query(1, m, 1, j);
                    // cout << j << ", " << cal << " | ";
                    sum += cal;
                    if (sum >= p[idx]) break;
                }
                // cout << sum << "\n";
                if (sum >= p[idx]) r[idx] = i - 1;
                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 (l[i] > k) cout << "NIE\n";
        else cout << l[i] << "\n";
    }
}

Compilation message (stderr)

met.cpp: In function 'int main()':
met.cpp:114:75: warning: iteration 1200020 invokes undefined behavior [-Waggressive-loop-optimizations]
  114 |         for (int i = 0; i <= 4 * N; i++) segtree.seg[i] = segtree.lazy[i] = 0;
      |                                                           ~~~~~~~~~~~~~~~~^~~
met.cpp:114:27: note: within this loop
  114 |         for (int i = 0; i <= 4 * N; i++) segtree.seg[i] = segtree.lazy[i] = 0;
      |                         ~~^~~~~~~~
met.cpp:114:75: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 9600168 bytes into a region of size 9600160 overflows the destination [-Wstringop-overflow=]
  114 |         for (int i = 0; i <= 4 * N; i++) segtree.seg[i] = segtree.lazy[i] = 0;
      |                                                           ~~~~~~~~~~~~~~~~^~~
met.cpp:48:3: note: at offset 9600160 into destination object 'segtree' of size 19200320
   48 | } segtree;
      |   ^~~~~~~

• 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