oj.uz

Submission #797638

# Submission time Handle Problem Language Result Execution time Memory
797638 2023-07-29T17:32:26 Z FEDIKUS Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 3000 ms 40908 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define xx first
#define yy second
#define ff(i,s,f) for(int i=s;i<f;i++)
#define fb(i,s,f) for(int i=(s)-1;i>=f;i--)
#define ffi(i,s,f) for(int i=s;i<=f;i++)
#define fbi(i,s,f) for(int i=s;i>=f;i--)
#define srt(a) sort(a.begin(),a.end());
#define srtg(a,int) sort(a.begin(),a.end(),greater<int>())
#define lb(a,x) lower_bound(a.begin(),a.end(),x)
#define ub(a,x) upper_bound(a.begin(),a.end(),x)
#define fnd(a,x) find(a.begin(),a.end(),x)
#define ios ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

using namespace std;

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

using ti = tuple<int,int,int>;

const int maxn=1e6+10;

int n,q;
int a[maxn];
int inv[maxn];
int veci[maxn];
int segt[4*maxn];
ti upit[maxn];
int res[maxn];

void update(int t,int v,int ind=1,int l=1,int r=n){
    if(l==r){
        segt[ind]=v;
        return;
    }
    int mid=l+(r-l)/2;
    if(t<=mid) update(t,v,2*ind,l,mid);
    else update(t,v,2*ind+1,mid+1,r);
    segt[ind]=segt[2*ind]+segt[2*ind+1];
}

int qry(int tl,int tr,int ind=1,int l=1,int r=n){
    if(tl>tr) return 0;
    if(tl<=l && r<=tr) return segt[ind];
    int mid=l+(r-l)/2;
    int ret=0;
    if(tl<=mid) ret+=qry(tl,tr,2*ind,l,mid);
    if(tr>mid) ret+=qry(tl,tr,2*ind+1,mid+1,r);
    return ret;
}

int pronadji(int x){
    int l=1,r=n;
    int ret=-1;
    while(l<=r){
        int mid=l+(r-l)/2;
        if(qry(1,mid)>=x){
            ret=mid;
            r=mid-1;
        }else l=mid+1;
    }
    assert(ret!=-1);
    return ret;
}

bool pomeri(){
    int lik=pronadji(n/2+1);
    int kraj=inv[lik]+qry(lik,lik)-1;
    int prosli=inv[lik]+n/2+1-qry(1,lik-1)-1;
    if(qry(a[prosli],a[prosli])!=0) return true;
    update(lik,n/2+1-qry(1,lik-1)-1);
    int tren=veci[prosli];
    while(tren<=kraj){
        update(a[prosli],tren-prosli);
        prosli=tren;
        tren=veci[tren];
    }
    update(a[prosli],kraj+1-prosli);
    return false;
}

void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        inv[a[i]]=i;
    }
    for(int i=1;i<=q;i++){
        int t,ind;
        cin>>t>>ind;
        upit[i]={t,ind,i};
    }
    sort(upit+1,upit+q+1);
    stack<int> stek;
    for(int i=n;i>0;i--){
        while(!stek.empty() && a[stek.top()]<a[i]) stek.pop();
        if(stek.empty()) veci[i]=n+1;
        else veci[i]=stek.top();
        stek.push(i);
    }

    int tren=1;
    int prosli=-1;
    while(tren<=n/2){
        if(prosli!=-1){
            update(a[prosli],tren-prosli);
        }
        prosli=tren;
        tren=veci[tren];
    }
    update(a[prosli],n/2+1-prosli);
    
    tren=n/2+1;
    prosli=-1;
    while(tren<=n){
        if(prosli!=-1) update(a[prosli],tren-prosli);
        prosli=tren;
        tren=veci[tren];
    }
    update(a[prosli],n+1-prosli);

    int tu=0;
    while(get<0>(upit[tu])==0){
        res[get<2>(upit[tu])]=a[get<1>(upit[tu])];
        tu++;
    }

    for(int t=1;tu<=q;t++){
        while(tu<=q && t>=get<0>(upit[tu])){
            auto [t,x,ind]=upit[tu];
            
            int gde=pronadji(x);
            int klk=x-qry(1,gde-1)-1;
            assert(inv[gde]+klk<=n && inv[gde]+klk>=0);
            res[ind]=a[inv[gde]+klk];

            tu++;
        }
        if(pomeri()) t=maxn;
    }
    for(int i=1;i<=q;i++){
        cout<<res[i]<<"\n";
    }
}

int main(){
    ios;
    int t=1;
    //cin>>t;
    while(t--) solve();
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 18296 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1385 ms 30676 KB Output is correct
2 Correct 1276 ms 40908 KB Output is correct
3 Correct 1148 ms 32524 KB Output is correct
4 Correct 998 ms 32660 KB Output is correct
5 Correct 1082 ms 33280 KB Output is correct
6 Correct 950 ms 32164 KB Output is correct
7 Correct 1194 ms 40088 KB Output is correct
8 Correct 1168 ms 38408 KB Output is correct
9 Correct 1028 ms 33176 KB Output is correct
10 Correct 1115 ms 37416 KB Output is correct
11 Correct 944 ms 31260 KB Output is correct
12 Correct 914 ms 31260 KB Output is correct
13 Correct 1106 ms 36696 KB Output is correct
14 Correct 966 ms 32244 KB Output is correct
15 Correct 1127 ms 38332 KB Output is correct
16 Correct 18 ms 5204 KB Output is correct
17 Correct 228 ms 35792 KB Output is correct
18 Correct 1102 ms 27396 KB Output is correct
19 Correct 54 ms 10076 KB Output is correct
20 Execution timed out 3070 ms 11276 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 4100 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3079 ms 18296 KB Time limit exceeded
2 Halted 0 ms 0 KB -