oj.uz

답안 #807581

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
807581 2023-08-04T19:43:42 Z HaroldVemeno Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 38908 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 < 10000) {
            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 552 ms 35388 KB Output is correct
2 Correct 352 ms 32160 KB Output is correct
3 Correct 396 ms 31296 KB Output is correct
4 Correct 328 ms 31212 KB Output is correct
5 Correct 379 ms 32640 KB Output is correct
6 Correct 346 ms 31808 KB Output is correct
7 Correct 389 ms 32720 KB Output is correct
8 Correct 337 ms 32084 KB Output is correct
9 Correct 330 ms 31932 KB Output is correct
10 Correct 318 ms 32140 KB Output is correct
11 Correct 337 ms 32116 KB Output is correct
12 Correct 304 ms 31820 KB Output is correct
13 Correct 332 ms 32212 KB Output is correct
14 Correct 332 ms 32352 KB Output is correct
15 Correct 332 ms 32732 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 253 ms 32188 KB Output is correct
18 Correct 781 ms 31964 KB Output is correct
19 Correct 5 ms 8148 KB Output is correct
20 Correct 4 ms 8052 KB Output is correct

Subtask #2
0 / 40.0

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

Subtask #3
0 / 25.0

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

Subtask #4
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 35388 KB Output is correct
2 Correct 352 ms 32160 KB Output is correct
3 Correct 396 ms 31296 KB Output is correct
4 Correct 328 ms 31212 KB Output is correct
5 Correct 379 ms 32640 KB Output is correct
6 Correct 346 ms 31808 KB Output is correct
7 Correct 389 ms 32720 KB Output is correct
8 Correct 337 ms 32084 KB Output is correct
9 Correct 330 ms 31932 KB Output is correct
10 Correct 318 ms 32140 KB Output is correct
11 Correct 337 ms 32116 KB Output is correct
12 Correct 304 ms 31820 KB Output is correct
13 Correct 332 ms 32212 KB Output is correct
14 Correct 332 ms 32352 KB Output is correct
15 Correct 332 ms 32732 KB Output is correct
16 Correct 4 ms 8148 KB Output is correct
17 Correct 253 ms 32188 KB Output is correct
18 Correct 781 ms 31964 KB Output is correct
19 Correct 5 ms 8148 KB Output is correct
20 Correct 4 ms 8052 KB Output is correct
21 Execution timed out 3046 ms 38908 KB Time limit exceeded
22 Halted 0 ms 0 KB -