oj.uz

Submission #1067304

# Submission time Handle Problem Language Result Execution time Memory
1067304 2024-08-20T14:24:03 Z Andrey Abracadabra (CEOI22_abracadabra) C++14
40 / 100
 263 ms 25936 KB 
#include<bits/stdc++.h>
using namespace std;

vector<int> haha(200001);
vector<int> p(200001,1e7);
vector<int> idk(200001);
vector<int> bruh(200001);
vector<int> pos(200001);
int n;

void upd(int a, int x) {
    while(a < idk.size()) {
        idk[a]+=x;
        a+=((a)&(-a));
    }
}

bool dude() {
    int c = 0,sb = 0;
    for(int i = 18; i >= 0; i--) {
        if(c+(1 << i) <= n && sb+idk[c+(1 << i)] < n/2) {
            c+=(1 << i);
            sb+=idk[c];
        }
    }
    c++;
    sb+=bruh[c];
    if(sb == n/2) {
        return false;
    }
    int y = pos[c]+bruh[c]-(sb-n/2);
    while(true) {
        if(p[y] < pos[c]+bruh[c]) {
            bruh[haha[y]] = p[y]-y;
            upd(haha[y],bruh[haha[y]]);
        }
        else {
            bruh[haha[y]] = pos[c]+bruh[c]-y;
            upd(haha[y],bruh[haha[y]]);
            break;
        }
        y = p[y];
    }
    upd(c,n/2-sb);
    bruh[c]+=n/2-sb;
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int q;
    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> haha[i];
        pos[haha[i]] = i;
    }
    stack<pair<int,int>> troll;
    for(int i = 1; i <= n; i++) {
        while(!troll.empty() && haha[i] > troll.top().first) {
            p[troll.top().second] = i;
            troll.pop();
        }
        troll.push({haha[i],i});
    }
    int y = 1,big = haha[1];
    for(int i = 2; i <= n/2; i++) {
        if(haha[i] > big) {
            bruh[haha[y]] = i-y;
            y = i;
            big = haha[i];
        }
    }
    bruh[haha[y]] = n/2-y+1;
    big = haha[n/2+1],y = n/2+1;
    for(int i = n/2+1; i <= n; i++) {
        if(haha[i] > big) {
            bruh[haha[y]] = i-y;
            y = i;
            big = haha[i];
        }
    }
    bruh[haha[y]] = n-y+1;
    for(int i = 1; i <= n; i++) {
        upd(i,bruh[i]);
    }
    for(int i = 0; i < q; i++) {
        int t,a;
        cin >> t >> a;
        if(t == 0) {
            cout << haha[a] << "\n";
        }
        else {
            if(i == 0) {
                for(int j = 0; j < t-1; j++) {
                    if(!dude()) {
                        break;
                    }
                }
            }
            int c = 0,sb = 0;
            for(int j = 18; j >= 0; j--) {
                if(c+(1 << j) <= n && sb+idk[c+(1 << j)] < a) {
                    c+=(1 << j);
                    sb+=idk[c];
                }
            }
            c++;
            sb+=bruh[c];
            cout << haha[pos[c]+bruh[c]-1-(sb-a)] << "\n";
        }
    }
    return 0;
}

Compilation message

Main.cpp: In function 'void upd(int, int)':
Main.cpp:12:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     while(a < idk.size()) {
      |           ~~^~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 263 ms 25936 KB Output is correct
2 Correct 237 ms 24656 KB Output is correct
3 Correct 186 ms 20816 KB Output is correct
4 Correct 180 ms 20052 KB Output is correct
5 Correct 193 ms 20484 KB Output is correct
6 Correct 175 ms 19732 KB Output is correct
7 Correct 208 ms 23952 KB Output is correct
8 Correct 211 ms 23072 KB Output is correct
9 Correct 191 ms 20308 KB Output is correct
10 Correct 201 ms 22096 KB Output is correct
11 Correct 162 ms 18768 KB Output is correct
12 Correct 180 ms 19028 KB Output is correct
13 Correct 201 ms 21472 KB Output is correct
14 Correct 172 ms 19540 KB Output is correct
15 Correct 220 ms 22668 KB Output is correct
16 Correct 17 ms 5464 KB Output is correct
17 Correct 155 ms 19536 KB Output is correct
18 Correct 160 ms 18512 KB Output is correct
19 Correct 42 ms 8272 KB Output is correct
20 Correct 65 ms 9812 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 6996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 161 ms 15956 KB Output isn't correct
2 Halted 0 ms 0 KB -