oj.uz

Submission #854597

# Submission time Handle Problem Language Result Execution time Memory
854597 2023-09-28T06:34:50 Z dreamoon Meteors (POI11_met) C++17
74 / 100
 645 ms 27472 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) {
    int 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 12776 KB Output is correct
3 Correct 4 ms 12888 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 14200 KB Output is correct
2 Correct 111 ms 15344 KB Output is correct
3 Correct 81 ms 15180 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 14904 KB Output is correct
2 Correct 97 ms 14984 KB Output is correct
3 Correct 105 ms 15604 KB Output is correct
4 Correct 22 ms 14280 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 14260 KB Output is correct
2 Correct 123 ms 16076 KB Output is correct
3 Correct 41 ms 13572 KB Output is correct
4 Correct 83 ms 15464 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14424 KB Output is correct
2 Correct 103 ms 15204 KB Output is correct
3 Correct 63 ms 14428 KB Output is correct
4 Correct 113 ms 16332 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 27472 KB Output is correct
2 Incorrect 525 ms 22516 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 26920 KB Output is correct
2 Incorrect 473 ms 20872 KB Output isn't correct
3 Halted 0 ms 0 KB -