oj.uz

Submission #773955

# Submission time Handle Problem Language Result Execution time Memory
773955 2023-07-05T09:55:36 Z Valters07 Abracadabra (CEOI22_abracadabra) C++14
10 / 100
 3000 ms 31520 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 == 0) 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};
    }
}
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");
    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])
            {
                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)
            {
                auto t1 = splitbysize(t.se,1);
                int val = treap[t1.fi].val;
                auto t2 = splitbymax(merg(t1.fi,t1.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 625 ms 23088 KB Output is correct
2 Correct 620 ms 29328 KB Output is correct
3 Correct 563 ms 28700 KB Output is correct
4 Correct 479 ms 27424 KB Output is correct
5 Correct 526 ms 31040 KB Output is correct
6 Correct 489 ms 30440 KB Output is correct
7 Correct 537 ms 31520 KB Output is correct
8 Correct 468 ms 29164 KB Output is correct
9 Correct 480 ms 28004 KB Output is correct
10 Correct 481 ms 27828 KB Output is correct
11 Correct 460 ms 28172 KB Output is correct
12 Correct 406 ms 25552 KB Output is correct
13 Correct 498 ms 26988 KB Output is correct
14 Correct 501 ms 29636 KB Output is correct
15 Correct 513 ms 27600 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 239 ms 25852 KB Output is correct
18 Correct 323 ms 25732 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 3075 ms 28536 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 3069 ms 11120 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 625 ms 23088 KB Output is correct
2 Correct 620 ms 29328 KB Output is correct
3 Correct 563 ms 28700 KB Output is correct
4 Correct 479 ms 27424 KB Output is correct
5 Correct 526 ms 31040 KB Output is correct
6 Correct 489 ms 30440 KB Output is correct
7 Correct 537 ms 31520 KB Output is correct
8 Correct 468 ms 29164 KB Output is correct
9 Correct 480 ms 28004 KB Output is correct
10 Correct 481 ms 27828 KB Output is correct
11 Correct 460 ms 28172 KB Output is correct
12 Correct 406 ms 25552 KB Output is correct
13 Correct 498 ms 26988 KB Output is correct
14 Correct 501 ms 29636 KB Output is correct
15 Correct 513 ms 27600 KB Output is correct
16 Correct 4 ms 5076 KB Output is correct
17 Correct 239 ms 25852 KB Output is correct
18 Correct 323 ms 25732 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 3075 ms 28536 KB Time limit exceeded
22 Halted 0 ms 0 KB -