Submission #635642

#	Time	Username	Problem	Language	Result	Execution time	Memory
635642		welleyth	Abracadabra (CEOI22_abracadabra)	C++17	35 / 100	3038 ms	37088 KiB

Main

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

//#define int long long
#define mp make_pair
#define pb push_back

using namespace std;
using namespace __gnu_pbds;
mt19937 rnd(time(nullptr));

constexpr int N = (int)1e6 + 111;

int tr[N];
int SUM = 0;
void upd(int r,int x){
    SUM += x;
    for(int i = r; i < N; i |= i+1)
        tr[i] += x;
    return;
}
int get(int r){
    int s = 0;
    for(int i = r; i >= 0; i&=i+1,i--)
        s += tr[i];
    return s;
}
int getSuf(int r){
    return SUM - get(r-1);
}
int a[N];
int t[N],P[N];
int n = 20,q = 20;

vector<int> brute(){
    int b[n];
    vector<int> ans;
    int A[n+1][n];
    for(int i = 0; i < n; i++){
        A[0][i] = a[i];
        b[i] = a[i];
    }
    int cnt = 0;
    for(int i = 1;; i++){
        int ptr[2] = {0,n/2};
        int pos = 0;
        while(ptr[0] < n/2 && ptr[1] < n){
            if(A[i-1][ptr[0]] < A[i-1][ptr[1]]){
                A[i][pos++] = A[i-1][ptr[0]++];
            } else {
                A[i][pos++] = A[i-1][ptr[1]++];
            }
        }
        while(ptr[0] < n/2) A[i][pos++] = A[i-1][ptr[0]++];
        while(ptr[1] < n) A[i][pos++] = A[i-1][ptr[1]++];
        bool diff = false;
        for(int j = 0; j < n; j++){
            diff |= A[i-1][j] != A[i][j];
        }
        cnt++;
        if(!diff)
            break;
    }
    for(int i = 0; i < q; i++){
        t[i] = min(t[i],cnt);
        ans.pb(A[t[i]][P[i]-1]);
    }
    return ans;
}

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> st;
int parent[N];
vector<pair<int,pair<int,int>>> Q;
int ans[N];

void __attribute__ (( optimize("Ofast","unroll-loops"), target("avx2") )) solve(){
    n = (int)10000, q = (int)10000;
    for(int i = 0; i <= n; i++) tr[i] = 0;
    st.clear();
    SUM = 0;
    Q.clear();
    cin >> n >> q;
    int rv[n+1];
    for(int i = 0; i < n; i++){
        cin >> a[i];
        rv[a[i]] = i;
    }
    int nxt[n+1];
    vector<pair<int,int>> RightBiggest;
    for(int i = n-1; i >= 0; i--){
        while(!RightBiggest.empty() && RightBiggest.back().first < a[i])
            RightBiggest.pop_back();
        if(!RightBiggest.empty())
            nxt[i] = RightBiggest.back().second;
        else
            nxt[i] = n;
        RightBiggest.pb(mp(a[i],i));
    }
    for(int i = 0; i < q; i++){
        cin >> t[i] >> P[i];
        Q.pb(mp(t[i],mp(P[i],i)));
    }
    sort(Q.begin(),Q.end());
    vector<pair<int,int>> v;
    bool used[n+1];
    for(int i = 0; i <= n; i++){
        used[i] = false;
    }
    for(int i = 0; i < n; i++){
        if(used[i])
            continue;
        int __r = nxt[i];
        if(i < n/2)
            __r = min(__r,n/2);
        for(int j = i; j < __r; j++) used[j] = 1;
        st.insert(mp(a[i],__r-i));
        upd(a[i],__r-i);
    }
//    cout << "st:\n";
//    for(auto&[x,y] : st){
//        cout << x << " " << y << "\n";
//    }
    int cur_t = 1;
    bool all = false;
    for(auto& query : Q){
        int& t = query.first;
        int& pos = query.second.first;
        int& id = query.second.second;
        if(t == 0){
            ans[id] = a[pos-1];
            continue;
        }
        while(!all && cur_t < t){
            int l = 0, r = st.size();
            while(r - l > 1){
                int m = (l+r)>>1;
                int x = st.find_by_order(m)->first;
                int tl = getSuf(x);
                if(tl > n/2)
                    l = m;
                else
                    r = m;
            }
            int x = st.find_by_order(l)->first;
            int y = st.find_by_order(l+1)->first;
            int tr = getSuf(y);
            if(n/2 - tr <= 0){
                all = true;
                break;
            }
            int delta = n/2 - tr;
            int __len = st.find_by_order(l)->second;
            int __pos = rv[x] + __len - delta;
            upd(x,-delta);
            st.erase(mp(x,__len));
            st.insert(mp(x,__len-delta));
            while(__pos < rv[x] + __len){
                int __r = min(nxt[__pos],rv[x] + __len);
                st.insert(mp(a[__pos],__r - __pos));
                upd(a[__pos],__r-__pos);
                __pos = __r;
            }
            cur_t++;
        }
        int l = 0, r = st.size();
        while(r - l > 1){
            int m = (l+r)>>1;
            int x = st.find_by_order(m)->first;
            if(getSuf(x) >= n - pos + 1)
                l = m;
            else
                r = m;
        }
        int x = st.find_by_order(l)->first;
        int sz = st.find_by_order(l)->second;
        int suffSum = 0;
        if(l + 1 != st.size()){
            int y = st.find_by_order(l+1)->first;
            suffSum = getSuf(y);
        }
        int cur_pos = (n - pos + 1) - suffSum;
//        cerr << "suffSum = " << suffSum << "\n";
        cur_pos = sz - cur_pos;
        int __pos = rv[x];
//        cerr << x << " " << sz << "\n";
//        cerr << "__pos = " << __pos << "\n";
//        cerr << "cur_pos = " << cur_pos << "\n";
        ans[id] = a[__pos + cur_pos];
//        cerr << "st:\n";
//        for(auto&[x,y] : st){
//            cerr << x << " " << y << "\n";
//        }
    }
    for(int i = 0; i < q; i++){
        cout << ans[i] << "\n";
    }
    return;
}

signed main(){
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int tests = 1;
//    cin >> tests;
    for(int test = 1; test <= tests; test++){
        solve();
    }
    return 0;
}
/**
6 1
2 1 5 4 6 3
1 1

2 1 4 5 6 3

6 1
1 5 6 2 3 4
1 2

10 1
7 5 2 9 10 8 4 3 6 1
3 4

7 5 2 || 8 4 3 6 1 || 9 || 10
3 || 6 1 || 7 5 2 || 8 4 || 9 || 10
2 || 3 || 6 1 || 7 5 || 8 4 || 9 || 10

**/

Compilation message (stderr)

Main.cpp: In function 'std::vector<int> brute()':
Main.cpp:37:9: warning: variable 'b' set but not used [-Wunused-but-set-variable]
   37 |     int b[n];
      |         ^
Main.cpp: In function 'void solve()':
Main.cpp:178:18: warning: comparison of integer expressions of different signedness: 'int' and '__gnu_pbds::detail::bin_search_tree_set<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::detail::tree_traits<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::tree_order_statistics_node_update, __gnu_pbds::rb_tree_tag, std::allocator<char> >, std::allocator<char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |         if(l + 1 != st.size()){
      |            ~~~~~~^~~~~~~~~~~~

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