oj.uz

Submission #542291

# Submission time Handle Problem Language Result Execution time Memory
542291 2022-03-26T04:57:02 Z SirCovidThe19th Meteors (POI11_met) C++17
100 / 100
 1398 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std; 

#define FOR(i, x, y) for (int i = x; i < y; i++)
#define ll long long

const int mx = 3e5 + 5;

int n, m, q, targ[mx], ans[mx]; ll bit[mx]; vector<int> pos[mx]; array<int, 3> Q[mx]; 

void upd(int i, int val){
    for (; i < mx; i += i & (-i)) bit[i] += val;
}
void rupd(int l, int r, int val){
    if (l <= r) upd(l, val), upd(r + 1, -val);
    else rupd(l, m, val), rupd(1, r, val);
}
ll qry(int i){
    ll ret = 0;
    for (; i > 0; i -= i & (-i)) ret += bit[i], ret = min(ret, (ll)1e9); //avoid overflow
    return ret;
}
void pbs(int l, int r, vector<pair<int, ll>> states){
    if (l == r or states.empty()){
        for (auto [i, _] : states) ans[i] = l;
        return;
    }
    int mid = (l + r) / 2; vector<pair<int, ll>> L, R;

    FOR(i, l, mid + 1) rupd(Q[i][0], Q[i][1], Q[i][2]);
    for (auto [i, initVal] : states){
        ll sm = initVal;
        for (int p : pos[i]) sm += qry(p);
        (sm >= targ[i]) ? L.push_back({i, initVal}) : R.push_back({i, sm});
    }
    FOR(i, l, mid + 1) rupd(Q[i][0], Q[i][1], -Q[i][2]);

    pbs(l, mid, L); pbs(mid + 1, r, R);
}

int main(){
    cin >> n >> m;
    FOR(i, 1, m + 1){ int x; cin >> x; pos[x].push_back(i); }
    FOR(i, 1, n + 1) cin >> targ[i];
    cin >> q;
    FOR(i, 1, q + 1) cin >> Q[i][0] >> Q[i][1] >> Q[i][2];

    vector<pair<int, ll>> all;
    FOR(i, 1, n + 1) all.push_back({i, 0});
    pbs(1, q + 1, all);
    FOR(i, 1, n + 1) cout<<(ans[i] <= q ? to_string(ans[i]) : "NIE")<<"\n";
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 7380 KB Output is correct
2 Correct 6 ms 7508 KB Output is correct
3 Correct 6 ms 7380 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7468 KB Output is correct
2 Correct 6 ms 7508 KB Output is correct
3 Correct 7 ms 7636 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 12096 KB Output is correct
2 Correct 136 ms 23072 KB Output is correct
3 Correct 126 ms 11512 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 11076 KB Output is correct
2 Correct 134 ms 10964 KB Output is correct
3 Correct 114 ms 18228 KB Output is correct
4 Correct 43 ms 13156 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 10700 KB Output is correct
2 Correct 154 ms 19808 KB Output is correct
3 Correct 68 ms 8536 KB Output is correct
4 Correct 125 ms 12368 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9676 KB Output is correct
2 Correct 146 ms 11320 KB Output is correct
3 Correct 87 ms 10032 KB Output is correct
4 Correct 157 ms 15352 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 737 ms 65536 KB Output is correct
2 Correct 460 ms 21204 KB Output is correct
3 Correct 373 ms 12764 KB Output is correct
4 Correct 1256 ms 47180 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 671 ms 53252 KB Output is correct
2 Correct 467 ms 20284 KB Output is correct
3 Correct 204 ms 13460 KB Output is correct
4 Correct 1398 ms 62008 KB Output is correct