Submission #78554

#TimeUsernameProblemLanguageResultExecution timeMemory
78554Charis02Crayfish scrivener (IOI12_scrivener)C++14
34 / 100
1099 ms233272 KiB
#include<stdio.h> #include<algorithm> #define ll int #define rep(i,a,b) for(int i = a;i < b;i++) #define N 1000004 #define gc getchar//_unlocked using namespace std; struct node{ ll tag; ll length; bool isupdate; char ans; }; struct node* root; ll countt = 0; struct node* dp[N][21]; struct node* ldp[N][21]; struct node* newNode() { struct node* neo = (struct node*)malloc(sizeof (struct node)); neo -> isupdate = false; neo -> length = 0; neo -> tag = countt++; return neo; } void Init() { root = newNode(); } ll read() { char c = gc(); while(c < '0' || c > '9') { c = gc(); } ll num = c - '0'; c = gc(); while(c >= '0' && c <= '9') { num *= 10; num += (c -'0'); c = gc(); } return num; } bool ison(ll x,ll i) { return (bool)(x&(1 << i)); } struct node* jump(struct node* cur,ll x) { if(dp[cur -> tag][x]) return dp[cur -> tag][x]; return dp[cur -> tag][x] = jump(jump(cur,x-1),x-1); } struct node* ancestor(struct node* cur,ll x) { if(x == 0) return cur; struct node* res = cur; rep(i,0,19) { if(ison(x,i)) { res = jump(res,i); } } return res; } struct node* letterjump(struct node* cur,ll x) { if(ldp[cur -> tag][x]) return ldp[cur -> tag][x]; return ldp[cur -> tag][x] = letterjump(letterjump(cur,x-1),x-1); } struct node* letterancestor(struct node* cur,ll x) { if(x == 0) return cur; struct node* res = cur; rep(i,0,19) { if(ison(x,i)) { res = letterjump(res,i); } } return res; } void TypeLetter(char c) { struct node* p = root; root = newNode(); dp[root -> tag][0] = p; if(p -> isupdate) { ldp[root -> tag][0] = ldp[p -> tag][0]; } else { ldp[root -> tag][0] = p; } root -> length = (p -> length) + 1; root -> ans = c; return; } void UndoCommands(ll x) { struct node* p = root; struct node* rp = ancestor(p,x); root = newNode(); dp[root -> tag][0] = p; if(rp -> isupdate) { ldp[root -> tag][0] = ldp[rp -> tag][0]; } else { ldp[root -> tag][0] = rp; } root -> isupdate = true; root -> length = rp -> length; root -> ans = '0'; return; } char GetLetter(int P) { return (letterancestor(root,(root -> length) - P - (ll)(!(root -> isupdate))) -> ans); } /* 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...