oj.uz

Submission #683449

# Submission time Handle Problem Language Result Execution time Memory
683449 2023-01-18T12:17:38 Z Tenis0206 Abracadabra (CEOI22_abracadabra) C++11
0 / 100
 13 ms 424 KB 
#include <bits/stdc++.h>

using namespace std;

struct queries
{
    int t,poz,cnt;
};

struct Node
{
    Node *st, *dr;
    int prior, sz;
    int val, Max;
};

int n,m;
int v[100005];
queries q[1000005];

Node nil[2];
Node *T = &nil[0];
Node *I = &nil[1];

int rez[1000005];

mt19937 my_rand(time(NULL));

Node *modfiu(Node *nod, bool care, Node *son)
{
    if(care==0)
    {
        nod -> st = son;
    }
    else
    {
        nod -> dr = son;
    }
    nod -> sz = nod -> st -> sz + 1 + nod -> dr -> sz;
    nod -> Max = nod -> val;
    nod -> Max = max(nod -> Max, nod->st->Max);
    nod -> Max = max(nod -> Max, nod->dr->Max);
    return nod;
}

Node *join(Node *st, Node *dr, bool care)
{
    if(st==&nil[care])
    {
        return dr;
    }
    if(dr==&nil[care])
    {
        return st;
    }
    if(st->prior >= dr->prior)
    {
        return modfiu(st,1,join(st->dr,dr,care));
    }
    else
    {
        return modfiu(dr,0,join(st,dr->st,care));
    }
}

pair<Node*,Node*> split(Node *nod, int k, bool care)
{
    if(nod==&nil[care])
    {
        return {&nil[care],&nil[care]};
    }
    if(nod->st->sz>=k)
    {
        auto t = split(nod->st,k,care);
        return {t.first,modfiu(nod,0,t.second)};
    }
    else
    {
        auto t = split(nod->dr,k - nod->st->sz - 1,care);
        return {modfiu(nod,1,t.first),t.second};
    }
}

pair<Node*,Node*> split_by_val(Node *nod, int val, bool care)
{
    if(nod==&nil[care])
    {
        return {&nil[care],&nil[care]};
    }
    if(nod->st->Max == val)
    {
        auto t = split(nod->st,val,care);
        return {t.first,modfiu(nod,0,t.second)};
    }
    else
    {
        auto t = split(nod->dr,val,care);
        return {modfiu(nod,1,t.first),t.second};
    }
}

int get_cnt_first(Node *nod, bool care)
{
    if(nod->st == &nil[care])
    {
        return nod -> sz;
    }
    return get_cnt_first(nod->st,care);
}

int query(int poz)
{
    auto t = split(T,poz-1,0);
    auto t2 = split(t.second,1,0);
    int val = t2.first -> val;
    T = join(t.first,join(t2.first,t2.second,0),0);
    return val;
}

int find_new_poz(int val)
{
    auto t = split_by_val(I,val,1);
    int rez = t.first -> sz;
    I = join(t.first,t.second,1);
    return rez;
}

bool next_perm()
{
    auto t = split(I,n/2,1);
    int first = t.first -> sz + 1;
    int cnt = get_cnt_first(t.second,1);
    auto t2 = split(t.second,cnt,1);
    t2.first -> sz = n / 2 - t.first -> sz;
    I = join(t.first,join(t2.first,t2.second,1),1);

    auto pref = split(T,n/2,0);
    auto buc = split(pref.second,first + cnt - 1 - (n / 2),0);
    /// pref.first = 1 - n / 2;
    /// buc.first = bucata mutata
    /// buc.second = sufixul sirului
    int poz = n / 2 + 1;
    bool ok = false;
    while(poz<=first+cnt-1)
    {
        int val = query(poz);
        auto aux = split_by_val(buc.first,val,0);
        int new_poz = find_new_poz(val);
        if(new_poz!=poz)
        {
            ok = true;
        }
        t = split(I,new_poz,1);
        I = join(t.first,join(new Node{&nil[1],&nil[1],my_rand(),aux.first -> sz,val,val},t.second,1),1);
        t = split(pref.first,new_poz,0);
        poz += aux.first -> sz;
        pref.first = join(t.first,join(aux.first,t.second,0),0);
        buc.first = aux.second;
    }
    T = join(pref.first,join(buc.first,buc.second,0),0);
    return ok;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
    cin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    for(int i=1; i<=m; i++)
    {
        cin>>q[i].t>>q[i].poz;
        q[i].cnt = i;
    }
    auto cmp = [](queries a, queries b)
    {
        return a.t < b.t;
    };
    sort(q+1,q+m+1,cmp);
    int first = v[1];
    int nr = 0;
    for(int i=1; i<=n; i++)
    {
        if(v[i] > first || i == n / 2 + 1)
        {
            if(i!=1)
            {
                I = join(I,new Node{&nil[1],&nil[1],my_rand(),nr,first,first},1);
            }
            first = v[i];
            nr = 0;
        }
        ++nr;
        T = join(T,new Node{&nil[0],&nil[0],my_rand(),1,v[i],v[i]},0);
    }
    int poz = 1;
    while(q[poz].t == 0)
    {
        rez[q[poz].cnt] = query(q[poz].poz);
        ++poz;
    }
    for(int t=1; t<=n; t++)
    {
        bool ok = next_perm();
        if(!ok)
        {
            break;
        }
        while(poz<=m && q[poz].t==t)
        {
            rez[q[poz].cnt] = query(q[poz].poz);
            ++poz;
        }
    }
    for(int i=poz; i<=m; i++)
    {
        rez[q[i].cnt] = query(q[i].poz);
    }
    for(int i=1; i<=m; i++)
    {
        cout<<rez[i]<<'\n';
    }
    return 0;
}

Compilation message

Main.cpp: In function 'bool next_perm()':
Main.cpp:154:63: warning: narrowing conversion of 'my_rand.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]
  154 |         I = join(t.first,join(new Node{&nil[1],&nil[1],my_rand(),aux.first -> sz,val,val},t.second,1),1);
      |                                                        ~~~~~~~^~
Main.cpp: In function 'int main()':
Main.cpp:193:60: warning: narrowing conversion of 'my_rand.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]
  193 |                 I = join(I,new Node{&nil[1],&nil[1],my_rand(),nr,first,first},1);
      |                                                     ~~~~~~~^~
Main.cpp:199:52: warning: narrowing conversion of 'my_rand.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]
  199 |         T = join(T,new Node{&nil[0],&nil[0],my_rand(),1,v[i],v[i]},0);
      |                                             ~~~~~~~^~
Main.cpp:168:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  168 |     freopen("nr.in","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
Main.cpp:169:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |     freopen("nr.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 420 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 408 KB Output isn't correct
2 Halted 0 ms 0 KB -