Submission #1054392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054392		gagik_2007	Prize (CEOI22_prize)	C++17	0 / 100	3 ms	4548 KiB

Main

#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 (stderr)

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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 19
• Subtask 4: 0 / 22
• Subtask 5: 0 / 24