oj.uz

Submission #635644

# Submission time Handle Problem Language Result Execution time Memory
635644 2022-08-26T14:50:35 Z welleyth Abracadabra (CEOI22_abracadabra) C++17
100 / 100
 1733 ms 48600 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;
constexpr int INF = (int)1e9 + 111;

int T[4*N];
int w[4*N];
void push(int v,int l,int r){
    if(w[v] == 0)
        return;
    int m = (l+r)>>1;
    T[v<<1] += w[v];
    T[v<<1|1] += w[v];
    w[v<<1] += w[v];
    w[v<<1|1] += w[v];
    w[v] = 0;
    return;
}
void upd(int v,int l,int r,int tl,int tr,int x){
    if(l > r || tl > tr){
        return;
    }
    if(l == tl && r == tr){
        T[v] += x;
        w[v] += x;
        return;
    }
    push(v,l,r);
    int m = (l+r)>>1;
    upd(v<<1,l,m,tl,min(tr,m),x);
    upd(v<<1|1,m+1,r,max(tl,m+1),tr,x);
    T[v] = min(T[v<<1],T[v<<1|1]);
    return;
}
int n,q;
void upd(int l,int r,int x){
    upd(1,1,n,l,r,x);
    return;
}
int get(int v,int l,int r,int tl,int tr){
    if(l > r || tl > tr)
        return INF;
    if(l == tl && r == tr)
        return T[v];
    push(v,l,r);
    int m = (l+r)>>1;
    return min(get(v<<1,l,m,tl,min(tr,m)),get(v<<1|1,m+1,r,max(m+1,tl),tr));
}

int get(int l,int r){
    return get(1,1,n,l,r);
}

int getPos(int v,int l,int r,int x){ /// get a[pos] <= x
    if(l > r)
        return -1;
    if(l == r)
        return l;
    int m = (l+r)>>1;
    push(v,l,r);
    if(T[v<<1] <= x)
        return getPos(v<<1,l,m,x);
    else
        return getPos(v<<1|1,m+1,r,x);
}

int getSuff(int r){
    return get(r,r);
}

int a[N];
int t[N],P[N];

set<int> st;
int parent[N];
vector<pair<int,pair<int,int>>> Q;
int ans[N];
int len[N];

void __attribute__ (( optimize("Ofast","unroll-loops"), target("avx2") )) solve(){
    n = (int)10000, q = (int)10000;
    for(int i = 0; i <= n; i++) T[i] = 0;
    st.clear();
    Q.clear();
//    cin >> n >> q;
    scanf("%d %d",&n,&q);
    int rv[n+1];
    for(int i = 0; i < n; i++){
//        cin >> a[i];
        scanf("%d",&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];
        scanf("%d %d",&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(a[i]);
        len[a[i]] = __r - i;
        upd(1,a[i],__r-i);
    }
    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 y = getPos(1,1,n,n/2);
            auto it = st.lower_bound(y);
            it--;
            int x = *it;
            int tr = getSuff(y);
            if(n/2 - tr <= 0){
                all = true;
                break;
            }
            int delta = n/2 - tr;
            int __len = len[x];
            int __pos = rv[x] + __len - delta;
            upd(1,x,-delta);
            len[x] -= delta;
            while(__pos < rv[x] + __len){
                int __r = min(nxt[__pos],rv[x] + __len);
                st.insert(a[__pos]);
                upd(1,a[__pos],__r-__pos);
                len[a[__pos]] = __r - __pos;
                __pos = __r;
            }
            cur_t++;
        }
        int x = getPos(1,1,n,n-pos);
        auto it = st.lower_bound(x);
        it--;
        if(get(x,x) <= n-pos){
            x = *it;
        }
        int sz = len[x];
        int suffSum = 0;
        it = st.lower_bound(x);
        it++;
        if(it != st.end()){
            int y = *it;
            suffSum = getSuff(y);
        }
        int cur_pos = (n - pos + 1) - suffSum;
        cur_pos = sz - cur_pos;
        int __pos = rv[x];
        ans[id] = a[__pos + cur_pos];
    }
    for(int i = 0; i < q; i++){
//        cout << ans[i] << "\n";
        printf("%d\n",ans[i]);
    }
    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;
}
/**
**/

Compilation message

Main.cpp: In function 'void push(int, int, int)':
Main.cpp:21:9: warning: unused variable 'm' [-Wunused-variable]
   21 |     int m = (l+r)>>1;
      |         ^
Main.cpp: In function 'void solve()':
Main.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
Main.cpp:100:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         scanf("%d",&a[i]);
      |         ~~~~~^~~~~~~~~~~~
Main.cpp:116:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         scanf("%d %d",&t[i],&P[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 27936 KB Output is correct
2 Correct 683 ms 27952 KB Output is correct
3 Correct 657 ms 26840 KB Output is correct
4 Correct 530 ms 26752 KB Output is correct
5 Correct 554 ms 27812 KB Output is correct
6 Correct 518 ms 26648 KB Output is correct
7 Correct 578 ms 27856 KB Output is correct
8 Correct 523 ms 26852 KB Output is correct
9 Correct 535 ms 26492 KB Output is correct
10 Correct 581 ms 27100 KB Output is correct
11 Correct 548 ms 26936 KB Output is correct
12 Correct 545 ms 26752 KB Output is correct
13 Correct 536 ms 27232 KB Output is correct
14 Correct 569 ms 27304 KB Output is correct
15 Correct 586 ms 27728 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 362 ms 27156 KB Output is correct
18 Correct 447 ms 26744 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1002 ms 44044 KB Output is correct
2 Correct 1022 ms 48228 KB Output is correct
3 Correct 825 ms 38136 KB Output is correct
4 Correct 599 ms 33448 KB Output is correct
5 Correct 646 ms 34684 KB Output is correct
6 Correct 582 ms 32312 KB Output is correct
7 Correct 686 ms 39268 KB Output is correct
8 Correct 657 ms 38076 KB Output is correct
9 Correct 619 ms 34008 KB Output is correct
10 Correct 616 ms 36992 KB Output is correct
11 Correct 548 ms 31776 KB Output is correct
12 Correct 553 ms 31428 KB Output is correct
13 Correct 656 ms 36920 KB Output is correct
14 Correct 559 ms 32168 KB Output is correct
15 Correct 693 ms 37612 KB Output is correct
16 Correct 27 ms 5964 KB Output is correct
17 Correct 399 ms 47372 KB Output is correct
18 Correct 477 ms 26600 KB Output is correct
19 Correct 86 ms 9624 KB Output is correct
20 Correct 161 ms 13908 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 11796 KB Output is correct
2 Correct 203 ms 12400 KB Output is correct
3 Correct 198 ms 11844 KB Output is correct
4 Correct 84 ms 7344 KB Output is correct
5 Correct 130 ms 9032 KB Output is correct
6 Correct 92 ms 7440 KB Output is correct
7 Correct 115 ms 8452 KB Output is correct
8 Correct 106 ms 7952 KB Output is correct
9 Correct 122 ms 8508 KB Output is correct
10 Correct 82 ms 6876 KB Output is correct
11 Correct 93 ms 7104 KB Output is correct
12 Correct 87 ms 6948 KB Output is correct
13 Correct 89 ms 7024 KB Output is correct
14 Correct 89 ms 7008 KB Output is correct
15 Correct 77 ms 6656 KB Output is correct
16 Correct 15 ms 4052 KB Output is correct
17 Correct 81 ms 12040 KB Output is correct
18 Correct 56 ms 4668 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 27936 KB Output is correct
2 Correct 683 ms 27952 KB Output is correct
3 Correct 657 ms 26840 KB Output is correct
4 Correct 530 ms 26752 KB Output is correct
5 Correct 554 ms 27812 KB Output is correct
6 Correct 518 ms 26648 KB Output is correct
7 Correct 578 ms 27856 KB Output is correct
8 Correct 523 ms 26852 KB Output is correct
9 Correct 535 ms 26492 KB Output is correct
10 Correct 581 ms 27100 KB Output is correct
11 Correct 548 ms 26936 KB Output is correct
12 Correct 545 ms 26752 KB Output is correct
13 Correct 536 ms 27232 KB Output is correct
14 Correct 569 ms 27304 KB Output is correct
15 Correct 586 ms 27728 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 362 ms 27156 KB Output is correct
18 Correct 447 ms 26744 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 1002 ms 44044 KB Output is correct
22 Correct 1022 ms 48228 KB Output is correct
23 Correct 825 ms 38136 KB Output is correct
24 Correct 599 ms 33448 KB Output is correct
25 Correct 646 ms 34684 KB Output is correct
26 Correct 582 ms 32312 KB Output is correct
27 Correct 686 ms 39268 KB Output is correct
28 Correct 657 ms 38076 KB Output is correct
29 Correct 619 ms 34008 KB Output is correct
30 Correct 616 ms 36992 KB Output is correct
31 Correct 548 ms 31776 KB Output is correct
32 Correct 553 ms 31428 KB Output is correct
33 Correct 656 ms 36920 KB Output is correct
34 Correct 559 ms 32168 KB Output is correct
35 Correct 693 ms 37612 KB Output is correct
36 Correct 27 ms 5964 KB Output is correct
37 Correct 399 ms 47372 KB Output is correct
38 Correct 477 ms 26600 KB Output is correct
39 Correct 86 ms 9624 KB Output is correct
40 Correct 161 ms 13908 KB Output is correct
41 Correct 214 ms 11796 KB Output is correct
42 Correct 203 ms 12400 KB Output is correct
43 Correct 198 ms 11844 KB Output is correct
44 Correct 84 ms 7344 KB Output is correct
45 Correct 130 ms 9032 KB Output is correct
46 Correct 92 ms 7440 KB Output is correct
47 Correct 115 ms 8452 KB Output is correct
48 Correct 106 ms 7952 KB Output is correct
49 Correct 122 ms 8508 KB Output is correct
50 Correct 82 ms 6876 KB Output is correct
51 Correct 93 ms 7104 KB Output is correct
52 Correct 87 ms 6948 KB Output is correct
53 Correct 89 ms 7024 KB Output is correct
54 Correct 89 ms 7008 KB Output is correct
55 Correct 77 ms 6656 KB Output is correct
56 Correct 15 ms 4052 KB Output is correct
57 Correct 81 ms 12040 KB Output is correct
58 Correct 56 ms 4668 KB Output is correct
59 Correct 0 ms 340 KB Output is correct
60 Correct 0 ms 340 KB Output is correct
61 Correct 1550 ms 47600 KB Output is correct
62 Correct 1733 ms 48600 KB Output is correct
63 Correct 1571 ms 46680 KB Output is correct
64 Correct 854 ms 38992 KB Output is correct
65 Correct 883 ms 40728 KB Output is correct
66 Correct 858 ms 39004 KB Output is correct
67 Correct 825 ms 39328 KB Output is correct
68 Correct 871 ms 38500 KB Output is correct
69 Correct 907 ms 38636 KB Output is correct
70 Correct 819 ms 37408 KB Output is correct
71 Correct 742 ms 36900 KB Output is correct
72 Correct 857 ms 36988 KB Output is correct
73 Correct 810 ms 37280 KB Output is correct
74 Correct 808 ms 37808 KB Output is correct
75 Correct 872 ms 37936 KB Output is correct
76 Correct 28 ms 5560 KB Output is correct
77 Correct 480 ms 47380 KB Output is correct
78 Correct 522 ms 32100 KB Output is correct
79 Correct 1 ms 340 KB Output is correct
80 Correct 1 ms 340 KB Output is correct