fork download 
  1. /*
  2. Problem Name: Substring Reversals
  3. Problem Link: https://c...content-available-to-author-only...s.fi/problemset/task/2073
  4. Author: Sachin Srivastava (mrsac7)
  5. */
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8.  
  9. #define int long long
  10. #define endl '\n'
  11.  
  12. struct node {
  13.     node *L, *R;
  14.     int W, S;
  15.     char V;
  16.     bool F;
  17.     node(char x) {
  18.         L = R = 0;
  19.         W = rand();
  20.         S = 1;
  21.         V = x;
  22.         F = 0;
  23.     }
  24. };
  25.  
  26. int size(node *treap) {
  27.     return (treap == 0 ? 0 : treap->S);
  28. }
  29.  
  30. void push(node *treap) {
  31.     if (treap && treap->F) {
  32.         treap->F = 0;
  33.         swap(treap->L, treap->R);
  34.         if (treap->L) treap->L->F ^= 1;
  35.         if (treap->R) treap->R->F ^= 1;
  36.     }
  37. }
  38.  
  39. void split(node *treap, node *&left, node *&right, int k) {
  40.     if (treap == 0)
  41.         left = right = 0;
  42.     else {
  43.         push(treap);
  44.         if (size(treap->L) < k) {
  45.             split(treap->R, treap->R, right, k - size(treap->L) - 1);
  46.             left = treap;
  47.         }
  48.         else {
  49.             split(treap->L, left, treap->L, k);
  50.             right = treap;
  51.         }
  52.         treap->S = size(treap->L) + size(treap->R) + 1;
  53.     }
  54. }
  55.  
  56. void merge(node *&treap, node *left, node *right) {
  57.     if (left == 0) treap = right;
  58.     else if (right == 0) treap = left;
  59.     else {
  60.         push(left);
  61.         push(right);
  62.         if (left->W < right->W) {
  63.             merge(left->R, left->R, right);
  64.             treap = left;
  65.         }
  66.         else {
  67.             merge(right->L, left, right->L);
  68.             treap = right;
  69.         }
  70.         treap->S = size(treap->L) + size(treap->R) + 1;
  71.     }
  72. }
  73.  
  74. void print(node *treap) {
  75.     if (treap == NULL) return;
  76.     push(treap);
  77.     print(treap->L);
  78.     cout << treap->V;
  79.     print(treap->R);
  80. }
  81.  
  82.  
  83. signed main(){
  84.     cin.tie(0)->sync_with_stdio(0);
  85.     #ifdef LOCAL
  86.     freopen("input.txt", "r" , stdin);
  87.     freopen("output.txt", "w", stdout);
  88.     #endif
  89.  
  90.     node *treap = 0;
  91.     int n, m; cin >> n >> m;
  92.     string s; cin >> s;
  93.     for (auto i: s) {
  94.         merge(treap, treap, new node(i));
  95.     }
  96.     while (m--) {
  97.         int x, y; cin >> x >> y;
  98.         node *A, *B, *C;
  99.         split(treap, A, B, x - 1);
  100.         split(B, B, C, y - x + 1);
  101.         B->F ^= 1;
  102.         merge(treap, A, B);
  103.         merge(treap, treap, C);
  104.     }
  105.     print(treap);
  106. }
  107.  
Runtime error #stdin #stdout 0.04s 5272KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/OH4BOy
language:
C++14 (gcc 8.3)
created:
177 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!