oj.uz

Submission #773978

# Submission time Handle Problem Language Result Execution time Memory
773978 2023-07-05T10:13:17 Z Valters07 Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 28564 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 328 ms 23168 KB Output is correct
2 Correct 325 ms 22664 KB Output is correct
3 Correct 285 ms 22316 KB Output is correct
4 Correct 215 ms 22060 KB Output is correct
5 Correct 241 ms 24776 KB Output is correct
6 Correct 218 ms 24760 KB Output is correct
7 Correct 242 ms 25024 KB Output is correct
8 Correct 218 ms 23536 KB Output is correct
9 Correct 216 ms 22380 KB Output is correct
10 Correct 217 ms 21908 KB Output is correct
11 Correct 220 ms 21852 KB Output is correct
12 Correct 212 ms 20040 KB Output is correct
13 Correct 229 ms 20848 KB Output is correct
14 Correct 224 ms 22892 KB Output is correct
15 Correct 223 ms 21220 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 205 ms 20216 KB Output is correct
18 Correct 183 ms 20116 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3058 ms 28564 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 3044 ms 11052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 328 ms 23168 KB Output is correct
2 Correct 325 ms 22664 KB Output is correct
3 Correct 285 ms 22316 KB Output is correct
4 Correct 215 ms 22060 KB Output is correct
5 Correct 241 ms 24776 KB Output is correct
6 Correct 218 ms 24760 KB Output is correct
7 Correct 242 ms 25024 KB Output is correct
8 Correct 218 ms 23536 KB Output is correct
9 Correct 216 ms 22380 KB Output is correct
10 Correct 217 ms 21908 KB Output is correct
11 Correct 220 ms 21852 KB Output is correct
12 Correct 212 ms 20040 KB Output is correct
13 Correct 229 ms 20848 KB Output is correct
14 Correct 224 ms 22892 KB Output is correct
15 Correct 223 ms 21220 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 205 ms 20216 KB Output is correct
18 Correct 183 ms 20116 KB Output is correct
19 Correct 2 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Execution timed out 3058 ms 28564 KB Time limit exceeded
22 Halted 0 ms 0 KB -