Submission #829026

#	Time	Username	Problem	Language	Result	Execution time	Memory
829026		AndriaBeridze	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	2571 ms	89340 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<deque>
#include<stack>
#include<queue>
#include<iomanip>
#include<fstream>
#include<cmath>
#define x first
#define l second.first
#define r second.second
#define int long long
#define N 400005
#define mod (int) 99824435
#define all(x) x.begin(), x.end()
#define mid(l, r) (l + r) / 2
#define left node * 2, l, (l + r) / 2
#define right node * 2 + 1, (l + r) / 2 + 1, r
#define connect(a, b) graph[a].push_back(b), graph[b].push_back(a)
#define YN(a) cout << (a ? "Yes" : "No") << endl;
#define size(v) (int) v.size()
#define debug cout << "!" << endl;
using namespace std;
set<pair<int, pair<int, int>>> st, ans;
vector<pair<pair<int, int>, int>> v;
vector<pair<int, pair<int, int>>> blocks;
vector<int> nxt(N + 1);
vector<int> f;
int a[N + 1];
int n, q;
int find(pair<int, pair<int, int>> p){
     int l1 = 0, r1 = size(blocks) - 1;
     while(l1 < r1){
          int mid = mid(l1, r1);
          if(blocks[mid] == p) return mid;
          if(blocks[mid] > p) r1 = mid - 1;
          else l1 = mid + 1;
     }
     return l1;
}
void find_block(){
     auto k = st;
     auto it = st.end();
     int sum = 0;
     for(int i = 0; i <= n; i++){
          while(true){
               it = st.end();
               it--;
               if(sum + (*it).r - (*it).l + 1 > n / 2) break;
               sum += (*it).r - (*it).l + 1;
               st.erase(it);
          }
          if(sum == n / 2) continue;
          it = st.end();
          it--;
          int cur = n - (sum + (*it).r - (*it).l + 1);
          int curi = (*it).l + (n / 2 - cur);
          auto p = *it;
          st.erase(it);
          st.insert({p.x, {p.l, curi - 1}});
          blocks.push_back({p.x, {p.l, curi - 1}});
          while(curi <= p.r){
               st.insert({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
               blocks.push_back({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
               curi = nxt[curi];
          }
     }
     st = k;
}
void add(int ind, int val){
     while(ind < size(f)){
          f[ind] += val;
          ind += (ind & (-ind));
     }
}
int count(int ind){
     int sum = 0;
     while(ind){
          sum += f[ind];
          ind -= (ind & (-ind));
     }
     return sum;
}
int find1(int val){
     int l1 = 1, r1 = size(blocks);
     while(l1 < r1){
          int mid = mid(l1, r1);
          if(count(mid) >= val) r1 = mid;
          else l1 = mid + 1;
     }
     return l1;
}
void solve(){
     cin >> n >> q;
     for(int i = 1; i <= n; i++) nxt[i] = n + 1;
     for(int i = 1; i <= n; i++){
          cin >> a[i];
     }
     stack<int> s;
     for(int i = 1; i <= n; i++){
          while(size(s) && a[s.top()] < a[i]){
               nxt[s.top()] = i;
               s.pop();
          }
          s.push(i);
     }

     int cnt = 0;
     while(q--){
          int i, t;
          cin >> t >> i;
          v.push_back({{min(n, t), i}, cnt++});
     }
     sort(all(v));
     int mx = 0;
     int L, R;
     for(int i = 1; i <= n; i++){
          if(mx > a[i]) R++;
          else{
               if(i != 1) st.insert({mx, {L, R}}), ans.insert({mx, {L, R}}), blocks.push_back({mx, {L, R}});
               L = R = i;
          }
          mx = max(mx, a[i]);
     }
     st.insert({mx, {L, R}});
     ans.insert({mx, {L, R}});
     blocks.push_back({mx, {L, R}});
     find_block();
     sort(all(blocks));
     f = vector<int>(size(blocks) + 1, 0);
     for(auto k : st){
          add(find(k) + 1, k.r - k.l + 1);
     }
     auto it = st.end();
     int sum = 0, ind = 0;
     vector<int> b(cnt, 0);
     for(int i = 0; i <= n; i++){
          while(ind != size(v) && v[ind].first.first == i){
               int ind1 = find1(v[ind].first.second);
               ind1--;
               //cout << v[ind].first.first << ' ' << v[ind].first.second << ' ' << blocks[ind1].x << ' ' << blocks[ind1].l << ' ' << blocks[ind1].r << endl;
               b[v[ind].second] = a[blocks[ind1].l + (v[ind].first.second - count(ind1)) - 1];
               ind++;
          }
          while(true){
               it = st.end();
               it--;
               if(sum + (*it).r - (*it).l + 1 > n / 2) break;
               sum += (*it).r - (*it).l + 1;
               st.erase(it);
          }
          if(sum == n / 2) continue;
          it = st.end();
          it--;
          int cur = n - (sum + (*it).r - (*it).l + 1);
          int curi = (*it).l + (n / 2 - cur);
          auto p = *it;
          add(find(p) + 1, -(p.r - p.l + 1));
          ans.erase(ans.find(p));
          st.erase(it);
          st.insert({p.x, {p.l, curi - 1}});
          ans.insert({p.x, {p.l, curi - 1}});
          add(find({p.x, {p.l, curi - 1}}) + 1, curi - p.l);
          while(curi <= p.r){
               st.insert({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
               ans.insert({a[curi], {curi, min(p.r, nxt[curi] - 1)}});
               add(find({a[curi], {curi, min(p.r, nxt[curi] - 1)}}) + 1, min(p.r, nxt[curi] - 1) - curi + 1);
               curi = nxt[curi];
          }
     }
     for(int k : b) cout << k << endl;
}
signed main(){
     int q = 1;
     //cin >> q;
     while(q--){
          solve();
     }
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:122:26: warning: 'R' may be used uninitialized in this function [-Wmaybe-uninitialized]
  122 |           if(mx > a[i]) R++;
      |                         ~^~

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