Submission #915699

#	Time	Username	Problem	Language	Result	Execution time	Memory
915699		AndiR	Meteors (POI11_met)	C++11	37 / 100	844 ms	43492 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 ("");
ofstream fout ("");

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
    while (bsrange[1].fi<=bsrange[1].se){
        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]){
                ll sum=0;
                bool ovr=0;
                for (auto pos:sect[stat]){
                    sum+=querry(pos);
                    if (sum>inf)
                        ovr=1;
                }
                int mij=(bsrange[stat].fi+bsrange[stat].se)/2;
                if (ovr || sum>=req[stat]){
                    bsrange[stat].se=mij-1;
                    sol[stat]=mij;
                }
                else bsrange[stat].fi=mij+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: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 13 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13