oj.uz

Submission #477553

# Submission time Handle Problem Language Result Execution time Memory
477553 2021-10-02T15:29:21 Z JovanB Meteors (POI11_met) C++17
100 / 100
 1020 ms 38288 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 300000;

int ql[N+5], qr[N+5], cnt[N+5];
int hoce[N+5];
int soln[N+5];

vector <int> vec[N+5];

int qrs, m;
int tr;

ll bit[N+5];

void upd(int x, ll v){
    while(x <= m){
        bit[x] += v;
        x += x & -x;
    }
}

ll query(int x){
    ll res = 0;
    while(x){
        res += bit[x];
        x -= x & - x;
    }
    return res;
}

void dodaj(int tr, int k){
    if(ql[tr] <= qr[tr]){
        upd(qr[tr] + 1, -cnt[tr]*k);
        upd(ql[tr], cnt[tr]*k);
    }
    else{
        upd(qr[tr] + 1, -cnt[tr]*k);
        upd(1, cnt[tr]*k);
        upd(ql[tr], cnt[tr]*k);
    }
}

void resi(int l, int r, vector <int> ask){
    if(ask.empty()) return;
    if(l == r){
        if(r == qrs+1) for(auto c : ask) soln[c] = -1;
        else for(auto c : ask) soln[c] = l;
        return;
    }
    int mid = (l+r)/2;
    while(tr > mid){
        dodaj(tr, -1);
        tr--;
    }
    while(tr < mid){
        tr++;
        dodaj(tr, 1);
    }
    vector <int> v1, v2;
    for(auto h : ask){
        ll x = 0;
        for(auto c : vec[h]){
            x += query(c);
            if(x >= hoce[h]) break;
        }
        if(x >= hoce[h]) v1.push_back(h);
        else v2.push_back(h);
    }
    resi(l, mid, v1);
    resi(mid+1, r, v2);
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n >> m;
    for(int i=1; i<=m; i++){
        int g;
        cin >> g;
        vec[g].push_back(i);
    }
    for(int i=1; i<=n; i++) cin >> hoce[i];
    cin >> qrs;
    for(int i=1; i<=qrs; i++){
        cin >> ql[i] >> qr[i] >> cnt[i];
    }
    vector <int> poc;
    for(int i=1; i<=n; i++) poc.push_back(i);
    resi(1, qrs+1, poc);
    for(int i=1; i<=n; i++){
        if(soln[i] == -1) cout << "NIE\n";
        else cout << soln[i] << "\n";
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7424 KB Output is correct
3 Correct 5 ms 7376 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 9356 KB Output is correct
2 Correct 63 ms 13552 KB Output is correct
3 Correct 70 ms 10488 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 9172 KB Output is correct
2 Correct 69 ms 10288 KB Output is correct
3 Correct 59 ms 12360 KB Output is correct
4 Correct 29 ms 9936 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 9028 KB Output is correct
2 Correct 75 ms 12728 KB Output is correct
3 Correct 25 ms 8528 KB Output is correct
4 Correct 71 ms 10756 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8584 KB Output is correct
2 Correct 62 ms 10344 KB Output is correct
3 Correct 42 ms 9768 KB Output is correct
4 Correct 79 ms 11828 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 27856 KB Output is correct
2 Correct 144 ms 21200 KB Output is correct
3 Correct 97 ms 12604 KB Output is correct
4 Correct 895 ms 34140 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 416 ms 24504 KB Output is correct
2 Correct 189 ms 20208 KB Output is correct
3 Correct 62 ms 13132 KB Output is correct
4 Correct 1020 ms 38288 KB Output is correct