oj.uz

Submission #866986

# Submission time Handle Problem Language Result Execution time Memory
866986 2023-10-27T14:36:10 Z Lalic Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 33456 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MAXN = 1e5+10;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const ll MOD = 1e9+7;
const ll inv2 = 500000004;

void solve(){
    int n, q; cin >> n >> q;

    vector<int> arr(n);
    int mx=0;
    for(int i=0;i<n;i++)
        cin >> arr[i], mx=max(mx, (i<n/2 ? arr[i] : -1));

    vector<pair<pii, int>> query(q);
    for(int i=0;i<q;i++)
        cin >> query[i].fi.fi >> query[i].fi.se, query[i].se=i;

    sort(all(query));

    vector<int> ans(q);
    int cnt=0;

    for(int i=0;i<q;i++){
        while(mx>arr[n/2] && cnt<query[i].fi.fi){
            cnt++;

            vector<int> att;
            mx=0;

            int ptr=n/2;
            for(int i=0;i<n/2;i++){
                while(ptr<n && arr[ptr]<arr[i]){
                    if((int)att.size()<n/2)
                        mx=max(mx, arr[ptr]);
                    att.pb(arr[ptr++]);
                }

                if((int)att.size()<n/2)
                    mx=max(mx, arr[i]);
                att.pb(arr[i]);
            }

            arr=att;
        }

        ans[query[i].se]=arr[query[i].fi.se-1];
    }

    for(int i=0;i<q;i++)
        cout << ans[i] << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    // freopen("fetiera.in", "r", stdin);

    int tt=1;
    // cin >> tt;
    while(tt--)
        solve();
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 27792 KB Output is correct
2 Correct 264 ms 27304 KB Output is correct
3 Correct 258 ms 26424 KB Output is correct
4 Correct 254 ms 25324 KB Output is correct
5 Correct 264 ms 26960 KB Output is correct
6 Correct 249 ms 25464 KB Output is correct
7 Correct 265 ms 26964 KB Output is correct
8 Correct 250 ms 25680 KB Output is correct
9 Correct 255 ms 25296 KB Output is correct
10 Correct 256 ms 26032 KB Output is correct
11 Correct 252 ms 25592 KB Output is correct
12 Correct 250 ms 24688 KB Output is correct
13 Correct 272 ms 25424 KB Output is correct
14 Correct 260 ms 26156 KB Output is correct
15 Correct 264 ms 26236 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 240 ms 24864 KB Output is correct
18 Correct 254 ms 24660 KB Output is correct
19 Correct 1 ms 500 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 3004 ms 33456 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 264 ms 27792 KB Output is correct
2 Correct 264 ms 27304 KB Output is correct
3 Correct 258 ms 26424 KB Output is correct
4 Correct 254 ms 25324 KB Output is correct
5 Correct 264 ms 26960 KB Output is correct
6 Correct 249 ms 25464 KB Output is correct
7 Correct 265 ms 26964 KB Output is correct
8 Correct 250 ms 25680 KB Output is correct
9 Correct 255 ms 25296 KB Output is correct
10 Correct 256 ms 26032 KB Output is correct
11 Correct 252 ms 25592 KB Output is correct
12 Correct 250 ms 24688 KB Output is correct
13 Correct 272 ms 25424 KB Output is correct
14 Correct 260 ms 26156 KB Output is correct
15 Correct 264 ms 26236 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 240 ms 24864 KB Output is correct
18 Correct 254 ms 24660 KB Output is correct
19 Correct 1 ms 500 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Execution timed out 3004 ms 33456 KB Time limit exceeded
22 Halted 0 ms 0 KB -