Submission #683273

#	Time	Username	Problem	Language	Result	Execution time	Memory
683273		vovamr	Collider (IZhO11_collider)	C++17	100 / 100	157 ms	48420 KiB

collider

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

struct Node {
	Node *l = nullptr;
	Node *r = nullptr;
	int sz, p; char val;
	Node(char x) : val(x), sz(1) { p = rng() % iinf; }
}; typedef Node* nd;
inline int sz(nd t) { return !t ? 0 : t->sz; }
inline void upd(nd t) { if (!t) return; t->sz = sz(t->l) + 1 + sz(t->r); }
inline nd mg(nd a, nd b) {
	if (!a || !b) return !a ? b : a;
	if (a->p > b->p) { a->r = mg(a->r, b); upd(a); return a; }
	else { b->l = mg(a, b->l); upd(b); return b; }
}
inline pair<nd,nd> sp(nd t, int x) {
	if (!t) return {nullptr, nullptr};
	int q = sz(t->l);
	if (x > q) { auto tt = sp(t->r, x - q - 1); t->r = tt.fi; upd(t); return {t, tt.se}; }
	else { auto tt = sp(t->l, x); t->l = tt.se; upd(t); return {tt.fi, t}; }
}
inline void pr(nd t, bool fir = 1) {
	if (!t) return;
	pr(t->l, 0); cout << t->val << " "; pr(t->r, 0);
	if (fir) cout << '\n';
}

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

	nd t = nullptr;
	for (int i = 0; i < n; ++i) {
		char x;
		cin >> x;
		t = mg(t, new Node(x));
	}

	while (q--) {
		char type;
		cin >> type;
		if (type == 'a') {
			int l, r;
			cin >> l >> r, --l, --r;

			auto [a, b] = sp(t, l);
			auto [c, d] = sp(b, 1);

			t = mg(a, d);
			auto [t1, t2] = sp(t, r);
			t = mg(t1, mg(c, t2));
//			pr(t);
		}
		else {
			int p;
			cin >> p, --p;
			auto [t1, t2] = sp(t, p);
			auto [t3, t4] = sp(t2, 1);

			cout << t3->val << '\n';
			t = mg(t1, mg(t3, t4));
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message (stderr)

collider.cpp: In constructor 'Node::Node(char)':
collider.cpp:25:18: warning: 'Node::val' will be initialized after [-Wreorder]
   25 |  int sz, p; char val;
      |                  ^~~
collider.cpp:25:6: warning:   'int Node::sz' [-Wreorder]
   25 |  int sz, p; char val;
      |      ^~
collider.cpp:26:2: warning:   when initialized here [-Wreorder]
   26 |  Node(char x) : val(x), sz(1) { p = rng() % iinf; }
      |  ^~~~

• Subtask 1: 100 / 100