oj.uz

Submission #923112

# Submission time Handle Problem Language Result Execution time Memory
923112 2024-02-06T16:45:58 Z GrindMachine Abracadabra (CEOI22_abracadabra) C++17
35 / 100
 3000 ms 35688 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;

            if(ignore){
                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 32220 KB Output is correct
2 Correct 251 ms 30056 KB Output is correct
3 Correct 246 ms 29260 KB Output is correct
4 Correct 200 ms 26972 KB Output is correct
5 Correct 221 ms 33028 KB Output is correct
6 Correct 201 ms 30764 KB Output is correct
7 Correct 223 ms 35108 KB Output is correct
8 Correct 213 ms 29324 KB Output is correct
9 Correct 209 ms 28768 KB Output is correct
10 Correct 202 ms 28292 KB Output is correct
11 Correct 201 ms 28340 KB Output is correct
12 Correct 216 ms 29872 KB Output is correct
13 Correct 206 ms 27308 KB Output is correct
14 Correct 211 ms 30320 KB Output is correct
15 Correct 213 ms 28504 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 228 ms 27616 KB Output is correct
18 Correct 192 ms 27032 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1378 ms 10304 KB Output is correct
2 Correct 79 ms 9704 KB Output is correct
3 Correct 1442 ms 9944 KB Output is correct
4 Correct 60 ms 9392 KB Output is correct
5 Correct 65 ms 9820 KB Output is correct
6 Correct 57 ms 9300 KB Output is correct
7 Correct 61 ms 9936 KB Output is correct
8 Correct 62 ms 9476 KB Output is correct
9 Correct 61 ms 9896 KB Output is correct
10 Correct 51 ms 9300 KB Output is correct
11 Correct 53 ms 9896 KB Output is correct
12 Correct 52 ms 9432 KB Output is correct
13 Correct 52 ms 9240 KB Output is correct
14 Correct 54 ms 9552 KB Output is correct
15 Correct 58 ms 9344 KB Output is correct
16 Correct 21 ms 5844 KB Output is correct
17 Correct 60 ms 8392 KB Output is correct
18 Correct 47 ms 9412 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 235 ms 32220 KB Output is correct
2 Correct 251 ms 30056 KB Output is correct
3 Correct 246 ms 29260 KB Output is correct
4 Correct 200 ms 26972 KB Output is correct
5 Correct 221 ms 33028 KB Output is correct
6 Correct 201 ms 30764 KB Output is correct
7 Correct 223 ms 35108 KB Output is correct
8 Correct 213 ms 29324 KB Output is correct
9 Correct 209 ms 28768 KB Output is correct
10 Correct 202 ms 28292 KB Output is correct
11 Correct 201 ms 28340 KB Output is correct
12 Correct 216 ms 29872 KB Output is correct
13 Correct 206 ms 27308 KB Output is correct
14 Correct 211 ms 30320 KB Output is correct
15 Correct 213 ms 28504 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 228 ms 27616 KB Output is correct
18 Correct 192 ms 27032 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3014 ms 35688 KB Time limit exceeded
22 Halted 0 ms 0 KB -