oj.uz

Submission #1054405

# Submission time Handle Problem Language Result Execution time Memory
1054405 2024-08-12T09:39:50 Z gagik_2007 Abracadabra (CEOI22_abracadabra) C++17
40 / 100
 1096 ms 43968 KB 
#include <bits/stdc++.h>
using namespace std;

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

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=200007;
ll n,m,k;
int a[N];
int d[N];
int ind[N];
bool met[N];
set<int>s;
int curlen=0;
pair<int,int> t[4*N];
vector<pair<int,int>>q;

void build(int v, int tl, int tr){
    if(tl==tr){
        t[v]={a[tl],tl};
    }
    else{
        int tm=(tl+tr)/2;
        build(2*v,tl,tm);
        build(2*v+1,tm+1,tr);
        t[v]=max(t[2*v],t[2*v+1]);
    }
}

pair<int,int> getmax(int v, int tl, int tr, int l, int r){
    if(l>r)return {0,0};
    if(tl==l&&tr==r){
        return t[v];
    }
    else{
        int tm=(tl+tr)/2;
        return max(getmax(2*v,tl,tm,l,min(r,tm)),
            getmax(2*v+1,tm+1,tr,max(tm+1,l),r));
    }
}

void step(){
    // cout<<"step"<<endl;
    while(curlen+d[-(*s.begin())]<=n/2){
        curlen+=d[-(*s.begin())];
        s.erase(s.begin());
    }
    int v=-(*s.begin());
    int i=ind[v];
    int len=d[v];
    // cout<<v<<" "<<i<<" "<<len<<endl;
    int l=ind[v]-d[v]+1;
    int r=n/2-curlen+l-1;
    d[v]=i-r;
    // cout<<l<<" "<<r<<endl;
    while(l<=r){
        pair<int,int>e=getmax(1,0,n-1,l,r);
        int mx=e.ff;
        int mxi=e.ss;
        int newlen=mxi-l+1;
        d[mx]=newlen;
        ind[mx]=mxi;
        s.insert(-mx);
        l=mxi+1;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("Ainput.txt","r",stdin);
    // freopen("Aoutput.txt","w",stdout);
    cin>>n>>m;
    for(int i=0;i<n;i++){
        cin>>a[n-i-1];
    }
    build(1,0,n-1);
    int lsti=-1;
    int mx=n;
    int i=0;
    while(i!=n){
        while(i!=n&&a[i]<mx){
            met[a[i]]=true;
            i++;
        }
        d[mx]=i-lsti;
        ind[mx]=i;
        s.insert(-mx);
        met[mx]=true;
        while(met[mx]){
            mx--;
        }
        lsti=i;
        i++;
    }
    int t=0;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y;
        y--;
        q.push_back({x,y});
        t=x;
    }
    for(int i=0;i<min(t*1ll,n*5);i++){
        step();
    }
    vector<int>ans;
    for(int i=n;i>=1;i--){
        if(d[i]!=0){
            // cout<<i<<": "<<ind[i]<<", "<<d[i]<<endl;
            for(int j=ind[i]-d[i]+1;j<=ind[i];j++){
                ans.push_back(a[j]);
            }
        }
    }
    // cout<<endl;
    for(int i=0;i<m;i++){
        cout<<ans[n-q[i].ss-1]<<endl;
    }
}

Compilation message

Main.cpp: In function 'void step()':
Main.cpp:58:9: warning: unused variable 'len' [-Wunused-variable]
   58 |     int len=d[v];
      |         ^~~

Subtask #1
0 / 10.0

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

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1068 ms 39776 KB Output is correct
2 Correct 1096 ms 43968 KB Output is correct
3 Correct 920 ms 34632 KB Output is correct
4 Correct 773 ms 32384 KB Output is correct
5 Correct 872 ms 33624 KB Output is correct
6 Correct 746 ms 35256 KB Output is correct
7 Correct 943 ms 39792 KB Output is correct
8 Correct 1008 ms 36532 KB Output is correct
9 Correct 799 ms 35156 KB Output is correct
10 Correct 971 ms 34936 KB Output is correct
11 Correct 734 ms 31688 KB Output is correct
12 Correct 739 ms 32096 KB Output is correct
13 Correct 888 ms 35640 KB Output is correct
14 Correct 757 ms 32948 KB Output is correct
15 Correct 962 ms 37316 KB Output is correct
16 Correct 13 ms 11488 KB Output is correct
17 Correct 896 ms 42568 KB Output is correct
18 Correct 716 ms 29416 KB Output is correct
19 Correct 193 ms 16544 KB Output is correct
20 Correct 193 ms 16128 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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