Submission #1185533

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185533		nagorn_ph	Meteors (POI11_met)	C++20	74 / 100	5098 ms	73484 KiB

met

#include <bits/stdc++.h>

using namespace std;

#define lll long long
#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], p[N], c[N];
vector <int> a[N], que[N];
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];
}
lll 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);
}

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]) {
    //         update(1, m, 1, x[i], y[i], c[i]);
    //         // cout << i << ": " << "UPDATE 1\n";
    //     }
    //     else {
    //         update(1, m, 1, x[i], m, c[i]), 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 << 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]) {
                update(1, m, 1, x[i], y[i], c[i]);
                // cout << i << ": " << "UPDATE 1\n";
            }
            else {
                update(1, m, 1, x[i], m, c[i]), 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 = 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++) seg[i] = 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:102:59: warning: iteration 1200020 invokes undefined behavior [-Waggressive-loop-optimizations]
  102 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                                                   ~~~~~~~~^~~
met.cpp:102:27: note: within this loop
  102 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                         ~~^~~~~~~~
met.cpp:102:59: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 9600168 bytes into a region of size 9600160 overflows the destination [-Wstringop-overflow=]
  102 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                                                   ~~~~~~~~^~~
met.cpp:14:17: note: destination object 'lazy' of size 9600160
   14 | lll seg[4 * N], lazy[4 * N];
      |                 ^~~~
met.cpp:102:49: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 9600168 bytes into a region of size 9600160 overflows the destination [-Wstringop-overflow=]
  102 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                                          ~~~~~~~^~~~~~~~~~~~~
met.cpp:14:5: note: destination object 'seg' of size 9600160
   14 | lll seg[4 * N], lazy[4 * 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