# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
78550 | Charis02 | Crayfish scrivener (IOI12_scrivener) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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];
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* newNode()
{
struct node* neo = (struct node*)malloc(sizeof (struct node));
neo -> isupdate = false;
neo -> length = 0;
neo -> tag = countt++;
return neo;
}
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 typechar(char c,struct node* p)
{
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 undo(ll x,struct node* p)
{
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 c,type;
ll n,d;
int main()
{
root = newNode();
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;
}