Submission #89891

#TimeUsernameProblemLanguageResultExecution timeMemory
89891popovicirobertCollider (IZhO11_collider)C++14
0 / 100
8 ms1028 KiB
#include <bits/stdc++.h> #define lsb(x) (x & (-x)) #define ll long long #define ull unsigned long long #define ld long double // 217 // 44 using namespace std; const int MAXN = (int) 1e6; char str[MAXN + 1]; typedef struct Treap *T; typedef pair <T, T> PTT; T root, NIL; struct Treap { Treap *left, *right; char ch; int prio, sz; Treap(char _ch) { left = right = NIL; ch = _ch; prio = rand(); sz = 1; } }; inline void refresh(T nod) { nod -> sz = nod -> left -> sz + nod -> right -> sz + 1; } T join(T a, T b) { if(a == NIL) { return b; } if(b == NIL) { return a; } if(a -> prio >= b -> prio) { a -> right = join(a -> right, b); refresh(a); return a; } b -> left = join(a, b -> left); refresh(b); return b; } PTT split(T nod, int sz) { if(nod == NIL) { return {NIL, NIL}; } if(nod -> left -> sz >= sz) { PTT aux = split(nod -> left, sz); nod -> left = aux.second; refresh(nod); return {aux.first, nod}; } if(nod -> left -> sz + 1 == sz) { T aux = nod -> right; nod -> right = NIL; refresh(nod); return {nod, aux}; } PTT aux = split(nod -> right, sz - nod -> left -> sz - 1); nod -> right = aux.first; refresh(nod); return {nod, aux.second}; } T ins(T nod, int sz, char ch) { PTT aux = split(nod, sz - 1); T cur = new Treap(ch); return join(aux.first, join(cur, aux.second)); } T del(T nod, int sz, char &cur) { PTT aux1 = split(nod, sz - 1); PTT aux2 = split(aux1.second, 1); cur = aux2.first -> ch; return join(aux1.first, aux2.second); } char query(T nod, int sz) { if(nod -> left -> sz + 1 == sz) { return nod -> ch; } if(nod -> left -> sz >= sz) { return query(nod -> left, sz); } return query(nod -> right, sz - nod -> left -> sz - 1); } int main() { //ifstream cin("A.in"); //ofstream cout("A.out"); int i, n, m; ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); srand(time(NULL)); cin >> n >> m; cin >> str + 1; NIL = new Treap(0); NIL -> left = NIL -> right = NIL; NIL -> sz = 0; root = NIL; for(i = 1; i <= n; i++) { root = ins(root, i, str[i]); } for(i = 1; i <= m; i++) { char ch; cin >> ch; if(ch == 'a') { int p1, p2; cin >> p1 >> p2; char cur; del(root, p1, cur); ins(root, p2, cur); } else { int p; cin >> p; cout << query(root, p) << "\n"; } } //cin.close(); //cout.close(); return 0; }

Compilation message (stderr)

collider.cpp: In function 'int main()':
collider.cpp:106:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     cin >> str + 1;
            ~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...