Submission #865593

#TimeUsernameProblemLanguageResultExecution timeMemory
865593mychecksedadAbracadabra (CEOI22_abracadabra)C++17
0 / 100
321 ms38184 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> using namespace std; #define ll long long int #define MOD (1000000000+7) #define MOD1 (998244353) #define pb push_back #define all(x) x.begin(), x.end() #define en cout << '\n' const int N = 1e6+100, M = 1e5+10, K = 52, MX = 30; int n, q, ans[N], T[N], to[N], posarray[N]; array<int, 2> pos[N]; vector<array<int, 3>> Q; vector<int> a; vector<bool> active; void build(int l, int r, int k){ if(l == r){ if(active[l]) T[k] = pos[l][1] - pos[l][0] + 1; else T[k] = 0; return; } int m = l+r>>1; build(l, m, k<<1); build(m+1, r, k<<1|1); T[k] = T[k<<1] + T[k<<1|1]; } array<int, 3> get(int l, int r, int p, int k){ if(l == r){ return {l, a[pos[l][0] + p - 1], pos[l][1] - pos[l][0] + 1}; } int m = l+r>>1; if(T[k<<1] >= p){ return get(l, m, p, k<<1); } return get(m+1, r, p - T[k<<1], k<<1|1); } void update(int l, int r, int p, int k, int val){ if(l == r){ T[k] = val; pos[l] = {posarray[l], posarray[l] + val - 1}; return; } int m = l+r>>1; if(p <= m) update(l, m, p, k<<1, val); else update(m+1, r, p, k<<1|1, val); T[k] = T[k<<1] + T[k<<1|1]; } void solve(){ cin >> n >> q; a.resize(n); active.resize(n); for(int i = 0; i < n; ++i) cin >> a[i]; for(int i = 0; i < q; ++i){ int t, x; cin >> t >> x; Q.pb({t, x, i}); } for(int i = 0; i < n; ++i) posarray[a[i]] = i; to[n - 1] = n - 1; deque<int> qq; qq.pb(n - 1); for(int i = n - 2; i >= 0; --i){ while(!qq.empty() && a[qq.back()] < a[i]) qq.pop_back(); if(qq.empty()) to[i] = n-1; else to[i] = qq.back()-1; qq.pb(i); } sort(all(Q)); bool ok = 1; int t = 0; int qp = 0; while(qp < Q.size() && Q[qp][0] == t){ ans[Q[qp][2]] = a[Q[qp][1] - 1]; ++qp; } int last = a[0], lastpos = 0; for(int i = 0; i < n; ++i){ if(last < a[i]){ pos[a[lastpos]] = {lastpos, i - 1}; active[a[lastpos]] = 1; last = a[i], lastpos = i; } } active[a[lastpos]] = 1; pos[a[lastpos]] = {lastpos, n-1}; build(1, n, 1); while(ok){ ok = 0; auto x = get(1, n, n/2+1, 1); int lenn = x[2]; while(x[0] > x[1]){ ok = 1; int len = to[posarray[x[1]]] - posarray[x[1]] + 1; lenn -= len; update(1, n, x[0], 1, lenn); update(1, n, x[1], 1, len); if(to[posarray[x[1]]] < n - 1 && a[to[posarray[x[1]]] + 1] < x[0]) x = {x[0], a[to[posarray[x[1]]] + 1], lenn}; else break; } ++t; while(qp < Q.size() && (Q[qp][0] == t || !ok)){ ans[Q[qp][2]] = get(1, n, Q[qp][1], 1)[1]; ++qp; } } for(int i = 0; i < q; ++i) cout << ans[i] << '\n'; } int main(){ cin.tie(0); ios::sync_with_stdio(0); int tt = 1, aa; // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); while(tt--){ solve(); } cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n"; return 0; }

Compilation message (stderr)

Main.cpp: In function 'void build(int, int, int)':
Main.cpp:26:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |   int m = l+r>>1;
      |           ~^~
Main.cpp: In function 'std::array<int, 3> get(int, int, int, int)':
Main.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = l+r>>1;
      |           ~^~
Main.cpp: In function 'void update(int, int, int, int, int)':
Main.cpp:48:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |   int m = l+r>>1;
      |           ~^~
Main.cpp: In function 'void solve()':
Main.cpp:81:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   while(qp < Q.size() && Q[qp][0] == t){
      |         ~~~^~~~~~~~~~
Main.cpp:114:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     while(qp < Q.size() && (Q[qp][0] == t || !ok)){
      |           ~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:126:15: warning: unused variable 'aa' [-Wunused-variable]
  126 |   int tt = 1, aa;
      |               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...