Submission #1038404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038404		underwaterkillerwhale	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	490 ms	67136 KiB

Main

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N = 2e5 + 7;
const int Mod = 1e9 + 7;
const int szBL = 240;
const int INF = 1e9 + 7;
const int BASE = 137;

struct fenwick_Tree {
    int m;
    int fen[N];

    void init (int n) {
        m = n;
    }
    void update (int pos, int val) {
        for (;pos <= m; pos += pos & -pos) fen[pos] += val;
    }
    int get (int pos) {
        int res = 0;
        for (;pos > 0; pos -= pos & -pos) res += fen[pos];
        return res;
    }
}fen;

int n, Q;
int a[N];
pair<int,int> itv[N];
vector<pair<int,int>> qr[N];
int spt[N][25];
int Ans[(int)1e6 + 7];

void solution () {
    cin >> n >> Q;
    rep (i, 1, n) cin >> a[i];

    fen.init(n);

    rep (i, 1, n) spt[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            spt[i][j] = max(spt[i][j - 1], spt[i + (1 << j - 1)][j - 1]);

    auto get = [] (int L, int R) {
        assert(L <= R);
        int K = 31 - __builtin_clz(R - L + 1);
        return max(spt[L][K], spt[R - (1 << K) + 1][K]);
    };

    auto get_bound = [&] (int pos, int R) {
        int lf = pos, rt = R;
        while (lf < rt) {
            int mid = lf + rt + 1 >> 1;
            if (get(pos, mid) == a[pos]) lf = mid;
            else rt = mid - 1;
        }
        return lf;
    };

    rep (i, 1, n) {
        int bound = get_bound(i, n);
        itv[a[i]] = {i, bound};
        fen.update (a[i], bound - i + 1);
        i = bound;
    }

    rep (i, 1, Q) {
        int T, p;
        cin >> T >> p;
        T = min(T, n);
        qr[T].push_back({p, i});
    }

    auto get_val = [] (int p) {
        int lf = 1, rt = n;
        while (lf < rt) {
            int mid = lf + rt >> 1;
            if (fen.get(mid) >= p) rt = mid;
            else lf = mid + 1;
        }
        return lf;
    };

    auto simulation = [&] (int p) {
        int val = get_val(p);
        int L = itv[val].fs, R = itv[val].se;
//        cout << val <<"hihi\n";
        if (p - fen.get(val - 1) == 1)
            return;
        int np = L + p - fen.get(val - 1) - 1;
//        cout << np <<" aa\n";
        fen.update(val, - (R - np + 1));
        itv[val] = {L, np - 1};
        rep (i, np, R) {
            int bound = get_bound(i, R);
            itv[a[i]] = {i, bound};
            fen.update(a[i], bound - i + 1);
            i = bound;
        }
    };

    rep (i, 0, n) {
//        cout << i <<":\n";
//        rep (i, 1, n) cout << a[i] <<" "<<itv[a[i]].fs<<" "<<itv[a[i]].se    <<"\n";
        iter (&id, qr[i]) {
            int val = get_val(id.fs);
//            cout << id.se <<" "<<id.fs<<" "<<val<<" "<<itv[val].fs<<" "<<itv[val].se<<" "<<fen.get(4)<<"qr\n";
            Ans[id.se] = a[itv[val].fs + id.fs - fen.get(val - 1) - 1];

        }
        simulation(n / 2 + 1);
    }
    rep (i, 1, Q) {
        cout << Ans[i] <<"\n";
    }


}

#define file(name) freopen(name".inp", "r", stdin); \
freopen(name".out", "w", stdout);
/*
*/
int main () {
//    file("c");
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll num_Test = 1;
//    cin >> num_Test;
    while(num_Test--)
        solution();
}
/*
no bug challenge +2
6
25 18 40 37 29 95 41 53 39 69 61 90
14 18 22 28 18 30 32 32 63 58 71 78

*/

Compilation message (stderr)

Main.cpp: In function 'void solution()':
Main.cpp:59:60: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   59 |             spt[i][j] = max(spt[i][j - 1], spt[i + (1 << j - 1)][j - 1]);
      |                                                          ~~^~~
Main.cpp: In lambda function:
Main.cpp:70:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |             int mid = lf + rt + 1 >> 1;
      |                       ~~~~~~~~^~~
Main.cpp: In lambda function:
Main.cpp:94:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |             int mid = lf + rt >> 1;
      |                       ~~~^~~~

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