oj.uz

답안 #965412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965412 2024-04-18T13:05:08 Z efedmrlr Abracadabra (CEOI22_abracadabra) C++17
40 / 100
 235 ms 46404 KB 
// #pragma GCC optimize("O3,Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;


#define lli long long int
#define MP make_pair
#define pb push_back
#define REP(i,n) for(int i = 0; (i) < (n); (i)++)
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()


void fastio() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}


const double EPS = 0.00001;
const int INF = 1e9+500;
const int N = 3e5+5;
const int ALPH = 26;
const int LGN = 25;
constexpr int MOD = 1e9+7;
int n,m,q;

struct SegT {
    vector<int> data;
    int sz;
    void reset(int s) {
        sz = s;
        data.assign(4*(sz + 3), 0);
    }
    void update(int tl, int tr, int v, int ind, int val) {
        if(tl == tr) {
            data[v] += val;
            return;
        }
        int tm = (tl + tr) >> 1;
        if(ind <= tm) {
            update(tl, tm, v << 1, ind, val);
        }
        else {
            update(tm + 1, tr, v << 1 ^ 1, ind, val);
        }
        data[v] = data[v << 1] + data[v << 1 ^ 1];
    }
    void update(int ind, int val) {
        update(0, sz, 1, ind, val);
    }
    int query(int tl, int tr, int v, int val) {
        if(tl == tr) {
            return tl;
        }   
        int tm = (tl + tr) >> 1;
        if(val <= data[v << 1]) {
            return query(tl, tm, v << 1, val);
        } 
        else {
            return query(tm + 1, tr, v << 1 ^ 1, val - data[v << 1]);
        }
    }
    int query(int val) {
        return query(0, sz, 1, val);
    }
};  


vector<int> a, nxt;
vector<array<int,3> > comp;
set<array<int,3> > st;
vector<int> fin;
vector<array<int,3> > qu;
int tot = 0;
void calcn() {
    a[n + 1] = INF;
    vector<array<int,2> > tmp;
    for(int i = 1; i<=n + 1; i++) {
        while(tmp.size() && tmp.back()[0] < a[i]) {
            nxt[tmp.back()[1]] = i;
            tmp.pop_back();
        }
        tmp.pb({a[i], i});
    }

}   
int itr;
int t = 0;
void get_fin(array<int,3> bl) {
    // cout << bl[0] << " " << bl[1] << " " << bl[2] << endl;
    for(int i = bl[2]; i >= bl[1]; i--) {
        fin[itr--] = a[i]; 
    }
}
void prt() {
    for(auto c : st) {
        cout << c[0] << " " << c[1] << " " << c[2] << "\n";
    }
}
void get_comp() {
    if(qu[0][0] == 0) return; // TODO
    for(int l = 1; l <= n / 2;) {
        int r = min(n / 2, nxt[l] - 1);
        st.insert({a[l], l, r});
        comp.pb({a[l], l, r});
        tot += r - l + 1;
        l = nxt[l];
    }
    for(int l = n / 2 + 1; l <= n;) {
        int r = nxt[l] - 1;
        st.insert({a[l], l, r});
        comp.pb({a[l], l, r});
        tot += r - l + 1;
        l = nxt[l];
    }
    t++;
    bool f1 = 1;
    while(f1) {
        // prt();
        // cout << "round" << t << endl;
        // cout << "tot:" << tot << "\n";

        if(st.empty()) break;
        if(t == qu[0][0]) break;
        auto last = st.end(); last--;
        while(tot - ((*last)[2] - (*last)[1] + 1) >= n / 2) {
            tot -= ((*last)[2] - (*last)[1] + 1);
            get_fin(*last);  // TODO
            
            st.erase(last);            
            assert(st.size() != 0);
            last = st.end(); last--;
        }
        auto el = *last;
        if(tot == n / 2) break;
        int len = el[2] - el[1] + 1;
        tot -= ((*last)[2] - (*last)[1] + 1);
        st.erase(last); 
        int ext = tot + len - n / 2;

        st.insert({el[0], el[1], el[2] - ext});
        comp.pb({el[0], el[1], el[2] - ext});
        tot += el[2] - ext - el[1] + 1;
        for(int l = el[2] - ext + 1; l <= el[2];) {
            int r = min(el[2], nxt[l] - 1);
            st.insert({a[l], l, r});
            tot += r - l + 1;
            comp.pb({a[l], l, r});
            l = nxt[l];
        } 
        t++;
    }
    while(st.size()) { // TODO
        auto x = prev(st.end());
        get_fin(*x);
        st.erase(x);
    }
    sort(all(comp));

}

inline void solve() {
    cin>>n>>q;
    a.resize(n + 2);
    nxt.resize(n + 1);
    fin.assign(n + 1, 0);
    qu.resize(q);
    itr = n;
    for(int i = 1; i<=n; i++) {
        cin >> a[i];
    }
    REP(i, q) {
        cin >> qu[i][0] >> qu[i][1];
        qu[i][2] = i;
    }
    // sort(all(qu));
    calcn();
    get_comp();
    for(int i = 0; i < q; i++) {
        if(qu[i][0] == 0) cout << a[qu[i][1]] << "\n";
        else {
            cout << fin[qu[i][1]] << "\n";
        }
    }
}
 
signed main() {

    fastio();
    int test = 1;
    //cin>>test;
    while(test--) {
        solve();
    }
    
}

Subtask #1
0 / 10.0

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

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 225 ms 42664 KB Output is correct
2 Correct 235 ms 46404 KB Output is correct
3 Correct 195 ms 35808 KB Output is correct
4 Correct 167 ms 30724 KB Output is correct
5 Correct 196 ms 32704 KB Output is correct
6 Correct 164 ms 29444 KB Output is correct
7 Correct 228 ms 36316 KB Output is correct
8 Correct 195 ms 35092 KB Output is correct
9 Correct 186 ms 31488 KB Output is correct
10 Correct 187 ms 32404 KB Output is correct
11 Correct 145 ms 26452 KB Output is correct
12 Correct 161 ms 26968 KB Output is correct
13 Correct 179 ms 31312 KB Output is correct
14 Correct 160 ms 27732 KB Output is correct
15 Correct 220 ms 32864 KB Output is correct
16 Correct 18 ms 3920 KB Output is correct
17 Correct 157 ms 29268 KB Output is correct
18 Correct 134 ms 24284 KB Output is correct
19 Correct 47 ms 9040 KB Output is correct
20 Correct 56 ms 10824 KB Output is correct

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

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