oj.uz

Submission #773972

# Submission time Handle Problem Language Result Execution time Memory
773972 2023-07-05T10:09:50 Z Valters07 Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 29564 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long
#define en cin.close();return 0;
#define pb push_back
#define fi first//printf("%lli\n",cur);
#define se second//scanf("%lli",&n);
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5+5;
struct node
{
    int prior, val, mx, sz, l, r;
};
vector<node> treap;
vector<pair<int,int> > qu[N];
int nw(int val)
{
    treap.pb({rng(),val,val,1,0,0});
    return treap.size()-1;
}
void update(int node)
{
    if(!node) return;
    int l = treap[node].l, r = treap[node].r;
    treap[node].mx = max({treap[node].val,treap[l].mx,treap[r].mx});
    treap[node].sz = treap[l].sz+treap[r].sz+1;
}
int merg(int t1, int t2)
{
    if(!t1||!t2)
        return (t1|t2);
    if(treap[t1].prior<treap[t2].prior)
    {
        treap[t1].r=merg(treap[t1].r,t2);
        update(t1);
        return t1;
    }
    else
    {
        treap[t2].l=merg(t1,treap[t2].l);
        update(t2);
        return t2;
    }
}
pair<int,int> splitbysize(int t, int k)
{
    if(!t)
        return {0,0};
    int l = treap[t].l, r = treap[t].r, sz = treap[l].sz;
//    cout << t << " : " << l << " " << r << "  " << sz << endl;
    if(sz>=k)
    {
        pair<int,int> tt = splitbysize(l,k);
        treap[t].l=tt.se;
        update(t);
        return {tt.fi,t};
    }
    else
    {
        pair<int,int> tt = splitbysize(r,k-treap[l].sz-1);
        treap[t].r=tt.fi;
        update(t);
        return {t,tt.se};
    }
}
pair<int,int> splitbymax(int t, int val)
{
    if(!t)
        return {0,0};
    int l = treap[t].l, r = treap[t].r;
    if(treap[l].mx>val||treap[t].val>val)
    {
        pair<int,int> tt = splitbymax(l,val);
        treap[t].l=tt.se;
        update(t);
        return {tt.fi,t};
    }
    else
    {
        pair<int,int> tt = splitbymax(r,val);
        treap[t].r=tt.fi;
        update(t);
        return {t,tt.se};
    }
}
int getkth(int t, int k)
{
    if(!t)
        return 0;
    int l = treap[t].l, r = treap[t].r, sz = treap[l].sz;
//    cout << t << " : "  << l << " " << r << endl;
//    cout << k << " " << sz << endl << endl;
    if(sz+1==k)
        return treap[t].val;
    if(sz>=k)
        return getkth(l,k);
    return getkth(r,k-sz-1);
}
vector<int> make_op(vector<int> &a)
{
    int n = a.size();
    vector<int> ret;
    int it = 0, it2 = n/2;
    while(it<n/2||it2<n)
    {
        if(it==n/2)
            ret.pb(a[it2++]);
        else if(it2==n)
            ret.pb(a[it++]);
        else if(a[it]<a[it2])
            ret.pb(a[it++]);
        else
            ret.pb(a[it2++]);
    }
    return ret;
}
//void pr(int u)
//{
//    if(u==0)
//        return;
//    pr(treap[u].l);
//    cout << treap[u].val << " ";
////    cout << u << " " << treap[u].val << "\n";
//    pr(treap[u].r);
//}
int main()
{
    fio
//    ifstream cin("in.in");
//    srand(69696);
    treap.pb({0,0,0,0,0,0});
    int n, q, r = 1;
    cin >> n >> q;
    vector<int> a(n), ans(q);
    for(auto &x:a)
        cin >> x;
    for(int qi = 0;qi<q;qi++)
    {
        int t, x;
        cin >> t >> x;
        qu[min(t,n-1)].pb({x,qi});
    }
    for(int i = 0;i<n;i++)
    {
        if(i==0)
        {
            for(auto x:qu[i])
                ans[x.se]=a[x.fi-1];
            a=make_op(a);
            r=nw(a[0]);
            for(int i = 1;i<n;i++)
                r=merg(r,nw(a[i]));
//            for(int i = 0;i<n;i++)
//                cout << a[i] << " ";en
//            pr(r);en
        }
        else
        {
            for(auto x:qu[i])
            {
                ans[x.se]=getkth(r,x.fi);
//                auto t = splitbysize(r,x.fi);
//                cout << endl;
//                pr(t.fi);en
//                cout << treap[1].l;en
//                cout << t.fi << " " << treap[t.fi].l;en
//                cout << treap[treap[t.fi].l].val << " " << t.se;en
//                auto t2 = splitbysize(t.fi,x.fi-1);
//                ans[x.se]=treap[t2.se].val;
//                r=merg(t2.fi,merg(t2.se,t.se));
            }
            auto t = splitbysize(r,n/2);
//            pr(t.fi);cout << endl;
//            pr(t.se);en
//                auto t4 = splitbysize(t2.fi,treap[t2.fi].sz-1);
//                t2.fi=t4.fi;
//                t2.se=merg(t4.se,t2.se);
            while(treap[t.se].sz>1)
            {
                int val = getkth(t.se,1);
//                cout << val;en
                auto t2 = splitbymax(t.se,val);
//                auto t4 = splitbysize(t2.fi,treap[t2.fi].sz-1);
//                t2.fi=t4.fi;
//                t2.se=merg(t4.se,t2.se);
//                pr(t2.fi);cout << endl;
//                pr(t2.se);en
                auto t3 = splitbymax(t.fi,val);
//                auto t5 = splitbysize(t3.fi,treap[t3.fi].sz-1);
//                t3.fi=t5.fi;
//                t3.se=merg(t5.se,t3.se);
                t.fi=merg(merg(t3.fi,t2.fi),t3.se);
                t.se=t2.se;
//                pr(t.fi);cout << endl;
//                pr(t.se);cout << endl << endl;
            }
            r=merg(t.fi,t.se);
        }
    }
    for(auto x:ans)
        cout << x << "\n";
//    cin.close();
    return 0;
}

Compilation message

Main.cpp: In function 'int nw(int)':
Main.cpp:21:18: warning: narrowing conversion of 'rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()()' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   21 |     treap.pb({rng(),val,val,1,0,0});
      |               ~~~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 23420 KB Output is correct
2 Correct 325 ms 22624 KB Output is correct
3 Correct 271 ms 22080 KB Output is correct
4 Correct 217 ms 21928 KB Output is correct
5 Correct 232 ms 24532 KB Output is correct
6 Correct 224 ms 24612 KB Output is correct
7 Correct 240 ms 24884 KB Output is correct
8 Correct 229 ms 23376 KB Output is correct
9 Correct 231 ms 22240 KB Output is correct
10 Correct 222 ms 22120 KB Output is correct
11 Correct 274 ms 22680 KB Output is correct
12 Correct 203 ms 21088 KB Output is correct
13 Correct 232 ms 21896 KB Output is correct
14 Correct 230 ms 23920 KB Output is correct
15 Correct 246 ms 22284 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 222 ms 21332 KB Output is correct
18 Correct 187 ms 21308 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3040 ms 29564 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3029 ms 11908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 311 ms 23420 KB Output is correct
2 Correct 325 ms 22624 KB Output is correct
3 Correct 271 ms 22080 KB Output is correct
4 Correct 217 ms 21928 KB Output is correct
5 Correct 232 ms 24532 KB Output is correct
6 Correct 224 ms 24612 KB Output is correct
7 Correct 240 ms 24884 KB Output is correct
8 Correct 229 ms 23376 KB Output is correct
9 Correct 231 ms 22240 KB Output is correct
10 Correct 222 ms 22120 KB Output is correct
11 Correct 274 ms 22680 KB Output is correct
12 Correct 203 ms 21088 KB Output is correct
13 Correct 232 ms 21896 KB Output is correct
14 Correct 230 ms 23920 KB Output is correct
15 Correct 246 ms 22284 KB Output is correct
16 Correct 5 ms 5076 KB Output is correct
17 Correct 222 ms 21332 KB Output is correct
18 Correct 187 ms 21308 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Execution timed out 3040 ms 29564 KB Time limit exceeded
22 Halted 0 ms 0 KB -