Submission #915724

#	Time	Username	Problem	Language	Result	Execution time	Memory
915724		AndiR	Meteors (POI11_met)	C++14	100 / 100	1744 ms	65536 KiB

met

// Author: Tanasescu Andrei-Rares
// Parallel binary-search approach
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <deque>
#include <iomanip>
#include <vector>
#include <cassert>

#pragma GCC optimize("O3")

#define fi first
#define se second
#define pb push_back
#define pf push_front

using namespace std;

ifstream fin ("meteors.in");
ofstream fout ("meteors.out");

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const ll Nmax=3e5+5, inf=1e9+5;

int n, m, q;
int req[Nmax], sol[Nmax];
vector<int> sect[Nmax], mid[Nmax];
pii bsrange[Nmax];
struct querry{
    int l, r, v;
} Q[Nmax];
ll aib[Nmax];
ll querry(int pos){
    ll sum=0;
    while (pos>0){
        sum+=aib[pos];
        pos-=pos&-pos;
    }
    return sum;
}
inline void __add(int pos, int val){
    while (pos<Nmax){
        aib[pos]+=val;
        pos+=pos&-pos;
    }
}
inline void _add(int l, int r, int v){
    __add(l, v);
    __add(r+1, -v);
}
inline void add(int l, int r, int v){
    if (l<=r)
        _add(l, r, v);
    else{
        _add(l, m, v);
        _add(1, r, v);
    }
}
inline void clear(){
    for (int i=1; i<Nmax; i++)
        aib[i]=0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;
    int nr;
    for (int i=1; i<=m; i++){
        cin>>nr;
        sect[nr].pb(i);
    }
    for (int i=1; i<=n; i++)
        cin>>req[i];
    
    cin>>q;
    for (int i=1; i<=n; i++){
        bsrange[i].fi=1;
        bsrange[i].se=q;
    }
    for (int i=1; i<=q; i++)
        cin>>Q[i].l>>Q[i].r>>Q[i].v;
    // parallel binary-search
    bool ok=1;
    while (ok){
        ok=0;
        for (int i=1; i<=n; i++)
            mid[(bsrange[i].fi+bsrange[i].se)/2].pb(i);
        for (int i=1; i<=q; i++){
            add(Q[i].l, Q[i].r, Q[i].v);
            for (auto stat:mid[i])
                if (bsrange[stat].fi<=bsrange[stat].se){
                    ll sum=0;
                    for (auto pos:sect[stat]){
                        sum+=querry(pos);
                        if (sum>=req[stat])
                            break;
                    }
                    if (sum>=req[stat]){
                        bsrange[stat].se=i-1;
                        sol[stat]=i;
                    }
                    else bsrange[stat].fi=i+1;
                    if (bsrange[stat].fi<=bsrange[stat].se)
                        ok=1;
                }
            mid[i].clear();
        }
        clear();
    }
    for (int i=1; i<=n; i++){
        if (sol[i]==0)
            cout<<"NIE\n";
        else cout<<sol[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