oj.uz

Submission #915724

# Submission time Handle Problem Language Result Execution time Memory
915724 2024-01-24T15:49:24 Z AndiR Meteors (POI11_met) C++14
100 / 100
 1744 ms 65536 KB 
// 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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23128 KB Output is correct
2 Correct 8 ms 23132 KB Output is correct
3 Correct 8 ms 23104 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 23128 KB Output is correct
2 Correct 8 ms 23132 KB Output is correct
3 Correct 9 ms 23132 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 24892 KB Output is correct
2 Correct 136 ms 26960 KB Output is correct
3 Correct 100 ms 26432 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 25940 KB Output is correct
2 Correct 112 ms 26176 KB Output is correct
3 Correct 130 ms 26964 KB Output is correct
4 Correct 27 ms 25180 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 25204 KB Output is correct
2 Correct 115 ms 27732 KB Output is correct
3 Correct 117 ms 23816 KB Output is correct
4 Correct 91 ms 26960 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 24408 KB Output is correct
2 Correct 124 ms 26316 KB Output is correct
3 Correct 84 ms 24860 KB Output is correct
4 Correct 126 ms 28244 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 827 ms 43572 KB Output is correct
2 Correct 427 ms 32352 KB Output is correct
3 Correct 612 ms 25952 KB Output is correct
4 Correct 1463 ms 63184 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 880 ms 42312 KB Output is correct
2 Correct 635 ms 30884 KB Output is correct
3 Correct 498 ms 26924 KB Output is correct
4 Correct 1744 ms 65536 KB Output is correct