Submission #1185563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185563		nagorn_ph	Meteors (POI11_met)	C++20	100 / 100	5641 ms	64092 KiB

met

#include <iostream>
#include <vector>
#pragma GCC optimize("Ofast,unroll-loops,fast-math,unsafe-math-optimizations")
#pragma GCC target("avx2,popcnt,tune=native")

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;
const int mod = 1e9 + 7;

int n, m, k, l[N], r[N], x[N], y[N], p[N], c[N];
vector <int> a[N], que[N];
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[2 * i] %= mod;
    lazy[2 * i + 1] %= mod;
    seg[i] %= mod;
    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, lazy[i] %= mod, 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];
    seg[i] %= mod;
}
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;
    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;
        }
        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]);
            }
            else {
                update(1, m, 1, x[i], m, c[i]), update(1, m, 1, 1, y[i], c[i]);
            }
            for (auto idx : que[i]) {
                lll sum = 0;
                for (auto j : a[idx]) {
                    lll cal = query(1, m, 1, j);
                    sum += cal;
                    if (sum >= p[idx]) break;
                }
                if (sum >= p[idx]) r[idx] = i - 1;
                else l[idx] = i + 1;
            }
        }
        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:84:59: warning: iteration 1200020 invokes undefined behavior [-Waggressive-loop-optimizations]
   84 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                                                   ~~~~~~~~^~~
met.cpp:84:27: note: within this loop
   84 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                         ~~^~~~~~~~
met.cpp:84:59: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 4800084 bytes into a region of size 4800080 overflows the destination [-Wstringop-overflow=]
   84 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                                                   ~~~~~~~~^~~
met.cpp:18:17: note: destination object 'lazy' of size 4800080
   18 | int seg[4 * N], lazy[4 * N];
      |                 ^~~~
met.cpp:84:49: warning: 'void* __builtin_memset(void*, int, long unsigned int)' writing 4800084 bytes into a region of size 4800080 overflows the destination [-Wstringop-overflow=]
   84 |         for (int i = 0; i <= 4 * N; i++) seg[i] = lazy[i] = 0;
      |                                          ~~~~~~~^~~~~~~~~~~~~
met.cpp:18:5: note: destination object 'seg' of size 4800080
   18 | int 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: 13 / 13
• Subtask 8: 13 / 13