oj.uz

Submission #824151

# Submission time Handle Problem Language Result Execution time Memory
824151 2023-08-13T15:49:26 Z kwongweng Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 277 ms 46760 KB 
#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];
    sz[posi]=sz[val.fi]-(val.se-1);
    st.update(posi, sz[posi]);
    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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 23144 KB Output is correct
2 Correct 211 ms 28848 KB Output is correct
3 Correct 202 ms 28272 KB Output is correct
4 Correct 167 ms 25320 KB Output is correct
5 Correct 187 ms 31348 KB Output is correct
6 Correct 175 ms 31548 KB Output is correct
7 Incorrect 191 ms 32848 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 33400 KB Output is correct
2 Correct 277 ms 46760 KB Output is correct
3 Correct 215 ms 38764 KB Output is correct
4 Correct 202 ms 39036 KB Output is correct
5 Correct 214 ms 39824 KB Output is correct
6 Correct 198 ms 38296 KB Output is correct
7 Incorrect 263 ms 46500 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8944 KB Output is correct
2 Correct 51 ms 10444 KB Output is correct
3 Correct 53 ms 10184 KB Output is correct
4 Correct 44 ms 10064 KB Output is correct
5 Correct 47 ms 10444 KB Output is correct
6 Correct 38 ms 10060 KB Output is correct
7 Incorrect 43 ms 10392 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 23144 KB Output is correct
2 Correct 211 ms 28848 KB Output is correct
3 Correct 202 ms 28272 KB Output is correct
4 Correct 167 ms 25320 KB Output is correct
5 Correct 187 ms 31348 KB Output is correct
6 Correct 175 ms 31548 KB Output is correct
7 Incorrect 191 ms 32848 KB Output isn't correct
8 Halted 0 ms 0 KB -