Submission #523257

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
523257	2022-02-07T09:28:56 Z	cadmiumsky	Collider (IZhO11_collider)	C++14	100 / 100	218 ms	47628 KB

collider

#include <bits/stdc++.h>

using namespace std;

namespace Treap { 
  struct node {
    char ch;
    int pri, area;
    node *l, *r;
    int val() {
      return l -> area + 1;
    }
  } *nil = new node {0,0,0,0,0};
  using ns = node*;
  struct pns {
    ns l, r;
  };
  ns updnode(ns node, ns c, int x) {
    (x? node -> r: node -> l) = c;
    node -> area = node -> l -> area + node -> r -> area + 1;
    return node;
  }
  ns merge(ns l, ns r) {
    return l == nil? r:
            r == nil? l:
              l -> pri > r -> pri? updnode(l, merge(l -> r, r), 1):
                updnode(r, merge(l, r -> l), 0);
  }
  pns split(ns node, int val) {
    pns temp;
    //cout << nil << ' ' << node << ' ' << val << ' ' << node -> area << '\n';
    return val == 0? pns{nil, node} :
              node -> area <= val? pns{node, nil}:
                node -> val() <= val? (temp = split(node -> r, val - node -> val()), temp.l = updnode(node, temp.l, 1), temp):
                  (temp = split(node -> l, val), temp.r = updnode(node, temp.r, 0), temp);
  }
  ns root = nil;
  void append(char ch) {
    root = merge(root, new node{ch, abs(rand()) + 1, 1, nil, nil});
  }
  void update(int pozadd, int pozelim) {
    pns temp[3];
    pozelim--;
    //cout << pozadd << ' ' << pozelim << '\n';
    temp[0] = split(root, pozadd - 1);
    //cout << temp[0].l->area << ' ' << temp[0].r->area << '\n';
    temp[1] = split(temp[0].r, 1);
    root = merge(temp[0].l, temp[1].r);
    temp[2] = split(root, pozelim);
    root = merge(temp[2].l, merge(temp[1].l, temp[2].r));
  }
  char query(int poz) {
    pns temp[2];
    temp[0] = split(root, poz - 1);
    temp[1] = split(temp[0].r, 1);
    char rez = temp[1].l -> ch;
    //cout << temp[0].l->area << ' ' << temp[1].l->area <<' ' << temp[1].r->area << '\n';
    root = merge(temp[0].l, merge(temp[1].l, temp[1].r));
    return rez;
  }
};

int main() {
  int n, m;
  cin >> n >> m;
  char ch;
  int x, y;
  for(int i = 0; i < n; i++) {
    cin >> ch;
    Treap::append(ch);
  }
  for(int i = 0; i < m; i++) {
    cin >> ch >> x;
    if(ch == 'q')
      cout << Treap::query(x) << '\n';
    else
      cin >> y, Treap::update(x, y);
    //for(int i = 1; i <= n; i++)
      //cout << Treap::query(i);
    //cout << '\n';
  }
}
//xxyyzxxzxzyyzyx
//xxyyzxxzxzyyzyx

//xxyyxzxxzxzyyzy
//xxyxyzxxzxzyyzy

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	272 KB	Output is correct
2	Correct	13 ms	428 KB	Output is correct
3	Correct	27 ms	5056 KB	Output is correct
4	Correct	141 ms	38116 KB	Output is correct
5	Correct	156 ms	38152 KB	Output is correct
6	Correct	179 ms	42836 KB	Output is correct
7	Correct	199 ms	47628 KB	Output is correct
8	Correct	187 ms	47588 KB	Output is correct
9	Correct	218 ms	47536 KB	Output is correct
10	Correct	194 ms	47584 KB	Output is correct