Submission #1011913

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1011913	2024-07-01T10:58:36 Z	atom	Meteors (POI11_met)	C++17	100 / 100	902 ms	41092 KB

#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif
 
const int N = 3e5 + 5;
 
struct FenwickTree {
    int n;
    vector <ll> f;
    void init(int _n) {
        n = _n;
        f.resize(n + 5, 0);  
    } 
 
    void modify(int x, int val) {
        for (; x <= n; x += x & -x) 
            f[x] += val;
    }
    void upd(int l, int r, int val) {
        if (l <= r) {
            modify(l, val);
            modify(r + 1, -val); 
        }
        else {
            upd(1, r, val);
            upd(l, n + 1, val);
        }
 
    }
    ll qry(int x) {
        ll sum = 0;
        for (; x; x -= x & -x)
            sum += f[x];
        return sum;
    }
} bit;
 
vector <int> adj[N];
vector <int> qs[N];
int ans[N];
ll tar[N];
 
 
void dnc(int l, int r, vector <int>& cand) {
    if (l == r) {
        debug(l, r, cand);
        for (int x : cand) ans[x] = l;
        return;
    }
 
    int m = (l + r) / 2;
 
    vector <int> L, R;
    for (int i = l; i <= m; ++i) {
        auto x = qs[i];
        bit.upd(x[0], x[1], x[2]);
    }
 
    vector <int> done, undone;
    for (auto x : cand) {
        ull sum = 0;
        for (int y : adj[x]) sum += (ull) bit.qry(y);
        if (sum >= (ull) tar[x]) {
            done.push_back(x);
        }
        else {
            tar[x] -= sum;
            undone.push_back(x);
        }
    }
 
    // reroll change as we no longer able to process
    for (int i = l; i <= m; ++i) {
        auto x = qs[i];
        bit.upd(x[0], x[1], -x[2]);
    }
 
    dnc(l, m, done);
    dnc(m + 1, r, undone);
}
 
int n, m;
int q;
 
signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    
    #ifdef JASPER
        freopen("in1", "r", stdin);
    #endif
 
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x; cin >> x;
        adj[x].push_back(i);
    }
    for (int i = 1; i <= n; ++i) 
        cin >> tar[i];
    
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        int l, r, c;
        cin >> l >> r >> c;
        qs[i] = {l, r, c};
    }
    qs[q + 1] = {0, 0, 0};
 
    vector <int> cand(n);
    iota(cand.begin(), cand.end(), 1);
 
    bit.init(m);
    
    dnc(1, q + 1, cand);
    for (int i = 1; i <= n; ++i) {
        if (ans[i] == q + 1) cout << "NIE\n";
        else cout << ans[i] << "\n";
    }
    
    return 0;
}

Compilation message

met.cpp: In function 'void dnc(int, int, std::vector<int>&)':
met.cpp:10:20: warning: statement has no effect [-Wunused-value]
   10 | #define debug(...) 166
      |                    ^~~
met.cpp:54:9: note: in expansion of macro 'debug'
   54 |         debug(l, r, cand);
      |         ^~~~~

Subtask #1
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	14428 KB	Output is correct
2	Correct	5 ms	14428 KB	Output is correct
3	Correct	6 ms	15708 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	15708 KB	Output is correct
2	Correct	5 ms	15708 KB	Output is correct
3	Correct	5 ms	15708 KB	Output is correct

Subtask #3
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	18468 KB	Output is correct
2	Correct	85 ms	20304 KB	Output is correct
3	Correct	67 ms	18768 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	61 ms	18516 KB	Output is correct
2	Correct	72 ms	18512 KB	Output is correct
3	Correct	79 ms	19532 KB	Output is correct
4	Correct	20 ms	17496 KB	Output is correct

Subtask #5
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	18268 KB	Output is correct
2	Correct	59 ms	19792 KB	Output is correct
3	Correct	43 ms	17244 KB	Output is correct
4	Correct	63 ms	18772 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	66 ms	18012 KB	Output is correct
2	Correct	72 ms	18512 KB	Output is correct
3	Correct	55 ms	18012 KB	Output is correct
4	Correct	77 ms	19536 KB	Output is correct

Subtask #7
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	697 ms	37204 KB	Output is correct
2	Correct	509 ms	28748 KB	Output is correct
3	Correct	204 ms	23684 KB	Output is correct
4	Correct	687 ms	38700 KB	Output is correct

Subtask #8
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	691 ms	35004 KB	Output is correct
2	Correct	516 ms	28756 KB	Output is correct
3	Correct	168 ms	22104 KB	Output is correct
4	Correct	902 ms	41092 KB	Output is correct