Submission #656789

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
656789	2022-11-08T08:38:09 Z	TheEvilBird	Collider (IZhO11_collider)	C++17	100 / 100	356 ms	2628 KB

collider

#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)((x).size())

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
//typedef __int128_t int128;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const char en = '\n';
const int INF = 1e9 + 7;
const ll INFLL = 1e18;

//mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
mt19937 rnd(1);

#ifdef __APPLE__
#include "debug.h"
//#define debug(...) 42
#else
#define debug(...) 42
#endif

struct Node {
    int val;
    int prior;
    int size;
    Node *l, *r;

    Node() = default;

    Node(int _val) : val(_val), prior(rnd()), size(1), l(nullptr), r(nullptr) {}
};

typedef Node* pnode;

int get_size(pnode root) {
    return (root == nullptr ? 0 : root->size);
}

void update(pnode root) {
    if (root == nullptr) {
        return;
    }
    root->size = 1 + get_size(root->l) + get_size(root->r);
}

pair<pnode, pnode> split(pnode root, int k) {
    if (root == nullptr) {
        return {nullptr, nullptr};
    }
    int siz = get_size(root->l) + 1;
    if (siz <= k) {
        auto [l, r] = split(root->r, k - siz);
        root->r = l;
        update(root);
        return {root, r};
    } else {
        auto [l, r] = split(root->l, k);
        root->l = r;
        update(root);
        return {l, root};
    }
}

pnode merge(pnode l, pnode r) {
    if (l == nullptr) {
        return r;
    }
    if (r == nullptr) {
        return l;
    }
    if (l->prior > r->prior) {
        l->r = merge(l->r, r);
        update(l);
        return l;
    } else {
        r->l = merge(l, r->l);
        update(r);
        return r;
    }
}

void solve() {
    int n, q;
    string s;
    cin >> n >> q >> s;
//    pnode root = nullptr;
//    for (int i = 0; i < n; ++i) {
//        root = merge(root, new Node(s[i] - 'x'));
//    }
    for (int w = 0; w < q; ++w) {
        char t;
        cin >> t;
        if (t == 'a') {
            int i, j;
            cin >> i >> j;
            if (i == j) {
                continue;
            }
            string ss;
            --i; --j;
            char c = s[i];
            s.erase(s.begin() + i);
            s.insert(s.begin() + j, c);
//            if (i < j) {
//                auto [L, R] = split(root, j - 1);
//                auto [l1, l2] = split(L, i - 1);
//                auto [x, l3] = split(l2, 1);
//                assert(x != nullptr);
//                root = merge(merge(merge(l1, l3), x), R);
//            } else {
//                auto [L, R] = split(root, i - 1);
//                auto [x, R1] = split(R, 1);
//                assert(x != nullptr);
//                auto [l1, l2] = split(L, j - 1);
//                root = merge(merge(merge(l1, x), l2), R1);
//            }
        } else { // t = 'q'
            int pos;
            cin >> pos;
            cout << s[pos - 1] << en;
//            auto [l, r] = split(root, pos);
//            auto [l1, m] = split(l, pos - 1);
//            assert(m != nullptr);
//            cout << (char)('x' + m->val) << en;
//            root = merge(merge(l1, m), r);
        }
    }
}

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0);
#endif
    solve();
    return 0;
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	2 ms	340 KB	Output is correct
3	Correct	16 ms	696 KB	Output is correct
4	Correct	102 ms	2212 KB	Output is correct
5	Correct	188 ms	2160 KB	Output is correct
6	Correct	307 ms	2376 KB	Output is correct
7	Correct	284 ms	2628 KB	Output is correct
8	Correct	122 ms	2476 KB	Output is correct
9	Correct	356 ms	2560 KB	Output is correct
10	Correct	236 ms	2544 KB	Output is correct