oj.uz

Submission #824156

# Submission time Handle Problem Language Result Execution time Memory
824156 2023-08-13T16:00:43 Z kwongweng Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 273 ms 33492 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>=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]; 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;
    int posi = a[pos[val.fi]+val.se-1];
    sz[posi]=sz[val.fi]-(val.se-1);
    sz[val.fi]=val.se-1;
    st.update(posi, sz[posi]);
    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

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

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 23244 KB Output is correct
2 Correct 215 ms 21592 KB Output is correct
3 Correct 198 ms 21096 KB Output is correct
4 Correct 167 ms 19652 KB Output is correct
5 Correct 184 ms 23772 KB Output is correct
6 Correct 166 ms 24960 KB Output is correct
7 Incorrect 202 ms 25548 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 33492 KB Output is correct
2 Correct 261 ms 33312 KB Output is correct
3 Correct 213 ms 28088 KB Output is correct
4 Correct 200 ms 28296 KB Output is correct
5 Correct 227 ms 28820 KB Output is correct
6 Correct 196 ms 27840 KB Output is correct
7 Incorrect 237 ms 33212 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 8944 KB Output is correct
2 Correct 52 ms 8780 KB Output is correct
3 Correct 54 ms 8492 KB Output is correct
4 Correct 37 ms 8524 KB Output is correct
5 Correct 47 ms 8784 KB Output is correct
6 Correct 38 ms 8396 KB Output is correct
7 Incorrect 44 ms 8720 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 23244 KB Output is correct
2 Correct 215 ms 21592 KB Output is correct
3 Correct 198 ms 21096 KB Output is correct
4 Correct 167 ms 19652 KB Output is correct
5 Correct 184 ms 23772 KB Output is correct
6 Correct 166 ms 24960 KB Output is correct
7 Incorrect 202 ms 25548 KB Output isn't correct
8 Halted 0 ms 0 KB -