Submission #679168

#	Time	Username	Problem	Language	Result	Execution time	Memory
679168		Lobo	Abracadabra (CEOI22_abracadabra)	C++17	100 / 100	653 ms	47668 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const long long inf = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()
const int maxn = 2e5+10;
const int maxq = 1e6+10;

int n, q, tra[4*maxn], trsz[4*maxn], a[maxn], pos[maxn], sz[maxn];
vector<pair<int,int>> qrys[maxn];
int ans[maxq];

void builda(int no, int l, int r) {
    if(l == r) {
        tra[no] = a[l];
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    builda(lc,l,mid);
    builda(rc,mid+1,r);
    tra[no] = max(tra[lc],tra[rc]);
}

int qrya(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) return tra[no];
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return max(qrya(lc,l,mid,L,R),qrya(rc,mid+1,r,L,R));
}

void updsz(int no, int l, int r, int pos, int val) {
    if(l > pos || r < pos) return;
    if(l == r) {
        trsz[no] = val;
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    updsz(lc,l,mid,pos,val);
    updsz(rc,mid+1,r,pos,val);
    trsz[no] = trsz[lc]+trsz[rc];
}
int qrysz(int no, int l, int r, int L, int R) {
    if(l > R || r < L) return 0;
    if(l >= L && r <= R) return trsz[no];
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    return qrysz(lc,l,mid,L,R)+qrysz(rc,mid+1,r,L,R);
}


void adjust(int x) {
    int l = pos[x];
    int r = pos[x]+sz[x]-1;
    auto mx = qrya(1,1,n,l,r);
    if(mx == x) return;
    sz[x] = pos[mx]-pos[x];
    updsz(1,1,n,x,sz[x]);
    sz[mx] = r-pos[mx]+1;
    updsz(1,1,n,mx,sz[mx]);
    adjust(x);
}

//last one with sum <= n/2
void cut(int no, int l, int r, int val) {
    if(l == r) {
        if(val == sz[l]) return;
        int x = a[pos[l]+val];
        sz[x] = pos[l]+sz[l]-1-pos[x]+1;
        updsz(1,1,n,x,sz[x]);
        sz[l] = val;
        updsz(1,1,n,l,sz[l]);
        adjust(x);
        return;
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    if(val-trsz[lc] <= 0) cut(lc,l,mid,val);
    else cut(rc,mid+1,r,val-trsz[lc]);
}

int find(int no, int l, int r, int val) {
    if(l == r) {
        return a[pos[l]+val-1];
    }
    int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
    if(val-trsz[lc] <= 0) return find(lc,l,mid,val);
    else return find(rc,mid+1,r,val-trsz[lc]);
}
void solve() {
    cin >> n >> q;

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    builda(1,1,n);

    sz[a[1]] = n;
    updsz(1,1,n,a[1],sz[a[1]]);
    adjust(a[1]);

    for(int i = 1; i <= q; i++) {
        int t,j; cin >> t >> j;
        if(t > n) t = n;
        qrys[t].pb(mp(j,i));
    }

    for(int i = 0; i <= n; i++) {
        for(auto X : qrys[i]) {
            int id = X.sc;
            int j = X.fr;
            ans[id] = find(1,1,n,j);
        }

        cut(1,1,n,n/2);
    }

    for(int i = 1; i <= q; i++) {
        cout << ans[i] << endl;
    }
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    // cin >> tt;
    while(tt--) {
        solve();
    }

}

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