Submission #688334

#	Time	Username	Problem	Language	Result	Execution time	Memory
688334		ksjsjsjsjsjsjs	Abracadabra (CEOI22_abracadabra)	C++14	100 / 100	646 ms	61304 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define bg begin
#define ed end
#define ft front
#define bk back
#define ins insert
#define ers erase
#define sz(x) (int)(x).size()
#define all(x) (x).bg(), (x).ed()
#define mtp make_tuple
#define ll long long
#define ull unsigned long long
#define db double
#define ldb long double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define FOS(i, r, l) for (int i = (r); i >= (l); --i)
#define FRN(i, n) for (int i = 0; i < (n); ++i)
#define FSN(i, n) for (int i = (n) - 1; i >= 0; --i)
#define EACH(i, x) for (auto &i : (x))
#define WHILE while
template<typename T> T gcd(T a, T b) { WHILE(b) { a %= b; swap(a, b); } return b; }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
#define file "TEST"
mt19937 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 oo = 1e9 + 5;
const int N = 2e5 + 5;
const int Q = 1e6 + 5;
int n, q, a[N], f[N], opos[N], maxx[N][18], LOG[N], ans[Q];
vpi d[N];
void upd(int pos, int v) { for (int i = pos; i <= n; i += (i & -i)) f[i] += v; }
int get(int pos) { int rs = 0; for (int i = pos; i > 0; i -= (i & -i)) rs += f[i]; return rs; }
void build() {
    FOR(i, 1, n) {
        maxx[i][0] = a[i];
        LOG[i] = log2(i);
    }
    FOR(j, 1, 17)
    FOR(i, 1, n) {
        if (i + (1 << j) - 1 > n) continue;
        maxx[i][j] = max(maxx[i][j - 1], maxx[i + (1 << (j - 1))][j - 1]);
    }
}
int getm(int l, int r) {
    int len = LOG[r - l + 1];
    return max(maxx[l][len], maxx[r - (1 << len) + 1][len]);
}
int lbound(int x) {
    int pos = 0, num = 0, ans = oo;
    FSN(i, 18) {
        if (pos + (1 << i) > n) continue;
        if (num + f[pos + (1 << i)] >= x) ans = min(ans, pos + (1 << i));
        else {
            pos |= 1 << i;
            num += f[pos];
        }
    }
    return ans;
}
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen(file".inp", "r", stdin);
//    freopen(file".out", "w", stdout);
    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> a[i];
        opos[a[i]] = i;
    }
    FOR(j, 1, q) {
        int t, i;
        cin >> t >> i;
        t = min(t, n);
        d[t].pb({j, i});
    }
    FOR(i, 1, n) {
        int j = i;
        WHILE(j <= n && a[j] <= a[i]) ++j;
        --j;
        upd(a[i], j - i + 1);
        i = j;
    }
    build();
    FOR(i, 0, n) {
        EACH(j, d[i]) {
            int id = j.st, z = j.nd, pos = lbound(z), op = opos[pos] + z - get(pos - 1) - 1;
            ans[id] = a[op];
        }
        int pos = lbound(n / 2), num = get(pos) - get(pos - 1), sum = get(pos);
        if (sum > n / 2) {
            upd(pos, n / 2 - sum);
            int cur = opos[pos] + n / 2 - get(pos - 1);
            WHILE(cur <= opos[pos] + num - 1) {
                int l = cur, r = opos[pos] + num - 1, nxt = -1;
                WHILE(l <= r) {
                    int mid = l + (r - l) / 2;
                    if (getm(cur, mid) <= a[cur]) {
                        nxt = mid;
                        l = mid + 1;
                    }
                    else r = mid - 1;
                }
                upd(a[cur], nxt - cur + 1);
                cur = nxt + 1;
            }
        }
    }
    FOR(i, 1, q) cout << ans[i] << '\n';
//    cerr << "\nTime: " << setprecision(5) << fixed << (ldb)clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

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