oj.uz

답안 #662258

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
662258 2022-11-26T07:57:39 Z fatemetmhr Abracadabra (CEOI22_abracadabra) C++17
0 / 100
 356 ms 39536 KB 
// heiy ... ye rooze jadid ...

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

const int maxn5 = 1e6 + 10;
const int maxnt = 1e6 + 10;

int sum[maxnt], a[maxn5], rev[maxn5], out[maxn5], per[maxn5];
int rig[maxn5], sz[maxn5], t[maxn5], ind[maxn5];
bool mark[maxn5];
vector <int> av;

inline bool cmp(int i, int j){return t[i] < t[j];}

void upd(int l, int r, int id, int val, int v){
    if(r - l == 1){
        sum[v] = val;
        return;
    }
    int mid = (l + r) >> 1;
    if(id < mid)
        upd(l, mid, id, val, v * 2);
    else
        upd(mid, r, id, val, v * 2 + 1);
    sum[v] = sum[v * 2] + sum[v * 2 + 1];
}

pair<int, int> find_first(int l, int r, int val, int v){
    if(r - l == 1)
        return {l, sum[v]};
    int mid = (l + r) >> 1;
    if(sum[v * 2] >= val)
        return find_first(l, mid, val, v * 2);
    auto ans = find_first(mid, r, val - sum[v * 2], v * 2 + 1);
    return {ans.fi, ans.se + sum[v * 2]};
}


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

    int n, q; cin >> n >> q;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        a[i]--;
        rev[a[i]] = i;
    }
    for(int i = 0; i < q; i++){
        cin >> t[i] >> ind[i];
        per[i] = i;
    }
    fill(rig, rig + n + 10, n);
    for(int i = n - 1; i >= 0; i--){
        while(av.size() && a[av.back()] < a[i])
            av.pop_back();
        if(av.size())
            rig[i] = av.back();
        av.pb(i);
    }

    for(int i = 0; i != n; i = rig[i]){
        upd(0, n, a[i], rig[i] - i, 1);
        sz[i] = rig[i] - i;
        mark[i] = true;
        //cout << "ok " << i << ' ' << rig[i] << ' ' << sz[i] << endl;
    }


    sort(per, per + q, cmp); // bar hasbe t[i]

    int done = 0;
    bool re = false;

    for(int i = 0; i < q; i++){
        while(done < t[per[i]] && !re){
            done++;
            auto tmp = find_first(0, n, n / 2, 1);
            int p = tmp.fi, r = tmp.se - n / 2;
            if(r == 0){
                re = true;
                break;
            }
            int v = rev[p] + sz[rev[p]] - r;
            //cout << "now " << done << ' ' << p << ' ' << r << ' ' << v << ' ' << rev[p] << ' ' << sz[rev[p]] << ' ' << tmp.se << endl;
            sz[rev[p]] -= r;
            upd(0, n, p, sz[rev[p]], 1);
            for(; !mark[v] && v != n ; v = rig[v]){
                mark[v] = true;
                sz[v] = rig[v] - v;
                upd(0, n, a[v], sz[v], 1);
            }
        }
        auto tmp = find_first(0, n, ind[per[i]], 1);
        int p = tmp.fi, r = tmp.se - ind[per[i]];
        r = sz[rev[p]] - r - 1;
        out[per[i]] = a[rev[p] + r] + 1;
    }

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

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 356 ms 19788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 344 ms 39536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 64 ms 4788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 356 ms 19788 KB Output isn't correct
2 Halted 0 ms 0 KB -