oj.uz

Submission #947327

# Submission time Handle Problem Language Result Execution time Memory
947327 2024-03-15T22:04:48 Z ttamx Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 946 ms 69396 KB 
#include<bits/stdc++.h>

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

struct Treap{
    struct node;
    using pnode = node*;
    struct node{
        int val,freq,sz,prio;
        pnode l,r;
        node(int _val,int _freq=1):val(_val),freq(_freq),sz(_freq),prio(rng()),l(nullptr),r(nullptr){}
    };
    pnode rt;
    Treap():rt(nullptr){}
    static int get_val(pnode t){
        return t?t->val:0;
    }
    static int get_sz(pnode t){
        return t?t->sz:0;
    }
    static void pull(pnode t){
        if(!t)return;
        t->sz=get_sz(t->l)+t->freq+get_sz(t->r);
    }
    static void merge(pnode &t,pnode l,pnode r){
        if(!l)return void(t=r);
        if(!r)return void(t=l);
        if(l->prio>r->prio)merge(l->r,l->r,r),t=l;
        else merge(r->l,l,r->l),t=r;
        pull(t);
    }
    void merge(pnode l,pnode r){
        merge(rt,l,r);
    }
    static void split(pnode t,pnode &l,pnode &r,int k){
        if(!t)return void(l=r=nullptr);
        int x=t->freq+get_sz(t->l);
        if(x>k)split(t->l,l,t->l,k),r=t;
        else split(t->r,t->r,r,k-x),l=t;
        pull(t);
    }
    void split(pnode &l,pnode &r,int k){
        split(rt,l,r,k);
    }
    static void split_first(pnode t,pnode &l,pnode &r){
        if(!t)return void(l=r=nullptr);
        if(t->l)split_first(t->l,l,t->l),r=t;
        else l=t,r=t->r,t->r=nullptr;
        pull(t);
    }
    static void split_by_val(pnode t,pnode &l,pnode &r,int key){
        if(!t)return void(l=r=nullptr);
        if(t->val>=key)split_by_val(t->l,l,t->l,key),r=t;
        else split_by_val(t->r,t->r,r,key),l=t;
        pull(t);
    }
    void split_by_val(pnode &l,pnode &r,int key){
        split_by_val(rt,l,r,key);
    }
    static int get_first(pnode t){
        if(!t)return 0;
        if(t->l)return get_first(t->l);
        return t->val;
    }
    int get_first(){
        return get_first(rt);
    }
    pair<int,int> get(pnode t,int k){
        if(k<=get_sz(t->l))return get(t->l,k);
        if(k>t->freq+get_sz(t->l))return get(t->r,k-t->freq-get_sz(t->l));
        return {t->val,k-get_sz(t->l)};
    }
    pair<int,int> get(int k){
        return get(rt,k);
    }
    void insert(int val,int freq=1){
        merge(rt,new node(val,freq));
    }
    int size(){
        return get_sz(rt);
    }
    void dbg(){
        function<void(pnode)> dfs=[&](pnode t){
            if(!t)return;
            dfs(t->l);
            cerr << "(" << t->val << "," << t->freq << ") ";
            dfs(t->r);
        };
        dfs(rt);
        cerr << "\n";
    }
};
using node = Treap::node;
using pnode = Treap::pnode;

const int N=2e5+5;
const int Q=1e6+5;

int n,q;
int a[N],nxt[N],inv[N],pre[N];
stack<int> s;
Treap t[N],tr;
bool done=false;
vector<tuple<int,int,int>> qr;
int ans[Q];

void insert_main_tree(int id,int freq){
    pnode t1,t2;
    tr.split_by_val(t1,t2,id);
    tr.merge(t1,new node(id,freq));
    tr.merge(tr.rt,t2);
}

void work(){
    if(done)return;
    pnode t1,t2,t3;
    tr.split(t1,t2,n/2);
    int rem=n/2-Treap::get_sz(t1);
    if(!rem)return done=true,tr.merge(t1,t2);
    Treap::split_first(t2,t2,t3);
    int id=inv[t2->val];
    int tar=nxt[id];
    t[id].split(t[id].rt,t2,rem);
    tr.merge(t1,new node(a[id],t[id].size()));
    id=inv[Treap::get_first(t2)];
    tr.merge(tr.rt,t3);
    for(int i=id;t2;){
        int memo=nxt[i];
        Treap::split(t2,t[i].rt,t2,memo-i);
        insert_main_tree(a[i],t[i].size());
        i=memo;
    }
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> q;
    for(int i=1;i<=n;i++)cin >> a[i],inv[a[i]]=i;
    for(int i=1;i<=n;i++){
        while(!s.empty()&&a[i]>a[s.top()]){
            int j=s.top();
            s.pop();
            nxt[j]=i;
        }
        if(s.empty()){
            t[i].insert(a[i]);
            pre[i]=i;
        }else{
            pre[i]=pre[s.top()];
            t[pre[i]].insert(a[i]);
        }
        s.emplace(i);
    }
    inv[0]=n+1;
    while(!s.empty()){
        nxt[s.top()]=n+1;
        s.pop();
    }
    for(int i=1;i<=n;i++)if(pre[i]==i)tr.insert(a[i],t[i].size());
    for(int i=0;i<q;i++){
        int x,y;
        cin >> x >> y;
        qr.emplace_back(x,y,i);
    }
    sort(qr.begin(),qr.end());
    int cnt=0;
    for(auto [x,y,i]:qr){
        while(!done&&cnt<x){
            work();
            cnt++;
        }
        auto [val,rem]=tr.get(y);
        ans[i]=t[inv[val]].get(rem).first;
    }
    for(int i=0;i<q;i++)cout << ans[i] << "\n";
}

Compilation message

Main.cpp: In function 'void work()':
Main.cpp:124:9: warning: unused variable 'tar' [-Wunused-variable]
  124 |     int tar=nxt[id];
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 32120 KB Output is correct
2 Correct 301 ms 31920 KB Output is correct
3 Correct 287 ms 31128 KB Output is correct
4 Correct 276 ms 29944 KB Output is correct
5 Correct 294 ms 31664 KB Output is correct
6 Correct 286 ms 30476 KB Output is correct
7 Correct 290 ms 31664 KB Output is correct
8 Correct 270 ms 30544 KB Output is correct
9 Correct 293 ms 30128 KB Output is correct
10 Correct 272 ms 30384 KB Output is correct
11 Correct 291 ms 30764 KB Output is correct
12 Correct 265 ms 29804 KB Output is correct
13 Correct 282 ms 30480 KB Output is correct
14 Correct 284 ms 30892 KB Output is correct
15 Correct 287 ms 31276 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 257 ms 30376 KB Output is correct
18 Correct 272 ms 29556 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 403 ms 66200 KB Output is correct
2 Correct 337 ms 60352 KB Output is correct
3 Correct 308 ms 52144 KB Output is correct
4 Correct 315 ms 48380 KB Output is correct
5 Correct 332 ms 49328 KB Output is correct
6 Correct 296 ms 46508 KB Output is correct
7 Correct 370 ms 51856 KB Output is correct
8 Correct 327 ms 50960 KB Output is correct
9 Correct 306 ms 47836 KB Output is correct
10 Correct 305 ms 47632 KB Output is correct
11 Correct 266 ms 43164 KB Output is correct
12 Correct 274 ms 43464 KB Output is correct
13 Correct 298 ms 46620 KB Output is correct
14 Correct 274 ms 43184 KB Output is correct
15 Correct 308 ms 48660 KB Output is correct
16 Correct 36 ms 17352 KB Output is correct
17 Correct 274 ms 53728 KB Output is correct
18 Correct 242 ms 40624 KB Output is correct
19 Correct 81 ms 24764 KB Output is correct
20 Correct 92 ms 26044 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 26564 KB Output is correct
2 Correct 88 ms 22664 KB Output is correct
3 Correct 118 ms 23496 KB Output is correct
4 Correct 72 ms 17564 KB Output is correct
5 Correct 107 ms 21192 KB Output is correct
6 Correct 74 ms 17920 KB Output is correct
7 Correct 118 ms 19904 KB Output is correct
8 Correct 87 ms 18372 KB Output is correct
9 Correct 90 ms 19908 KB Output is correct
10 Correct 62 ms 16568 KB Output is correct
11 Correct 66 ms 16940 KB Output is correct
12 Correct 60 ms 16432 KB Output is correct
13 Correct 74 ms 17028 KB Output is correct
14 Correct 65 ms 16844 KB Output is correct
15 Correct 63 ms 16684 KB Output is correct
16 Correct 17 ms 11868 KB Output is correct
17 Correct 47 ms 20888 KB Output is correct
18 Correct 45 ms 16852 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 300 ms 32120 KB Output is correct
2 Correct 301 ms 31920 KB Output is correct
3 Correct 287 ms 31128 KB Output is correct
4 Correct 276 ms 29944 KB Output is correct
5 Correct 294 ms 31664 KB Output is correct
6 Correct 286 ms 30476 KB Output is correct
7 Correct 290 ms 31664 KB Output is correct
8 Correct 270 ms 30544 KB Output is correct
9 Correct 293 ms 30128 KB Output is correct
10 Correct 272 ms 30384 KB Output is correct
11 Correct 291 ms 30764 KB Output is correct
12 Correct 265 ms 29804 KB Output is correct
13 Correct 282 ms 30480 KB Output is correct
14 Correct 284 ms 30892 KB Output is correct
15 Correct 287 ms 31276 KB Output is correct
16 Correct 1 ms 6492 KB Output is correct
17 Correct 257 ms 30376 KB Output is correct
18 Correct 272 ms 29556 KB Output is correct
19 Correct 1 ms 6492 KB Output is correct
20 Correct 1 ms 6492 KB Output is correct
21 Correct 403 ms 66200 KB Output is correct
22 Correct 337 ms 60352 KB Output is correct
23 Correct 308 ms 52144 KB Output is correct
24 Correct 315 ms 48380 KB Output is correct
25 Correct 332 ms 49328 KB Output is correct
26 Correct 296 ms 46508 KB Output is correct
27 Correct 370 ms 51856 KB Output is correct
28 Correct 327 ms 50960 KB Output is correct
29 Correct 306 ms 47836 KB Output is correct
30 Correct 305 ms 47632 KB Output is correct
31 Correct 266 ms 43164 KB Output is correct
32 Correct 274 ms 43464 KB Output is correct
33 Correct 298 ms 46620 KB Output is correct
34 Correct 274 ms 43184 KB Output is correct
35 Correct 308 ms 48660 KB Output is correct
36 Correct 36 ms 17352 KB Output is correct
37 Correct 274 ms 53728 KB Output is correct
38 Correct 242 ms 40624 KB Output is correct
39 Correct 81 ms 24764 KB Output is correct
40 Correct 92 ms 26044 KB Output is correct
41 Correct 136 ms 26564 KB Output is correct
42 Correct 88 ms 22664 KB Output is correct
43 Correct 118 ms 23496 KB Output is correct
44 Correct 72 ms 17564 KB Output is correct
45 Correct 107 ms 21192 KB Output is correct
46 Correct 74 ms 17920 KB Output is correct
47 Correct 118 ms 19904 KB Output is correct
48 Correct 87 ms 18372 KB Output is correct
49 Correct 90 ms 19908 KB Output is correct
50 Correct 62 ms 16568 KB Output is correct
51 Correct 66 ms 16940 KB Output is correct
52 Correct 60 ms 16432 KB Output is correct
53 Correct 74 ms 17028 KB Output is correct
54 Correct 65 ms 16844 KB Output is correct
55 Correct 63 ms 16684 KB Output is correct
56 Correct 17 ms 11868 KB Output is correct
57 Correct 47 ms 20888 KB Output is correct
58 Correct 45 ms 16852 KB Output is correct
59 Correct 1 ms 6492 KB Output is correct
60 Correct 1 ms 6492 KB Output is correct
61 Correct 946 ms 69396 KB Output is correct
62 Correct 782 ms 61660 KB Output is correct
63 Correct 875 ms 62896 KB Output is correct
64 Correct 660 ms 53320 KB Output is correct
65 Correct 715 ms 55180 KB Output is correct
66 Correct 645 ms 53680 KB Output is correct
67 Correct 639 ms 51368 KB Output is correct
68 Correct 639 ms 50264 KB Output is correct
69 Correct 693 ms 51380 KB Output is correct
70 Correct 597 ms 47800 KB Output is correct
71 Correct 467 ms 46768 KB Output is correct
72 Correct 567 ms 48808 KB Output is correct
73 Correct 500 ms 47788 KB Output is correct
74 Correct 569 ms 48512 KB Output is correct
75 Correct 587 ms 48388 KB Output is correct
76 Correct 32 ms 17236 KB Output is correct
77 Correct 342 ms 53932 KB Output is correct
78 Correct 362 ms 46400 KB Output is correct
79 Correct 1 ms 6492 KB Output is correct
80 Correct 1 ms 6492 KB Output is correct