oj.uz

답안 #708743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
708743 2023-03-12T08:56:49 Z becaido Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 1025 ms 524288 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout (T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 2e5 + 5;
const int QSIZ = 1e6 + 5;

int n, q;
int a[SIZE], b[SIZE], ans[QSIZ];
tuple<int, int, int> ask[QSIZ];
vector<int> v[SIZE];

int bit[SIZE];
void upd(int pos, int x) {
    for (; pos <= n; pos += pos & -pos) bit[pos] += x;
}
int que(int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}
int sch(int x) {
    int pos = 0, sum = 0;
    for (int i = __lg(n); i >= 0; i--) if (pos + (1 << i) <= n && sum + bit[pos + (1 << i)] <= x) {
        sum += bit[pos += 1 << i];
    }
    return pos + 1;
}

bool work() {
    int k = sch(n / 2), sum = que(k - 1);
    if (sum == n / 2) return 0;
    vector<int> nv;
    int ncnt = v[k].size() - (n / 2 - sum);
    FOR (i, v[k].size() - ncnt, v[k].size() - 1) nv.pb(v[k][i]);
    FOR (i, 1, ncnt) v[k].pop_back();
    upd(k, -ncnt);
    int mx = 0, cnt = 0;
    for (int i = 0; i < nv.size(); i++) {
        if (nv[i] > mx) mx = nv[i], cnt = 0;
        v[mx].pb(nv[i]);
        cnt++;
        if (i == nv.size() - 1 || nv[i + 1] > mx) upd(mx, cnt);
    }
    return 1;
}

int cal(int p) {
    int k = sch(p - 1), sum = que(k - 1);
    return v[k][p - sum - 1];
}

void solve() {
    cin >> n >> q;
    FOR (i, 1, n) cin >> a[i];
    //iota(a + 1, a + n + 1, 1);
    //shuffle(a + 1, a + n + 1, mt19937(time(NULL)));
    FOR (i, 1, q) {
        auto &[t, p, id] = ask[i];
        cin >> t >> p;
        id = i;
    }

    int mx = 0, cnt = 0;
    FOR (i, 1, n) {
        if (a[i] > mx) mx = a[i], cnt = 0;
        v[mx].pb(a[i]);
        cnt++;
        if (i == n || a[i + 1] > mx) upd(mx, cnt);
    }

    sort(ask + 1, ask + q + 1);
    int cur = 0, f = 1;
    FOR (i, 1, q) {
        auto [t, p, id] = ask[i];
        while (f && cur < t) {
            f &= work();
            cur++;
        }
        ans[id] = cal(p);
    }
    FOR (i, 1, q) cout << ans[i] << '\n';
}

int main() {
    Waimai;
    solve();
}

Compilation message

Main.cpp: In function 'bool work()':
Main.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < nv.size(); i++) {
      |                     ~~^~~~~~~~~~~
Main.cpp:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         if (i == nv.size() - 1 || nv[i + 1] > mx) upd(mx, cnt);
      |             ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 25752 KB Output is correct
2 Correct 375 ms 25244 KB Output is correct
3 Correct 351 ms 24848 KB Output is correct
4 Correct 334 ms 24132 KB Output is correct
5 Correct 362 ms 25016 KB Output is correct
6 Correct 336 ms 24176 KB Output is correct
7 Correct 351 ms 25140 KB Output is correct
8 Correct 339 ms 24316 KB Output is correct
9 Correct 330 ms 24116 KB Output is correct
10 Correct 339 ms 24440 KB Output is correct
11 Correct 350 ms 24472 KB Output is correct
12 Correct 379 ms 24140 KB Output is correct
13 Correct 363 ms 24676 KB Output is correct
14 Correct 345 ms 24772 KB Output is correct
15 Correct 347 ms 24964 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 332 ms 24468 KB Output is correct
18 Correct 326 ms 24300 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1025 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 872 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 25752 KB Output is correct
2 Correct 375 ms 25244 KB Output is correct
3 Correct 351 ms 24848 KB Output is correct
4 Correct 334 ms 24132 KB Output is correct
5 Correct 362 ms 25016 KB Output is correct
6 Correct 336 ms 24176 KB Output is correct
7 Correct 351 ms 25140 KB Output is correct
8 Correct 339 ms 24316 KB Output is correct
9 Correct 330 ms 24116 KB Output is correct
10 Correct 339 ms 24440 KB Output is correct
11 Correct 350 ms 24472 KB Output is correct
12 Correct 379 ms 24140 KB Output is correct
13 Correct 363 ms 24676 KB Output is correct
14 Correct 345 ms 24772 KB Output is correct
15 Correct 347 ms 24964 KB Output is correct
16 Correct 3 ms 4948 KB Output is correct
17 Correct 332 ms 24468 KB Output is correct
18 Correct 326 ms 24300 KB Output is correct
19 Correct 3 ms 4948 KB Output is correct
20 Correct 3 ms 4948 KB Output is correct
21 Runtime error 1025 ms 524288 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -