Submission #824368

#	Time	Username	Problem	Language	Result	Execution time	Memory
824368		kwongweng	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	738 ms	45772 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

/*Decompose the array into blocks such that:
Leftmost value of block is max in the block
the values of leftmost of each block is strictly increasing
Each swap simply decompose the block containing position n/2, n/2+1
(i.e. a "cut" between n/2 and n/2+1)
Then the blocks will be sorted based on leftmost value.
The structure of the blocks can be maintained using segtree*/

/*segtree used to find the position & maintain the blocks
sm[v] (with tl==tr) stores the number of elements in the block with leftmost value tl.

*/ 
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);}
};

//segtree2 is range maximum, returns index with max value.
struct segtree2{
  int sz; vi mx, a;
  void init(int n, vi A){
    sz=n; mx.assign(4*n,-1); a=A;
  }
  void build(int v, int tl, int tr){
    if (tl==tr){mx[v]=tl; return;}
    int tm=(tl+tr)/2;
    build(2*v,tl,tm); build(2*v+1,tm+1,tr);
    if (a[mx[2*v]]>a[mx[2*v+1]]) mx[v]=mx[2*v];
    else mx[v]=mx[2*v+1];
  }
  int get(int v, int tl, int tr, int l, int r){
    if (tl==l && tr==r) return mx[v];
    if (l>r) return -1;
    int tm=(tl+tr)/2;
    int L=get(2*v,tl,tm,l,min(r,tm)); int R=get(2*v+1,tm+1,tr,max(l,tm+1),r);
    if (L==-1) return R;
    if (R==-1) return L;
    if (a[L]<a[R]) return R;
    return L;
  }
  int get(int l, int r){return get(1,0,sz-1,l,r);}
};

//offline query, sort the query in increasing order of t-value (# swaps)
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]--;}
  segtree2 st2; st2.init(n,a); st2.build(1,0,n-1);
  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>=n) qr.t=n-1;
    Q[qr.t].pb(qr);
  }
  segtree st; st.init(n);
  vi used(n); // decompose the array
  ROF(i,n-1,0){
    if (used[i]) continue;
    int L = pos[i]; 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,0,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;
    // there is block containing the middle 2 positions, decompose this block.
    int L=pos[val.fi]+val.se-1, R=pos[val.fi]+sz[val.fi]-1;
    while(st2.get(L,R) != -1){
      int mx = st2.get(L,R); 
      sz[a[mx]]=R-mx+1; st.update(a[mx],sz[a[mx]]);
      R=mx-1; 
    }
    sz[val.fi]=val.se-1; st.update(val.fi, sz[val.fi]);
  }
  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:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:129:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |      freopen("output.txt", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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