oj.uz

Submission #867076

# Submission time Handle Problem Language Result Execution time Memory
867076 2023-10-27T16:35:56 Z Lalic Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 318 ms 31484 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 2e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9+7;

int tree[4*MAXN];

void upd(int node, int l, int r, int pos, int val){
    if(r<pos || l>pos)
        return;
    if(l==r){
        tree[node]=val;
        return;
    }

    int mid=(l+r)/2;

    upd(node*2, l, mid, pos, val);
    upd(node*2+1, mid+1, r, pos, val);

    tree[node]=tree[node*2]+tree[node*2+1];
}

pii search(int node, int l, int r, int val){
    if(l==r)
        return {l, tree[node]};

    int mid=(l+r)/2;

    if(tree[node*2]>=val)
        return search(node*2, l, mid, val);
    
    pii resp=search(node*2+1, mid+1, r, val-tree[node*2]);
    return {resp.fi, resp.se+tree[node*2]};
}

void solve(){
    int n, q; cin >> n >> q;

    vector<int> arr(n);
    for(int i=0;i<n;i++)
        cin >> arr[i];

    vector<pair<pii, int>> query(q);
    for(int i=0;i<q;i++)
        cin >> query[i].fi.fi >> query[i].fi.se, query[i].se=i;

    sort(all(query));
    vector<int> ans(q);

    vector<int> rev(n+1);
    for(int i=0;i<n;i++)
        rev[arr[i]]=i;

    int cnt=0;
    bool foi=0;

    vector<int> nx(n+1);
    set<pii> act;
    for(int i=0;i<n;i++){
        auto curr=act.begin();

        while(curr!=act.end() && curr->fi<arr[i]){
            nx[curr->fi]=i-curr->se;
            curr=act.erase(curr);
        }

        act.insert({arr[i], i});
    }

    for(auto u : act)
        nx[u.fi]=n-u.se;

    vector<int> sz(n+1, 0);
    for(int i=0;i<n;i++){
        sz[arr[i]]=nx[arr[i]];
        upd(1, 1, n, arr[i], nx[arr[i]]);
        i+=(nx[arr[i]]-1);
    }

    for(int i=0;i<q;i++){
        while(!foi && cnt<query[i].fi.fi){
            pii curr=search(1, 1, n, n/2+1);

            if(curr.se-sz[curr.fi]>=n/2){
                foi=1;
                break;
            }

            int nwsize=n/2-curr.se+sz[curr.fi];

            upd(1, 1, n, curr.fi, nwsize);
            sz[curr.fi]=nwsize;

            int ptr=rev[curr.fi]+nwsize;
            while(ptr<n && arr[ptr]<curr.fi){
                upd(1, 1, n, arr[ptr], nx[arr[ptr]]);
                sz[arr[ptr]]=nx[arr[ptr]];
                ptr+=nx[arr[ptr]];
            }
            
            cnt++;
        }

        pii resp=search(1, 1, n, query[i].fi.se);
        ans[query[i].se]=arr[rev[resp.fi]+query[i].fi.se-(resp.se-sz[resp.fi]+1)];
    }

    for(int i=0;i<q;i++)
        cout << ans[i] << "\n";
}

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

    int tt=1;
    // cin >> tt;
    while(tt--)
        solve();
    return 0;
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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