oj.uz

Submission #635642

# Submission time Handle Problem Language Result Execution time Memory
635642 2022-08-26T14:45:27 Z welleyth Abracadabra (CEOI22_abracadabra) C++17
35 / 100
 3000 ms 37088 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 28448 KB Output is correct
2 Correct 771 ms 28464 KB Output is correct
3 Correct 783 ms 27344 KB Output is correct
4 Correct 415 ms 27096 KB Output is correct
5 Correct 553 ms 28292 KB Output is correct
6 Correct 523 ms 27096 KB Output is correct
7 Correct 562 ms 28468 KB Output is correct
8 Correct 520 ms 27356 KB Output is correct
9 Correct 569 ms 27104 KB Output is correct
10 Correct 582 ms 27516 KB Output is correct
11 Correct 512 ms 27540 KB Output is correct
12 Correct 441 ms 27124 KB Output is correct
13 Correct 474 ms 27612 KB Output is correct
14 Correct 549 ms 27804 KB Output is correct
15 Correct 503 ms 28444 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 353 ms 27540 KB Output is correct
18 Correct 351 ms 27304 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 392 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3038 ms 37088 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 778 ms 11724 KB Output is correct
2 Correct 573 ms 12292 KB Output is correct
3 Correct 677 ms 11720 KB Output is correct
4 Correct 164 ms 5868 KB Output is correct
5 Correct 252 ms 8076 KB Output is correct
6 Correct 145 ms 6064 KB Output is correct
7 Correct 209 ms 7308 KB Output is correct
8 Correct 177 ms 6720 KB Output is correct
9 Correct 256 ms 7432 KB Output is correct
10 Correct 98 ms 5296 KB Output is correct
11 Correct 107 ms 5540 KB Output is correct
12 Correct 109 ms 5244 KB Output is correct
13 Correct 113 ms 5384 KB Output is correct
14 Correct 95 ms 5412 KB Output is correct
15 Correct 82 ms 5312 KB Output is correct
16 Correct 13 ms 2448 KB Output is correct
17 Correct 113 ms 11864 KB Output is correct
18 Correct 49 ms 4976 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 764 ms 28448 KB Output is correct
2 Correct 771 ms 28464 KB Output is correct
3 Correct 783 ms 27344 KB Output is correct
4 Correct 415 ms 27096 KB Output is correct
5 Correct 553 ms 28292 KB Output is correct
6 Correct 523 ms 27096 KB Output is correct
7 Correct 562 ms 28468 KB Output is correct
8 Correct 520 ms 27356 KB Output is correct
9 Correct 569 ms 27104 KB Output is correct
10 Correct 582 ms 27516 KB Output is correct
11 Correct 512 ms 27540 KB Output is correct
12 Correct 441 ms 27124 KB Output is correct
13 Correct 474 ms 27612 KB Output is correct
14 Correct 549 ms 27804 KB Output is correct
15 Correct 503 ms 28444 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 353 ms 27540 KB Output is correct
18 Correct 351 ms 27304 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 392 KB Output is correct
21 Execution timed out 3038 ms 37088 KB Time limit exceeded
22 Halted 0 ms 0 KB -