Submission #824128

#	Time	Username	Problem	Language	Result	Execution time	Memory
824128		kwongweng	Abracadabra (CEOI22_abracadabra)	C++17	0 / 100	245 ms	33416 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second

struct segtree{
  int sz; vi sm;
  void init(int n){
    sz=n; sm.assign(4*n,0);
  }
  void update(int v, int tl, int tr, int pos, int val){
    if (tl==tr) {sm[v]=val; return;}
    int tm=(tl+tr)/2;
    if (pos<=tm) update(2*v,tl,tm,pos,val);
    else update(2*v+1,tm+1,tr,pos,val);
    sm[v]=sm[2*v]+sm[2*v+1];
  }
  void update(int pos, int val) {update(1,0,sz-1,pos,val);}
  ii get(int v, int tl, int tr, int val){
    if (tl==tr) return {tl,val};
    int tm=(tl+tr)/2;
    if (sm[2*v]<val) return get(2*v+1,tm+1,tr,val-sm[2*v]);
    return get(2*v,tl,tm,val);
  }
  ii get(int val){return get(1,0,sz-1,val);}
};

struct que{
  int id, pos, t;
};

void solve(){
  int n,q; cin>>n>>q;
  vi a(n); FOR(i,0,n){ cin>>a[i]; a[i]--;}
  vi pos(n); FOR(i,0,n) pos[a[i]]=i;
  vi sz(n);
  vector<que> Q[n]; vi ans(q);
  FOR(i,0,q){
    que qr; cin>>qr.t>>qr.pos; qr.id=i; qr.pos--;
    if (qr.t==0){
      ans[i]=a[qr.pos]; continue;
    }
    if (qr.t>=n) qr.t=n-1;
    Q[qr.t].pb(qr);
  }
  segtree st; st.init(n);
  vi used(n);
  ROF(i,n-1,0){
    if (used[i]) continue;
    int L = pos[i];
    if (L < n/2){
      int cnt=0;
      while (L < n/2){
        if (used[a[L]]) break;
        cnt++; used[a[L]]=1; L++;
      }
      st.update(i,cnt); sz[i]=cnt;
      //cout<<i<<" "<<cnt<<'\n';
    }else{
      int cnt=0;
      while (L < n){
        if (used[a[L]]) break;
        cnt++; used[a[L]]=1; L++;
      }
      st.update(i,cnt); sz[i]=cnt;
      //cout<<i<<" "<<cnt<<'\n';
    }
  }
  FOR(i,1,n){
    for (que qr : Q[i]){
      ii val = st.get(qr.pos+1);
      ans[qr.id] = a[pos[val.fi]+val.se-1];
    }
    ii val = st.get(n/2+1);
    if (val.se == 1) continue;
    int posi = a[pos[val.fi]+val.se-1];
    st.update(posi, sz[val.fi]-(val.se-1));
    st.update(val.fi, val.se-1); sz[val.fi]=val.se-1;
  }
  FOR(i,0,q) cout<<ans[i]+1<<"\n";
}

int main(){
	//MOD=MOD1;
    ios::sync_with_stdio(false);
    if (fopen("input.txt", "r")) {
		freopen("input.txt", "r", stdin);
    	freopen("output.txt", "w", stdout);
	}
    int TC = 1;
    //cin >> TC; 
    FOR(i, 1, TC+1){
        //cout << "Case #" << i << ": ";
        solve();
    }
	
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:97:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |   freopen("input.txt", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:98:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |      freopen("output.txt", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25