oj.uz

Submission #773991

# Submission time Handle Problem Language Result Execution time Memory
773991 2023-07-05T10:29:47 Z Valters07 Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 28820 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;
    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;
    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;
}
int main()
{
    fio
//    ifstream cin("in.in");
    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]));
        }
        else
        {
            for(auto x:qu[i])
                ans[x.se]=getkth(r,x.fi);
            auto t = splitbysize(r,n/2);
            while(treap[t.se].sz>1)
            {
                int val = getkth(t.se,1);
                auto t2 = splitbymax(t.se,val);
                auto t3 = splitbymax(t.fi,val);
                t.fi=merg(merg(t3.fi,t2.fi),t3.se);
                t.se=t2.se;
            }
            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 332 ms 23264 KB Output is correct
2 Correct 313 ms 23136 KB Output is correct
3 Correct 282 ms 22640 KB Output is correct
4 Correct 222 ms 22416 KB Output is correct
5 Correct 240 ms 25048 KB Output is correct
6 Correct 218 ms 25128 KB Output is correct
7 Correct 237 ms 25420 KB Output is correct
8 Correct 251 ms 23836 KB Output is correct
9 Correct 217 ms 22788 KB Output is correct
10 Correct 220 ms 22552 KB Output is correct
11 Correct 228 ms 22996 KB Output is correct
12 Correct 202 ms 21144 KB Output is correct
13 Correct 258 ms 22256 KB Output is correct
14 Correct 229 ms 24012 KB Output is correct
15 Correct 234 ms 22396 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 206 ms 21144 KB Output is correct
18 Correct 191 ms 21016 KB Output is correct
19 Correct 3 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 3049 ms 28820 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 11328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 332 ms 23264 KB Output is correct
2 Correct 313 ms 23136 KB Output is correct
3 Correct 282 ms 22640 KB Output is correct
4 Correct 222 ms 22416 KB Output is correct
5 Correct 240 ms 25048 KB Output is correct
6 Correct 218 ms 25128 KB Output is correct
7 Correct 237 ms 25420 KB Output is correct
8 Correct 251 ms 23836 KB Output is correct
9 Correct 217 ms 22788 KB Output is correct
10 Correct 220 ms 22552 KB Output is correct
11 Correct 228 ms 22996 KB Output is correct
12 Correct 202 ms 21144 KB Output is correct
13 Correct 258 ms 22256 KB Output is correct
14 Correct 229 ms 24012 KB Output is correct
15 Correct 234 ms 22396 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 206 ms 21144 KB Output is correct
18 Correct 191 ms 21016 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 2 ms 4948 KB Output is correct
21 Execution timed out 3049 ms 28820 KB Time limit exceeded
22 Halted 0 ms 0 KB -