oj.uz

Submission #1104929

# Submission time Handle Problem Language Result Execution time Memory
1104929 2024-10-24T18:41:27 Z Irate Meteors (POI11_met) C++17
100 / 100
 772 ms 28604 KB 
#include<bits/stdc++.h>
using namespace std;
const int mxN = 3e5 + 5;
long long fen[mxN];
vector<int> pos[mxN];
int sectors[mxN], need[mxN], ans[mxN];
int P = -1, n, m, q;
void Update(int pos, int val){
    while(pos < mxN){
        fen[pos] += val;
        pos += (pos & -pos);
    }
}
long long Sum(int pos){
    long long sum = 0;
    while(pos > 0){
        sum += fen[pos];
        pos -= (pos & -pos);
    }
    return sum;
}
struct Query{
    int l, r, a;
} queries[mxN];
void f(int l, int r, vector<int>&exist){
    int mid = (l + r) / 2;
    if(mid == q){
        for(int &sector : exist){
            ans[sector] = -1;       
        }
        return;
    }
    if(l == r){
        for(int &sector : exist){
            ans[sector] = l;
        }
        return;
    }
    while(P + 1 <= mid){
        P++;
        int l = queries[P].l, r = queries[P].r, a = queries[P].a;
        if(l <= r){
            Update(l, a);
            Update(r + 1, -a);
        }
        else{
            Update(l, a);
            Update(1, a);
            Update(r + 1, -a);
        }
    }
    while(P - 1 >= mid){
        int l = queries[P].l, r = queries[P].r, a = queries[P].a;
        if(l <= r){
            Update(l, -a);
            Update(r + 1, a);
        }
        else{
            Update(l, -a);
            Update(1, -a);
            Update(r + 1, a);
        }
        P--;
    }
    vector<int>left, right;
    for(int &sector : exist){
        long long tot = 0;
        for(int &i : pos[sector]){
            tot += Sum(i);
            if(tot >= need[sector]){
                break;
            }
        }
        if(tot >= need[sector]){
            left.push_back(sector);
        }
        else{
            right.push_back(sector);
        }
    }
    f(l, mid, left);
    f(mid + 1, r, right);
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> m >> n;
    for(int i = 1;i <= n;++i){
        cin >> sectors[i];
        pos[sectors[i]].push_back(i);
    }
    vector<int>exist;
    for(int i = 1;i <= m;++i){
        cin >> need[i];
        exist.push_back(i);
    }
    cin >> q;
    for(int i = 0;i < q;++i){
        int l, r, a;
        cin >> l >> r >> a;
        queries[i] = {l, r, a};
    }
    f(0, q, exist);
    for(int i = 1;i <= m;++i){
        if(ans[i] < 0){
            cout << "NIE\n";
        }
        else{
            cout << ans[i] + 1 << '\n';
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 15688 KB Output is correct
2 Correct 89 ms 17348 KB Output is correct
3 Correct 65 ms 15724 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 15440 KB Output is correct
2 Correct 68 ms 15616 KB Output is correct
3 Correct 88 ms 16732 KB Output is correct
4 Correct 17 ms 13904 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 15440 KB Output is correct
2 Correct 95 ms 16972 KB Output is correct
3 Correct 52 ms 15092 KB Output is correct
4 Correct 57 ms 15944 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 15184 KB Output is correct
2 Correct 73 ms 15692 KB Output is correct
3 Correct 50 ms 15184 KB Output is correct
4 Correct 75 ms 16456 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 525 ms 25960 KB Output is correct
2 Correct 331 ms 18008 KB Output is correct
3 Correct 282 ms 14928 KB Output is correct
4 Correct 656 ms 27324 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 545 ms 24128 KB Output is correct
2 Correct 358 ms 18128 KB Output is correct
3 Correct 222 ms 14928 KB Output is correct
4 Correct 772 ms 28604 KB Output is correct