oj.uz

답안 #957300

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
957300 2024-04-03T12:40:03 Z Lukap Abracadabra (CEOI22_abracadabra) C++14
0 / 100
 3000 ms 23232 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 500;
const int OFF = (1 << 18);

int n, q, t;
int niz[MAXN], rj[MAXN];
int iduci[MAXN];
vector<pair<pair<int, int>, int> > querys;
int ind, maks, koji[MAXN];
vector<pair<int, pair<int, int> > > v;
set<pair<int, pair<int, int> > > s;
vector<int> blokovi;
stack<int> stek;

int tour[2 * OFF];

void update (int x, int v) {
    x += OFF;
    tour[x] += v;
    x /= 2;
    while (x > 0) {
        tour[x] = tour[2 * x] + tour[2 * x + 1];
        x /= 2;
    }
}

int query_ind (int k, int x = 1, int lo = 0, int hi = OFF) {
    if (hi - lo == 1) return lo;

    int mid = (lo + hi) / 2;
    if (tour[2 * x] >= k) return query_ind(k, 2 * x, lo, mid);
    else return query_ind (k - tour[2 * x], 2 * x + 1, mid, hi);
}

int query_sum (int a, int b, int x = 1, int lo = 0, int hi = OFF) {
    if (a >= hi || b <= lo) return 0;
    if (lo >= a && hi <= b) return tour[x];

    int mid = (lo + hi) / 2;
    return query_sum(a, b, 2 * x, lo, mid) + query_sum(a, b, 2 * x + 1, mid, hi);
}

void stavi (int l, int granica) {
    while (l < granica) {
        v.push_back ({niz[l], {l, min (iduci[l], granica - 1)}});
        update (koji[l], min (iduci[l], granica - 1) - l + 1);
        l = iduci[l] + 1;
    }
}

void calc (int k, int vel) {
//    cout << "AAA " << k << ' ' << vel << "\n";
    if (vel == n / 2) {
        for (int i = (int) v.size () - 1; i >= 0; i--) blokovi.push_back (v[i].second.first);
        return;
    }

//    for (int i = OFF; i < OFF + 10; i++) cout << tour[i] << ' ';
//    cout << "\n";
    while (ind < querys.size () && min (querys[ind].first.first, maks) == k) {
        int taj = querys[ind].first.second;
        int bluk = query_ind (taj);
//        cout << taj << ' ' << bluk << "\n";
//        cout << blokovi[bluk] << ' ' << taj << ' ' << query_sum (0, bluk) << "\n";
        rj[querys[ind].second] = niz[blokovi[bluk] + taj - query_sum(0, bluk) - 1];
        ind++;
    }
//    for (auto it: v) cout << it.first << ' ' << it.second.first << ' ' << it.second.second << "\n";



    maks = max (maks, k);
    s.clear ();
    for (auto it: v) s.insert (it);

    while (true) {
        auto it = s.end ();
        it--;
        if (vel - ((*it).second.second - (*it).second.first + 1) >= n / 2) {
            blokovi.push_back((*it).second.first);
            vel -= (*it).second.second - (*it).second.first + 1;
            s.erase (it);
        }
        else break;
    }

//    cout << "AAAAAAAAAAa\n";


    auto it = s.end ();
    it--;
    int l = (*it).second.first, r = (*it).second.second, mid =  r - (vel - n / 2);
    s.erase (it);
    update (koji[l], -(r - l + 1));
    v.clear ();
    for (auto it: s) v.push_back(it);

    v.push_back ({niz[l], {l, mid}});
    update (koji[l], mid - l + 1);

    stavi (mid + 1, r + 1);
    calc (k + 1, vel);
}

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

    cin >> n >> q;
    for (int i = 0; i < n; i++) cin >> niz[i];

    for (int i = 0; i < n; i++) {
        while (stek.size () > 0 && niz[i] > niz[stek.top ()]) {
            iduci[stek.top ()] = i - 1;
            stek.pop ();
        }
        stek.push(i);
    }
    while (stek.size () > 0) {
        iduci[stek.top ()] = n - 1;
        stek.pop ();
    }
    stavi (0, n / 2);
    stavi (n / 2, n);
    calc (1, n);
    reverse (blokovi.begin (), blokovi.end ());
    for (int i = 0; i < (int) blokovi.size (); i++) koji[blokovi[i]] = i;

    for (int i = 0; i < q; i++) {
        int t, a;
        cin >> t >> a;
        if (t > min (maks, 0)) querys.push_back ({{t,a}, i});
        else rj[i] = niz[a - 1];
    }
    sort (querys.begin (), querys.end ());

//    for (auto it: blokovi) cout << it << ' ';
//    cout << "\n";

    memset (tour, 0, sizeof (tour));
    v.clear ();
    stavi (0, n / 2);
    stavi (n / 2, n);
    calc (1, n);

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

    return 0;
}

Compilation message

Main.cpp: In function 'void calc(int, int)':
Main.cpp:63:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     while (ind < querys.size () && min (querys[ind].first.first, maks) == k) {
      |            ~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3092 ms 7964 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3026 ms 7044 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

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