답안 #523257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
523257 2022-02-07T09:28:56 Z cadmiumsky 입자 가속기 (IZhO11_collider) C++14
100 / 100
218 ms 47628 KB
#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
# 결과 실행 시간 메모리 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