oj.uz

Submission #854599

# Submission time Handle Problem Language Result Execution time Memory
854599 2023-09-28T06:40:34 Z dreamoon Meteors (POI11_met) C++17
100 / 100
 1318 ms 41300 KB 
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
using LL = long long;
const int MAX_V = 300001;
int p[MAX_V];
int l[MAX_V], r[MAX_V], a[MAX_V];
vector<int> pos[MAX_V];
LL bit[MAX_V];
void bit_clear() {
    memset(bit, 0, sizeof(bit));
}
void bit_ins(int x, int v) {
    for(; x < MAX_V; x += x & -x) {
        bit[x] += v;
    }
}
LL bit_query(int x) {
    LL res = 0;
    for(; x; x -= x & -x) {
        res += bit[x];
    }
    return res;
}
void solve() {
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int o;
        cin >> o;
        pos[o].push_back(i);
    }
    for(int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    int k;
    cin >> k;
    for(int i = 1; i <= k; i++) {
        cin >> l[i] >> r[i] >> a[i];
    }
    queue<tuple<int, int, vector<int>>> queries;
    {
        vector<int> ids;
        for(int i = 1; i <= n; i++) {
            ids.push_back(i);
        }
        queries.push({1, k + 1, ids});
    }
    int ptr = 0;
    vector<int> ans(n + 1);
    while(!queries.empty()) {
        auto [low, hi, ids] = queries.front();
        queries.pop();
        if(low == hi) {
            for(int id: ids) {
                ans[id] = low;
            }
            continue;
        }
        int mid = low + (hi - low) / 2;
        if(mid < ptr) {
            bit_clear();
            ptr = 0;
        }
        while(ptr < mid) {
            ptr++;
            bit_ins(l[ptr], a[ptr]);
            bit_ins(r[ptr] + 1, -a[ptr]);
            if(r[ptr] < l[ptr]) {
                bit_ins(1, a[ptr]);
            }
        }
        vector<int> small_id, big_id;
        for(int id: ids) {
            long long need = p[id];
            for(int p: pos[id]) {
                need -= bit_query(p);
                if(need <= 0) break;
            }
            if(need <= 0) {
                small_id.push_back(id);
            } else {
                big_id.push_back(id);
            }
        }
        if(!small_id.empty()) {
            queries.push({low, mid, small_id});
        }
        if(!big_id.empty()) {
            queries.push({mid + 1, hi, big_id});
        }
    }
    for(int i = 1; i <= n; i++) {
        if(ans[i] > k) {
            cout << "NIE\n";
        }
        else {
            cout << ans[i] << "\n";
        }
    }
}
int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13144 KB Output is correct
2 Correct 3 ms 12892 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 13356 KB Output is correct
2 Correct 104 ms 14140 KB Output is correct
3 Correct 75 ms 14152 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13908 KB Output is correct
2 Correct 93 ms 13848 KB Output is correct
3 Correct 99 ms 14236 KB Output is correct
4 Correct 20 ms 13876 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 13648 KB Output is correct
2 Correct 137 ms 14680 KB Output is correct
3 Correct 41 ms 12892 KB Output is correct
4 Correct 78 ms 14388 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 13144 KB Output is correct
2 Correct 100 ms 14008 KB Output is correct
3 Correct 61 ms 13392 KB Output is correct
4 Correct 107 ms 14956 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 567 ms 19628 KB Output is correct
2 Correct 102 ms 14688 KB Output is correct
3 Correct 313 ms 15440 KB Output is correct
4 Correct 1040 ms 39484 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 538 ms 19100 KB Output is correct
2 Correct 451 ms 14804 KB Output is correct
3 Correct 59 ms 16340 KB Output is correct
4 Correct 1318 ms 41300 KB Output is correct