oj.uz

Submission #923111

# Submission time Handle Problem Language Result Execution time Memory
923111 2024-02-06T16:44:20 Z GrindMachine Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 50688 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

read the edi a long time ago and remember some ideas from there

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick() {

    }

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

void solve(int test_case)
{
    ll n,q; cin >> n >> q;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];

    vector<ll> rx(n+5,n);
    stack<ll> stk;
    rep1(i,n){
        while(!stk.empty() and a[i] > a[stk.top()]){
            rx[stk.top()] = i-1;
            stk.pop();
        }
        stk.push(i);
    }

    vector<ll> pos(n+5);
    rep1(i,n) pos[a[i]] = i;

    fenwick<ll> fenw(n+5);
    ll curr_mx = 0;

    rep1(i,n){
        if(a[i] > curr_mx){
            fenw.pupd(a[i],rx[i]-i+1);
            curr_mx = a[i];
        }
    }

    vector<pll> queries[n+5];
    rep1(id,q){
        ll t,i; cin >> t >> i;
        amin(t,n);
        queries[t].pb({i,id});
    }

    vector<ll> ans(q+5);

    rep(t,n+1){
        if(t){
            ll l = 1, r = n;
            ll mid_block = -1;

            while(l <= r){
                ll mid = (l+r) >> 1;
                if(fenw.query(1,mid) > n/2){
                    mid_block = mid;
                    r = mid-1;
                }
                else{
                    l = mid+1;
                }
            }

            assert(mid_block != -1);

            ll prev_sum = fenw.query(1,mid_block-1);
            ll ignore = n/2-prev_sum;
            ll siz = fenw.query(mid_block,mid_block);
            fenw.pupd(mid_block,-siz+ignore);

            vector<pll> blocks;
            blocks.pb({0,0});

            for(int i = pos[mid_block]+ignore; i < pos[mid_block]+siz; ++i){
                if(a[i] > blocks.back().ff){
                    blocks.pb({a[i],1});
                }
                else{
                    blocks.back().ss++;
                }
            }

            for(auto [val,cnt] : blocks){
                if(!val) conts;
                fenw.pupd(val,cnt);
            }
        }

        for(auto [i,id] : queries[t]){
            ll l = 1, r = n;
            ll block = -1;

            while(l <= r){
                ll mid = (l+r) >> 1;
                if(fenw.query(1,mid) >= i){
                    block = mid;
                    r = mid-1;
                }
                else{
                    l = mid+1;
                }
            }

            ll prev_sum = fenw.query(1,block-1);
            ans[id] = a[pos[block]+i-prev_sum-1];
        }
    }

    rep1(i,q) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 39780 KB Output is correct
2 Correct 271 ms 37552 KB Output is correct
3 Correct 239 ms 36540 KB Output is correct
4 Correct 223 ms 33096 KB Output is correct
5 Correct 216 ms 40108 KB Output is correct
6 Correct 199 ms 37220 KB Output is correct
7 Correct 219 ms 42196 KB Output is correct
8 Correct 224 ms 35944 KB Output is correct
9 Correct 205 ms 34720 KB Output is correct
10 Correct 218 ms 34692 KB Output is correct
11 Correct 251 ms 34904 KB Output is correct
12 Correct 206 ms 35936 KB Output is correct
13 Correct 211 ms 33436 KB Output is correct
14 Correct 236 ms 36860 KB Output is correct
15 Correct 218 ms 34928 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 239 ms 32688 KB Output is correct
18 Correct 188 ms 33120 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1747 ms 12040 KB Output is correct
2 Correct 74 ms 11552 KB Output is correct
3 Correct 1856 ms 11616 KB Output is correct
4 Correct 65 ms 11092 KB Output is correct
5 Correct 77 ms 11596 KB Output is correct
6 Correct 62 ms 10928 KB Output is correct
7 Correct 63 ms 11480 KB Output is correct
8 Correct 75 ms 10888 KB Output is correct
9 Correct 63 ms 11200 KB Output is correct
10 Correct 59 ms 10832 KB Output is correct
11 Correct 56 ms 11344 KB Output is correct
12 Correct 58 ms 10916 KB Output is correct
13 Correct 62 ms 10576 KB Output is correct
14 Correct 56 ms 11192 KB Output is correct
15 Correct 63 ms 10892 KB Output is correct
16 Correct 25 ms 6236 KB Output is correct
17 Correct 66 ms 9676 KB Output is correct
18 Execution timed out 3061 ms 10132 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 39780 KB Output is correct
2 Correct 271 ms 37552 KB Output is correct
3 Correct 239 ms 36540 KB Output is correct
4 Correct 223 ms 33096 KB Output is correct
5 Correct 216 ms 40108 KB Output is correct
6 Correct 199 ms 37220 KB Output is correct
7 Correct 219 ms 42196 KB Output is correct
8 Correct 224 ms 35944 KB Output is correct
9 Correct 205 ms 34720 KB Output is correct
10 Correct 218 ms 34692 KB Output is correct
11 Correct 251 ms 34904 KB Output is correct
12 Correct 206 ms 35936 KB Output is correct
13 Correct 211 ms 33436 KB Output is correct
14 Correct 236 ms 36860 KB Output is correct
15 Correct 218 ms 34928 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 239 ms 32688 KB Output is correct
18 Correct 188 ms 33120 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Execution timed out 3041 ms 50688 KB Time limit exceeded
22 Halted 0 ms 0 KB -