Submission #784048

#	Time	Username	Problem	Language	Result	Execution time	Memory
784048		Ozy	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	666 ms	62244 KiB

Main

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++)
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
//para el vector de querys
#define p second.first
#define id second.second

lli n,q,offset,apu,a,b,t,comp;
lli arr[MAX+2],p_arr[MAX+2]; //p_arr[i], poscion de numero i en el arreglo
vector<lli> res;
lli stree[MAX*4];
vector<pair<lli,pll> > querys;
pll sig[MAX+2];
stack<lli> pila;

void update(lli pos, lli ini, lli fin, lli l, lli r, lli val) {

    if (ini > r || fin < l) return;
    if (l <= ini && fin <= r) {
        stree[pos] = val;
        return;
    }

    lli mitad = (ini+fin)/2;
    update(pos*2,ini,mitad,l,r,val);
    update((pos*2)+1,mitad+1,fin,l,r,val);
    stree[pos] = stree[pos*2] + stree[(pos*2)+1];
}

lli suma(lli pos, lli ini, lli fin, lli l, lli r) {

    if (l > r) return 0;
    if (ini > r || fin < l) return 0;
    if (l <= ini && fin <= r) return stree[pos];

    lli a;
    lli mitad = (ini+fin)/2;
    a = suma(pos*2,ini,mitad,l,r);
    a += suma((pos*2)+1,mitad+1,fin,l,r);
    return a;
}

lli busca(lli pos, lli ini, lli fin, lli sum) {
    if (ini == fin) return ini;

    lli mitad = (ini+fin)/2;
    if (stree[pos*2] >= sum) return busca(pos*2,ini,mitad,sum);
    else return busca((pos*2)+1,mitad+1,fin,sum-stree[pos*2]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    res.resize(q+2);
    offset = 1;
    while (offset < n) offset *= 2;

    rep(i,1,n) {
        cin >> arr[i];
        p_arr[ arr[i] ] = i;
    }
    rep(i,1,q) {
        cin >> a >> b;
        if (a == 0) res[i] = arr[b];
        else querys.push_back({a,{b,i}});
    }
    sort(querys.begin(), querys.end());

    //pre proceso de monotone stacks
    //der a izq
    pila.push(n+1);
    repa(i,n,1) {
        while (pila.top() < arr[i]) pila.pop();
        sig[arr[i]].second = pila.top();
        pila.push(arr[i]);
    }

    // de izq a der
    while (!pila.empty()) pila.pop();
    pila.push(n+1);
    rep(i,1,n) {
        while (pila.top() < arr[i]) pila.pop();
        sig[arr[i]].first = pila.top();
        pila.push(arr[i]);
    }

    //activa los nodos y haz el primer shuffle
    lli mitad = (n/2);
    lli dif,s,pos = 1;

    p_arr[n+1] = n+1;
    arr[n+1] = n+1;
    while (pos <= n) {

        s = p_arr[ sig[arr[pos]].second ];
        if (pos <= mitad && s > mitad) s = mitad+1;
        dif = s - pos;

        update(1,1,offset,arr[pos],arr[pos],dif);

        pos = s;
    }

    apu = 0;
    t = 1;
    while (apu < querys.size()) {
        //responde querys

        while (apu < querys.size() && querys[apu].first == t) {
            a = busca(1,1,offset,querys[apu].p);
            b = suma(1,1,offset,1,a-1);

            b++;
            b = querys[apu].p - b;

            res[querys[apu].id] = arr[ p_arr[a] + b];
            apu++;
        }
        if (apu == querys.size()) break;

        //shuffle
        t++;
        a = busca(1,1,offset,(n/2)+1);
        b = suma(1,1,offset,1,a-1);

        if (b == (n/2)) {
            //se termino
            rep(i,apu,querys.size()-1) querys[i].first = t;
            continue;
        }

        dif = (n/2) - b;
        comp = stree[offset+a-1];
        pos = p_arr[a] + dif;
        update(1,1,offset,a,a,dif);

        while (pos < p_arr[a]+comp) {
            s = p_arr[ sig[arr[pos]].second ];
            if (s >= p_arr[a]+comp) s = p_arr[a]+comp;

            dif = s - pos;
            update(1,1,offset,arr[pos],arr[pos],dif);
            pos = s;
        }

    }

    rep(i,1,q) cout << res[i] << "\n";

    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:117:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     while (apu < querys.size()) {
      |            ~~~~^~~~~~~~~~~~~~~
Main.cpp:120:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         while (apu < querys.size() && querys[apu].first == t) {
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:130:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |         if (apu == querys.size()) break;
      |             ~~~~^~~~~~~~~~~~~~~~
Main.cpp:7:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(i,a,b) for(int i = (a); i <= (b); i++)
      |                                       ^
Main.cpp:139:13: note: in expansion of macro 'rep'
  139 |             rep(i,apu,querys.size()-1) querys[i].first = t;
      |             ^~~

• Subtask 1: 10 / 10
• Subtask 2: 40 / 40
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25