oj.uz

Submission #807535

# Submission time Handle Problem Language Result Execution time Memory
807535 2023-08-04T19:06:14 Z HaroldVemeno Abracadabra (CEOI22_abracadabra) C++17
10 / 100
 3000 ms 34540 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;
    }

};


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* merge(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 = merge(l, a->l);
    a->r = merge(r, a->r);
    pull(a);
    return a;
}

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);
        if(r) 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;

    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 = new Node{as[i]};
        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) {
            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;
        }
        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

# Verdict Execution time Memory Grader output
1 Correct 549 ms 22052 KB Output is correct
2 Correct 359 ms 22000 KB Output is correct
3 Correct 393 ms 21088 KB Output is correct
4 Correct 309 ms 21200 KB Output is correct
5 Correct 342 ms 26908 KB Output is correct
6 Correct 313 ms 25356 KB Output is correct
7 Correct 346 ms 27048 KB Output is correct
8 Correct 305 ms 25556 KB Output is correct
9 Correct 307 ms 25224 KB Output is correct
10 Correct 329 ms 25708 KB Output is correct
11 Correct 320 ms 25620 KB Output is correct
12 Correct 284 ms 24584 KB Output is correct
13 Correct 319 ms 25460 KB Output is correct
14 Correct 315 ms 26244 KB Output is correct
15 Correct 317 ms 26188 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 235 ms 24900 KB Output is correct
18 Correct 758 ms 24716 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3068 ms 34540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3061 ms 11832 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 549 ms 22052 KB Output is correct
2 Correct 359 ms 22000 KB Output is correct
3 Correct 393 ms 21088 KB Output is correct
4 Correct 309 ms 21200 KB Output is correct
5 Correct 342 ms 26908 KB Output is correct
6 Correct 313 ms 25356 KB Output is correct
7 Correct 346 ms 27048 KB Output is correct
8 Correct 305 ms 25556 KB Output is correct
9 Correct 307 ms 25224 KB Output is correct
10 Correct 329 ms 25708 KB Output is correct
11 Correct 320 ms 25620 KB Output is correct
12 Correct 284 ms 24584 KB Output is correct
13 Correct 319 ms 25460 KB Output is correct
14 Correct 315 ms 26244 KB Output is correct
15 Correct 317 ms 26188 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 235 ms 24900 KB Output is correct
18 Correct 758 ms 24716 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Execution timed out 3068 ms 34540 KB Time limit exceeded
22 Halted 0 ms 0 KB -