Submission #169600

#TimeUsernameProblemLanguageResultExecution timeMemory
169600SamAndCollider (IZhO11_collider)C++17
100 / 100
250 ms53372 KiB
#include <bits/stdc++.h> using namespace std; mt19937 rnd(3413); const int N = 1000006; int yz; int yy[N]; void pre() { for (int i = 0; i < N; ++i) yy[i] = i; for (int i = N - 1; i >= 0; --i) swap(yy[i], yy[(rnd() % (i + 1))]); } struct ban { ban *l, *r; int y; char x; int q; ban(){} ban(char x) { l = r = 0; y = yy[yz++]; this->x = x; q = 1; } }; typedef ban* pban; int getq(pban t) { if (t == 0) return 0; return t->q; } void ubdq(pban t) { if (t == 0) return; t->q = getq(t->l) + 1 + getq(t->r); } void mer(pban l, pban r, pban& t) { if (l == 0) { t = r; return; } if (r == 0) { t = l; return; } if (l->y > r->y) { mer(l->r, r, l->r); t = l; } else { mer(l, r->l, r->l); t = r; } ubdq(t); } void spl(pban t, int x, pban& l, pban& r) { if (t == 0) { l = 0; r = 0; return; } if (x <= getq(t->l)) { spl(t->l, x, l, t->l); r = t; } else { spl(t->r, x - getq(t->l) - 1, t->r, r); l = t; } ubdq(l); ubdq(r); } void pb(pban& t, char x) { mer(t, new ban(x), t); } void ubd(pban& t, int x, int y) { if (x == y) return; if (x < y) { pban t1, t2, t3, t4; spl(t, x - 1, t1, t); spl(t, 1, t2, t); spl(t, y - x, t3, t4); mer(t1, t3, t); mer(t, t2, t); mer(t, t4, t); } else { pban t1, t2, t3, t4; spl(t, y - 1, t1, t); spl(t, x - y, t2, t); spl(t, 1, t3, t4); mer(t1, t3, t); mer(t, t2, t); mer(t, t4, t); } } char qry(pban& t, int x) { pban t1, t2, t3; spl(t, x - 1, t1, t); spl(t, 1, t2, t3); char ans = t2->x; mer(t1, t2, t); mer(t, t3, t); return ans; } void pr(pban t) { if (t == 0) return; pr(t->l); printf("%c", t->x); pr(t->r); } int n, m; char a[N]; int main() { //freopen("input.txt", "r", stdin); scanf("%d%d", &n, &m); scanf(" %s", a); pre(); pban t = 0; for (int i = 0; i < n; ++i) pb(t, a[i]); //pr(t); //printf("\n"); while (m--) { char ty; scanf(" %c", &ty); if (ty == 'a') { int x, y; scanf("%d%d", &x, &y); ubd(t, x, y); //pr(t); //printf("\n"); } else { int x; scanf("%d", &x); printf("%c\n", qry(t, x)); } } return 0; }

Compilation message (stderr)

collider.cpp: In function 'int main()':
collider.cpp:151:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf(" %s", a);
     ~~~~~^~~~~~~~~~
collider.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c", &ty);
         ~~~~~^~~~~~~~~~~~
collider.cpp:166:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d%d", &x, &y);
             ~~~~~^~~~~~~~~~~~~~~~
collider.cpp:174:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &x);
             ~~~~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...