제출 #78559

#제출 시각아이디문제언어결과실행 시간메모리
78559Charis02크레이피쉬 글쓰는 기계 (IOI12_scrivener)C++14
34 / 100
1029 ms123248 KiB
#include<stdio.h> #include<algorithm> #define ll int #define rep(i,a,b) for(int i = a;i < b;i++) #define N 1000004 using namespace std; ll root; ll countt = 0; ll dp[N][21]; ll ldp[N][21]; ll length[N]; bool isupdate[N]; char ans[N]; ll newNode() { isupdate[countt] = false; length[countt] = 0; countt++; return countt-1; } void Init() { root = newNode(); } bool ison(ll x,ll i) { return (bool)(x&(1 << i)); } ll jump(ll cur,ll x) { if(dp[cur][x]) return dp[cur][x]; return dp[cur][x] = jump(jump(cur,x-1),x-1); } ll ancestor(ll cur,ll x) { if(x == 0) return cur; ll res = cur; rep(i,0,20) { if(ison(x,i)) { res = jump(res,i); } } return res; } ll letterjump(ll cur,ll x) { if(ldp[cur][x]) return ldp[cur][x]; return ldp[cur][x] = letterjump(letterjump(cur,x-1),x-1); } ll letterancestor(ll cur,ll x) { if(x == 0) return cur; ll res = cur; rep(i,0,20) { if(ison(x,i)) { res = letterjump(res,i); } } return res; } void TypeLetter(char c) { ll p = root; root = newNode(); dp[root][0] = p; if(isupdate[p]) { ldp[root][0] = ldp[p][0]; } else { ldp[root][0] = p; } length[root] = length[p] + 1; ans[root] = c; return; } void UndoCommands(ll x) { ll p = root; ll rp = ancestor(p,x); root = newNode(); dp[root][0] = p; if(isupdate[rp]) { ldp[root][0] = ldp[rp][0]; } else { ldp[root][0] = rp; } isupdate[root] = true; length[root] = length[rp]; ans[root] = '0'; return; } char GetLetter(int P) { return ans[letterancestor(root,(length[root]) - P - (ll)(!isupdate[root]))]; } /* int main() { n = read(); rep(i,0,n) { type = gc(); while(type < 'A' || type > 'Z') type = gc(); if(type == 'T') { c = gc(); while(c < 'a' || c > 'z') c = gc(); typechar(c,root); } else if(type == 'U') { d = read(); undo(d,root); } else { d = read(); printf("%c\n",(letterancestor(root,(root -> length) - d - (ll)(!(root -> isupdate))) -> ans)); } } return 0; }*/
#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...