# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
237345 | T0p_ | 크레이피쉬 글쓰는 기계 (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
struct node
{
int l, r;
char c;
};
int all, ver;
int root[1000005];
node seg[23000000];
int build(int l, int r)
{
int now = ++all;
if(l == r) return now;
int mid = (l+r)>>1;
int L = build(l, mid), R = build(mid+1, r);
seg[now] = {L, R};
return now;
}
void Init() {
root[0] = build(1, 1000000);
}
int update(int idx, int l, int r, int p, char c) {
if(!(l <= p && p <= r)) return idx;
int now = ++all;
if(l == r)
{
seg[now].c = c;
return now;
}
int mid = (l+r)>>1;
int L = update(seg[idx].l, l, mid, p, c), R = update(seg[idx].r, mid+1, r, p, c);
seg[now].l = L, seg[now].r = R;
return now;
}
void TypeLetter(char L) {
ver++;
root[ver] = update(root[ver-1], 1, 1000000, seg[root[ver-1]].v+1, L);
}
void UndoCommands(int U) {
ver++;
root[ver] = root[ver-U-1];
}
char query(int idx, int l, int r, int p)
{
if(l == r) return seg[idx].c;
int mid = (l+r)>>1;
return (p <= mid) ? query(seg[idx].l, l, mid, p) : query(seg[idx].r, mid+1, r, p);
}
char GetLetter(int P) {
return query(root[ver], 1, 1000000, P+1);
}