oj.uz

Submission #915699

# Submission time Handle Problem Language Result Execution time Memory
915699 2024-01-24T14:55:22 Z AndiR Meteors (POI11_met) C++11
37 / 100
 844 ms 43492 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 ("");
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.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 70 ms 24748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 25952 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 25168 KB Output is correct
2 Correct 134 ms 27444 KB Output is correct
3 Correct 118 ms 23888 KB Output is correct
4 Correct 92 ms 26852 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 24404 KB Output is correct
2 Correct 119 ms 26152 KB Output is correct
3 Correct 72 ms 24660 KB Output is correct
4 Incorrect 122 ms 27984 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 820 ms 43492 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 844 ms 42256 KB Output isn't correct
2 Halted 0 ms 0 KB -