oj.uz

Submission #994486

# Submission time Handle Problem Language Result Execution time Memory
994486 2024-06-07T17:30:03 Z biank Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 750 ms 33464 KB 
#include <bits/stdc++.h>

using namespace std;

#define sz(x) int(x.size())
#define all(x) begin(x),end(x)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define forn(i,n) for(int i=0;i<int(n);i++)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
//#define dbg(x) cerr<<#x<<": "<<x<<endl

#define pb push_back

typedef vector<int> vi;
typedef vector<pair<int,int>> vii;

struct Node{
    int val;
    int maxi;
    int sz;
    int p;
    Node* l;
    Node* r;
    Node(int v){
        val=maxi=v,sz=1;
        p=rand();
        l=r=nullptr;
    }
};

int max(Node* u){
    if(!u)return 0;
    return u->maxi;
}

int size(Node* u){
    if(!u)return 0;
    return u->sz;
}

void evaluate(Node* u){
    if(u){
        u->maxi=max({u->val,max(u->l),max(u->r)});
        u->sz=1+size(u->l)+size(u->r);
    }
}

pair<Node*,Node*> splitk(Node* u, int k){
    if(!u) return {nullptr, nullptr};
    if(k>=size(u->l)+1){
        auto[l,r]=splitk(u->r,k-size(u->l)-1);
        u->r=l;
        evaluate(u);
        return {u,r};
    }else{
        auto[l,r]=splitk(u->l,k);
        u->l=r;
        evaluate(u);
        return {l,u};
    }
}

Node* merge(Node* l, Node* r){
    if(!l) return r;
    if(!r) return l;
    if(l->p>r->p){
        l->r=merge(l->r,r);
        evaluate(l);
        return l;
    }else{
        r->l=merge(l,r->l);
        evaluate(r);
        return r;
    }
}

void heapify(Node *u){
    if(!u)return;
    Node* maxP=u;
    if(u->l&&u->l->p>maxP->p) maxP=u->l;
    if(u->r&&u->r->p>maxP->p) maxP=u->r;
    if(maxP!=u){
        swap(maxP->p,u->p);
        heapify(maxP);
    }
}

Node* build(vi &v, int l, int r){
    if(l>r) return nullptr;
    int m=(l+r)/2;
    Node* u=new Node(v[m]);
    u->l=build(v,l,m-1);
    u->r=build(v,m+1,r);
    evaluate(u);
    return u;
}

void dfs(Node* u){
    if(!u) return;
    dfs(u->l);
    cerr<<u->val<<' ';
    dfs(u->r);
}

pair<Node*,Node*> splitv(Node* u, int v){
    if(!u) return {nullptr, nullptr};
    if(max(max(u->l),u->val)<=v){
        auto[l,r]=splitv(u->r,v);
        u->r=l;
        evaluate(u);
        return {u,r};
    }else{
        auto[l,r]=splitv(u->l,v);
        u->l=r;
        evaluate(u);
        return {l,u};
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    srand(time(0));
    int n,q;
    cin>>n>>q;
    vi v(n);
    forn(i,n) cin>>v[i];
    Node* root=build(v,0,n-1);
    heapify(root);
    vector<vii> queries(n+1);
    forn(idx,q){
        int t,i;
        cin>>t>>i;
        t=min(t,n),--i;
        queries[t].pb({i,idx});
    }
    vi res(q);
    #define dbg(x) dfs(x); cerr<<'\n'
    forn(i,n+1){
        for(auto[p,idx]:queries[i]){
            Node *l,*m,*r;
            tie(l,r)=splitk(root,p);
            tie(m,r)=splitk(r,1);
            res[idx]=m->val;
            root=merge(merge(l,m),r);
        }
        Node *l, *m1, *m2, *r;
        tie(l,r)=splitk(root,n/2);
        int val=max(l);
        //dbg(l);
        //dbg(r);
        tie(m2,r)=splitv(r,val);
        //dbg(m2);
        val=max(m2);
        tie(l,m1)=splitv(l,val);
        //dbg(m1);
        root=merge(merge(l,m2),merge(m1,r));
    }
    forn(i,q) cout<<res[i]<<'\n';
    
    return 0;
}

Compilation message

Main.cpp: In function 'std::pair<Node*, Node*> splitk(Node*, int)':
Main.cpp:52:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         auto[l,r]=splitk(u->r,k-size(u->l)-1);
      |             ^
Main.cpp:57:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   57 |         auto[l,r]=splitk(u->l,k);
      |             ^
Main.cpp: In function 'std::pair<Node*, Node*> splitv(Node*, int)':
Main.cpp:109:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |         auto[l,r]=splitv(u->r,v);
      |             ^
Main.cpp:114:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  114 |         auto[l,r]=splitv(u->l,v);
      |             ^
Main.cpp: In function 'int main()':
Main.cpp:141:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  141 |         for(auto[p,idx]:queries[i]){
      |                 ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 18364 KB Output is correct
2 Correct 435 ms 17232 KB Output is correct
3 Correct 417 ms 16720 KB Output is correct
4 Correct 399 ms 15756 KB Output is correct
5 Correct 417 ms 19028 KB Output is correct
6 Correct 405 ms 19540 KB Output is correct
7 Incorrect 421 ms 20308 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 750 ms 33456 KB Output is correct
2 Correct 704 ms 33464 KB Output is correct
3 Correct 585 ms 29620 KB Output is correct
4 Correct 566 ms 30388 KB Output is correct
5 Correct 591 ms 29876 KB Output is correct
6 Correct 590 ms 29936 KB Output is correct
7 Incorrect 680 ms 33204 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 10836 KB Output is correct
2 Correct 152 ms 10324 KB Output is correct
3 Correct 150 ms 10068 KB Output is correct
4 Correct 144 ms 10000 KB Output is correct
5 Correct 173 ms 10556 KB Output is correct
6 Correct 152 ms 9904 KB Output is correct
7 Incorrect 153 ms 10324 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 425 ms 18364 KB Output is correct
2 Correct 435 ms 17232 KB Output is correct
3 Correct 417 ms 16720 KB Output is correct
4 Correct 399 ms 15756 KB Output is correct
5 Correct 417 ms 19028 KB Output is correct
6 Correct 405 ms 19540 KB Output is correct
7 Incorrect 421 ms 20308 KB Output isn't correct
8 Halted 0 ms 0 KB -