Submission #477553

#	Time	Username	Problem	Language	Result	Execution time	Memory
477553		JovanB	Meteors (POI11_met)	C++17	100 / 100	1020 ms	38288 KiB

met

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13