Submission #865575

#TimeUsernameProblemLanguageResultExecution timeMemory
865575mychecksedadAbracadabra (CEOI22_abracadabra)C++17
10 / 100
3046 ms32876 KiB
/* Author : Mychecksdead */ #include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> // Common file #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #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; typedef tree< array<int, 3>, null_type, less<array<int, 3>>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; int n, q, ans[N]; vector<array<int, 3>> Q; void solve(){ cin >> n >> q; vector<int> a(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 - 1, 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]]; ++qp; } ordered_set oset; int last = a[0], lastpos = 0; for(int i = 0; i < n; ++i){ if(last < a[i]) last = a[i], lastpos = i; oset.insert({last, i - lastpos, a[i]}); } // for(auto k: oset) cout << k[0] << ' ' << k[1] << ' ' << k[2] << '\n'; // en; while(ok){ ok = 0; int last = 0, lastpos = 0; for(int i = n/2; i < n; ++i){ auto it = oset.find_by_order(i); if((*it)[2] > last){ last = (*it)[2]; lastpos = i; } array<int, 3> vv = {last, i - lastpos, (*it)[2]}; if(last == (*it)[0]) break; ok = 1; oset.erase(it); oset.insert(vv); } ++t; while(qp < Q.size() && (Q[qp][0] == t || !ok)){ ans[Q[qp][2]] = (*oset.find_by_order(Q[qp][1]))[2]; ++qp; } // for(auto k: oset) cout << k[0] << ' ' << k[1] << ' ' << k[2] << '\n'; // en; } 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 solve()':
Main.cpp:37: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]
   37 |   while(qp < Q.size() && Q[qp][0] == t){
      |         ~~~^~~~~~~~~~
Main.cpp:67: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]
   67 |     while(qp < Q.size() && (Q[qp][0] == t || !ok)){
      |           ~~~^~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:81:15: warning: unused variable 'aa' [-Wunused-variable]
   81 |   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...