제출 #567458

#제출 시각아이디문제언어결과실행 시간메모리
567458shahriarkhan크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++14
100 / 100
510 ms246968 KiB
#include<bits/stdc++.h> using namespace std ; const int MX = 1e6 + 5 ; int od = 0 ; string s = "" ; struct Node { int left = 0 , right = 0 , sum = 0 ; } emp ; struct psegtree { int cur = 0 , cnt = 0 , N ; vector<Node> T ; vector<int> root ; void init(int n , int m) { N = n ; T = vector<Node> (20*n + 5 , emp) ; root = vector<int> (m + 5 , 0) ; } int _update(int node , int low , int high , int idx , int val) { if((idx<low) || (idx>high)) return 0 ; if((low==high) && (low==idx)) { ++cur ; T[cur].sum = T[node].sum + val ; return cur ; } int mid = (low+high)>>1 , left = T[node].left , right = T[node].right , par = ++cur ; if(idx<=mid) T[par].left = _update(left,low,mid,idx,val) , T[par].right = right ; else T[par].left = left , T[par].right = _update(right,mid+1,high,idx,val) ; T[par].sum = T[T[par].left].sum + T[T[par].right].sum ; return par ; } void add(int idx) { ++cnt ; root[cnt] = _update(root[cnt-1],1,N,idx,1) ; } void undo(int x) { ++cnt ; root[cnt] = root[cnt-x-1] ; } int _query(int node , int low , int high , int idx) { if(low==high) return low ; int mid = (low+high)>>1 , left = T[node].left , right = T[node].right ; if(T[left].sum>=idx) return _query(left,low,mid,idx) ; else return _query(right,mid+1,high,idx-T[left].sum) ; } int get_val(int idx) { return _query(root[cnt],1,N,idx) ; } } P ; void Init() { P.init(MX,MX) ; } void TypeLetter(char L) { s += L ; P.add(++od) ; } void UndoCommands(int U) { P.undo(U) ; } char GetLetter(int p) { return s[P.get_val(p+1)-1] ; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...