oj.uz

Submission #829026

# Submission time Handle Problem Language Result Execution time Memory
829026 2023-08-18T02:09:47 Z AndriaBeridze Abracadabra (CEOI22_abracadabra) C++14
100 / 100
 2571 ms 89340 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1659 ms 46464 KB Output is correct
2 Correct 1614 ms 46188 KB Output is correct
3 Correct 1495 ms 44592 KB Output is correct
4 Correct 1464 ms 43136 KB Output is correct
5 Correct 1537 ms 45628 KB Output is correct
6 Correct 1521 ms 43364 KB Output is correct
7 Correct 1510 ms 45748 KB Output is correct
8 Correct 1411 ms 43732 KB Output is correct
9 Correct 1440 ms 43148 KB Output is correct
10 Correct 1489 ms 43992 KB Output is correct
11 Correct 1477 ms 43864 KB Output is correct
12 Correct 1417 ms 42516 KB Output is correct
13 Correct 1484 ms 43744 KB Output is correct
14 Correct 1475 ms 44704 KB Output is correct
15 Correct 1518 ms 44864 KB Output is correct
16 Correct 2 ms 3432 KB Output is correct
17 Correct 1541 ms 43232 KB Output is correct
18 Correct 1489 ms 42712 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 1 ms 3412 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1943 ms 89340 KB Output is correct
2 Correct 1967 ms 83436 KB Output is correct
3 Correct 1615 ms 74040 KB Output is correct
4 Correct 1391 ms 54672 KB Output is correct
5 Correct 1478 ms 56548 KB Output is correct
6 Correct 1426 ms 54032 KB Output is correct
7 Correct 1674 ms 60556 KB Output is correct
8 Correct 1574 ms 60324 KB Output is correct
9 Correct 1642 ms 53576 KB Output is correct
10 Correct 1666 ms 54044 KB Output is correct
11 Correct 1243 ms 44456 KB Output is correct
12 Correct 1366 ms 45512 KB Output is correct
13 Correct 1504 ms 52744 KB Output is correct
14 Correct 1305 ms 46048 KB Output is correct
15 Correct 1571 ms 54768 KB Output is correct
16 Correct 46 ms 6348 KB Output is correct
17 Correct 1717 ms 83372 KB Output is correct
18 Correct 1196 ms 43152 KB Output is correct
19 Correct 343 ms 15424 KB Output is correct
20 Correct 368 ms 17332 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 25748 KB Output is correct
2 Correct 278 ms 25840 KB Output is correct
3 Correct 302 ms 25272 KB Output is correct
4 Correct 210 ms 11408 KB Output is correct
5 Correct 252 ms 18088 KB Output is correct
6 Correct 213 ms 12040 KB Output is correct
7 Correct 240 ms 15492 KB Output is correct
8 Correct 228 ms 13724 KB Output is correct
9 Correct 229 ms 15768 KB Output is correct
10 Correct 228 ms 9688 KB Output is correct
11 Correct 172 ms 10124 KB Output is correct
12 Correct 166 ms 9392 KB Output is correct
13 Correct 206 ms 10032 KB Output is correct
14 Correct 173 ms 9768 KB Output is correct
15 Correct 179 ms 9408 KB Output is correct
16 Correct 24 ms 5232 KB Output is correct
17 Correct 231 ms 28540 KB Output is correct
18 Correct 158 ms 9844 KB Output is correct
19 Correct 2 ms 3488 KB Output is correct
20 Correct 2 ms 3412 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1659 ms 46464 KB Output is correct
2 Correct 1614 ms 46188 KB Output is correct
3 Correct 1495 ms 44592 KB Output is correct
4 Correct 1464 ms 43136 KB Output is correct
5 Correct 1537 ms 45628 KB Output is correct
6 Correct 1521 ms 43364 KB Output is correct
7 Correct 1510 ms 45748 KB Output is correct
8 Correct 1411 ms 43732 KB Output is correct
9 Correct 1440 ms 43148 KB Output is correct
10 Correct 1489 ms 43992 KB Output is correct
11 Correct 1477 ms 43864 KB Output is correct
12 Correct 1417 ms 42516 KB Output is correct
13 Correct 1484 ms 43744 KB Output is correct
14 Correct 1475 ms 44704 KB Output is correct
15 Correct 1518 ms 44864 KB Output is correct
16 Correct 2 ms 3432 KB Output is correct
17 Correct 1541 ms 43232 KB Output is correct
18 Correct 1489 ms 42712 KB Output is correct
19 Correct 2 ms 3412 KB Output is correct
20 Correct 1 ms 3412 KB Output is correct
21 Correct 1943 ms 89340 KB Output is correct
22 Correct 1967 ms 83436 KB Output is correct
23 Correct 1615 ms 74040 KB Output is correct
24 Correct 1391 ms 54672 KB Output is correct
25 Correct 1478 ms 56548 KB Output is correct
26 Correct 1426 ms 54032 KB Output is correct
27 Correct 1674 ms 60556 KB Output is correct
28 Correct 1574 ms 60324 KB Output is correct
29 Correct 1642 ms 53576 KB Output is correct
30 Correct 1666 ms 54044 KB Output is correct
31 Correct 1243 ms 44456 KB Output is correct
32 Correct 1366 ms 45512 KB Output is correct
33 Correct 1504 ms 52744 KB Output is correct
34 Correct 1305 ms 46048 KB Output is correct
35 Correct 1571 ms 54768 KB Output is correct
36 Correct 46 ms 6348 KB Output is correct
37 Correct 1717 ms 83372 KB Output is correct
38 Correct 1196 ms 43152 KB Output is correct
39 Correct 343 ms 15424 KB Output is correct
40 Correct 368 ms 17332 KB Output is correct
41 Correct 300 ms 25748 KB Output is correct
42 Correct 278 ms 25840 KB Output is correct
43 Correct 302 ms 25272 KB Output is correct
44 Correct 210 ms 11408 KB Output is correct
45 Correct 252 ms 18088 KB Output is correct
46 Correct 213 ms 12040 KB Output is correct
47 Correct 240 ms 15492 KB Output is correct
48 Correct 228 ms 13724 KB Output is correct
49 Correct 229 ms 15768 KB Output is correct
50 Correct 228 ms 9688 KB Output is correct
51 Correct 172 ms 10124 KB Output is correct
52 Correct 166 ms 9392 KB Output is correct
53 Correct 206 ms 10032 KB Output is correct
54 Correct 173 ms 9768 KB Output is correct
55 Correct 179 ms 9408 KB Output is correct
56 Correct 24 ms 5232 KB Output is correct
57 Correct 231 ms 28540 KB Output is correct
58 Correct 158 ms 9844 KB Output is correct
59 Correct 2 ms 3488 KB Output is correct
60 Correct 2 ms 3412 KB Output is correct
61 Correct 2369 ms 88836 KB Output is correct
62 Correct 2571 ms 83360 KB Output is correct
63 Correct 2013 ms 89240 KB Output is correct
64 Correct 1780 ms 62984 KB Output is correct
65 Correct 1875 ms 66188 KB Output is correct
66 Correct 1867 ms 63080 KB Output is correct
67 Correct 1969 ms 60124 KB Output is correct
68 Correct 1945 ms 60080 KB Output is correct
69 Correct 1797 ms 60992 KB Output is correct
70 Correct 1652 ms 54724 KB Output is correct
71 Correct 1628 ms 52656 KB Output is correct
72 Correct 1763 ms 54548 KB Output is correct
73 Correct 1658 ms 53636 KB Output is correct
74 Correct 1608 ms 55208 KB Output is correct
75 Correct 1704 ms 55404 KB Output is correct
76 Correct 46 ms 6348 KB Output is correct
77 Correct 1742 ms 83696 KB Output is correct
78 Correct 1433 ms 51892 KB Output is correct
79 Correct 2 ms 3412 KB Output is correct
80 Correct 2 ms 3492 KB Output is correct