oj.uz

답안 #807578

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807578 2023-08-04T19:42:37 Z HaroldVemeno Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 30728 KB 
#include <bits/stdc++.h>

#ifdef GUDEB
    #define D(x) cerr << #x << ": " << (x) << '\n';
    #define ifdeb if(true)
#else
    #define D(x) ;
    #define ifdeb if(false)
#endif

#define all(x) begin(x), end(x)

using namespace std;
using ull = unsigned long long;
using ll = long long;
// #define int ll;

int as[200000];

struct Node {
    int v;
    int s = 1;
    int p = rand();
    Node* l = nullptr;
    Node* r = nullptr;
    Node* c = nullptr;

    void print(ostream& o, string bef = string{}, int pos = 0) const {
        if(l == nullptr) {
            o << bef;
            if(pos == -1) o << "  ";
            if(pos == 1)  o << "| ";
            if(pos == 2)  o << "c ";
            o << ",-o\n";
        } else {
            if(pos == -1) l->print(o, bef + "  ", -1);
            if(pos == 1)  l->print(o, bef + "| ", -1);
            if(pos == 2) l->print(o, bef + "c ", -1);
            if(pos == 0)  l->print(o, bef, -1);
        }
        o << bef;
        if(pos == -1) o << ",-";
        if(pos == 1)  o << "`-";
        if(pos == 2)  o << "c-";
        o << "(v: " << v << ", p: " << p << ", s:" << s << ")\n";
        if(c) {
            if(pos == -1) c->print(o, bef + "| | ", 2);
            if(pos == 1) c->print(o, bef + "  | ", 2);
            if(pos == 2) c->print(o, bef + "  | ", 2);
            if(pos == 0) c->print(o, bef + "| ", 2);
        }
        if(r == nullptr) {
            o << bef;
            if(pos == -1) o << "| ";
            if(pos == 1)  o << "  ";
            if(pos == 2)  o << "  ";
            o << "`-o\n";
        } else {
            if(pos == -1) r->print(o, bef + "| ", 1);
            if(pos == 1)  r->print(o, bef + "  ", 1);
            if(pos == 2)  r->print(o, bef + "  ", 1);
            if(pos == 0)  r->print(o, bef, 1);
        }

    }

    friend ostream& operator<< (ostream& o, const Node* a) {
        o << '\n';
        if(!a) o << "o\n";
        else a->print(o);
        return o;
    }

};

Node buf[200000];

int size(Node* a) {
    return a?a->s:0;
}

void pull(Node* a) {
    if(a) {
        a->s = 1;
        a->s += size(a->l);
        a->s += size(a->r);
        a->s += size(a->c);
    }
}

Node* concat(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->p > b->p) {
        a->r = concat(a->r, b);
        pull(a);
        return a;
    } else {
        b->l = concat(a, b->l);
        pull(b);
        return b;
    }
}


pair<Node*, Node*> splitbyv(Node* a, int v) {
    if(!a) return {a, a};
    if(a->v < v) {
        auto [rl, rr] = splitbyv(a->r, v);
        a->r = rl;
        pull(a);
        return {a, rr};
    } else {
        auto [ll, lr] = splitbyv(a->l, v);
        a->l = lr;
        pull(a);
        return {ll, a};
    }
}

Node* merge2(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(b->p > a->p) swap(a, b);
    auto [l, r] = splitbyv(b, a->v);
    a->l = merge2(l, a->l);
    a->r = merge2(r, a->r);
    pull(a);
    return a;
}

Node* merge(Node* a, Node* b) {
    if(!a) return b;
    if(!b) return a;
    if(a->s > b->s) swap(a, b);
    b = merge(a->l, b);
    a->l = nullptr;
    b = merge(a->r, b);
    a->r = nullptr;
    pull(a);
    auto [l, r] = splitbyv(b, a->v);
    b = concat(l, concat(a, r));
    return b;
}

struct SplitRes {
    Node* l;
    Node* m;
    Node* r;
};

SplitRes splitons(Node* a, int s) {
    D(s)
    D(a)
    if(!a) return {a, a, a};
    if( s <= size(a->l) ) {
        auto[l, m, r] = splitons(a->l, s);
        a->l = r;
        pull(a);
        return {l, m, a};
    } else if(s >= size(a->l) + size(a->c) + 1) {
        auto[l, m, r] = splitons(a->r, s - size(a->c) - size(a->l) - 1 );
        a->r = l;
        pull(a);
        return {a, m, r};
    } else {
        auto[l, m, r] = splitons(a->c, s - size(a->l) - 1);
        m = concat(m, r);
        a->c = l;
        auto ar = a->r;
        a->r = nullptr;
        pull(a);
        return {a, m, ar};
    }
}


int valuebys(Node* a, int s) {
    D(size(a))
    if(s < size(a->l)) {
        return valuebys(a->l, s);
    } else if(s == size(a->l)) {
        return a->v;
    } else if(s < size(a->l) + 1 + size(a->c)) {
        return valuebys(a->c, s - size(a->l) - 1);
    } else {
        return valuebys(a->r, s - size(a->l) - 1 - size(a->c));
    }
}

struct Q {
    int t;
    int ind;
    int i;
    int res;
};

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

    srand(4994040);

    vector<Q> qs(q);
    for(int i = 0; i < n; ++i) {
        cin >> as[i];
    }
    for(int i = 0; i < q; ++i) {
        cin >> qs[i].t >> qs[i].ind;
        --qs[i].ind;
        qs[i].i = i;
    }
    sort(all(qs), [](Q a, Q b){return a.t < b.t;});

    vector<Node*> trs;
    for(int i = n-1; i >= 0; --i) {
        Node* tr = buf+i;
        tr->v = as[i];
        tr->s = 1;
        tr->p = rand();
        while(!trs.empty() && trs.back()->v < tr->v) {
            tr->c = concat(tr->c, trs.back());
            trs.pop_back();
        }
        pull(tr);
        trs.push_back(tr);
    }
    Node* tr = nullptr;
    for(Node* t : trs) {
        tr = concat(t, tr);
    }
    trs.clear();
    D(tr);
    D(size(tr));

    int t = 0;
    bool changed = true;
    for(int i = 0; i < q; ++i) {
        D(i)
        while(changed && qs[i].t > t && t < 220000) {
            D(t)
            auto [l, m, r] = splitons(tr, n/2);
            if(m == nullptr) changed = false;
            D(l)
            D(m)
            D(r)
            l = merge(l, m);
            D(l)
            tr = concat(l, r);
            D(tr)
            ++t;
        }
        D(t)
        qs[i].res = valuebys(tr, qs[i].ind);
    }


    sort(all(qs), [](Q a, Q b){return a.i < b.i;});
    for(auto q : qs) cout << q.res << '\n';
    return;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << setprecision(20);

    solve();
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 518 ms 27688 KB Output is correct
2 Correct 350 ms 28492 KB Output is correct
3 Correct 399 ms 27668 KB Output is correct
4 Correct 329 ms 27548 KB Output is correct
5 Correct 351 ms 28488 KB Output is correct
6 Correct 372 ms 27616 KB Output is correct
7 Correct 353 ms 28516 KB Output is correct
8 Correct 352 ms 27828 KB Output is correct
9 Correct 338 ms 27624 KB Output is correct
10 Correct 331 ms 27944 KB Output is correct
11 Correct 332 ms 27884 KB Output is correct
12 Correct 299 ms 27340 KB Output is correct
13 Correct 342 ms 27968 KB Output is correct
14 Correct 342 ms 28148 KB Output is correct
15 Correct 335 ms 28504 KB Output is correct
16 Correct 5 ms 8148 KB Output is correct
17 Correct 288 ms 27488 KB Output is correct
18 Correct 800 ms 27400 KB Output is correct
19 Correct 6 ms 8144 KB Output is correct
20 Correct 4 ms 8160 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 518 ms 27688 KB Output is correct
2 Correct 350 ms 28492 KB Output is correct
3 Correct 399 ms 27668 KB Output is correct
4 Correct 329 ms 27548 KB Output is correct
5 Correct 351 ms 28488 KB Output is correct
6 Correct 372 ms 27616 KB Output is correct
7 Correct 353 ms 28516 KB Output is correct
8 Correct 352 ms 27828 KB Output is correct
9 Correct 338 ms 27624 KB Output is correct
10 Correct 331 ms 27944 KB Output is correct
11 Correct 332 ms 27884 KB Output is correct
12 Correct 299 ms 27340 KB Output is correct
13 Correct 342 ms 27968 KB Output is correct
14 Correct 342 ms 28148 KB Output is correct
15 Correct 335 ms 28504 KB Output is correct
16 Correct 5 ms 8148 KB Output is correct
17 Correct 288 ms 27488 KB Output is correct
18 Correct 800 ms 27400 KB Output is correct
19 Correct 6 ms 8144 KB Output is correct
20 Correct 4 ms 8160 KB Output is correct
21 Execution timed out 3064 ms 30728 KB Time limit exceeded
22 Halted 0 ms 0 KB -