oj.uz

Submission #237260

# Submission time Handle Problem Language Result Execution time Memory
237260 2020-06-05T14:03:58 Z Autoratch Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 534 ms 210168 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 1;

int n = N-1,ver,cnt,root[N],len[N];
struct node{ char c; int left,right; }tree[N*20];

int clone(int x){ tree[++cnt] = tree[x]; return cnt; }

void build(int l,int r,int idx)
{
    tree[idx] = {0,idx*2,idx*2+1};
    cnt = max(cnt,idx);
    if(l==r) return;
    int m = (l+r)/2;
    build(l,m,idx*2),build(m+1,r,idx*2+1);
}

int update(int l,int r,int idx,int x,char c)
{
    int now = clone(idx);
    if(l==r)
    {
        tree[now] = {c,idx,idx};
        return now;
    }
    int m = (l+r)/2;
    if(x<=m) tree[now].left = update(l,m,tree[now].left,x,c);
    else tree[now].right = update(m+1,r,tree[now].right,x,c);
    return now;
}

char read(int l,int r,int idx,int x)
{
    if(l==r) return tree[idx].c;
    int m = (l+r)/2;
    if(x<=m) return read(l,m,tree[idx].left,x);
    else return read(m+1,r,tree[idx].right,x);
}

void Init(){ build(1,n,1),root[0] = 1; }

void TypeLetter(char c){ root[ver+1] = update(1,n,root[ver],len[ver]+1,c),len[ver+1] = len[ver]+1,ver++; }

void UndoCommands(int u){ root[ver+1] = root[ver-u],len[ver+1] = len[ver-u],ver++; }

char GetLetter(int x){ return read(1,n,root[ver],x+1); }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24960 KB Output is correct
2 Correct 24 ms 24960 KB Output is correct
3 Correct 25 ms 24960 KB Output is correct
4 Correct 24 ms 24960 KB Output is correct
5 Correct 26 ms 24952 KB Output is correct
6 Correct 28 ms 24952 KB Output is correct
7 Correct 27 ms 24960 KB Output is correct
8 Correct 26 ms 24960 KB Output is correct
9 Correct 24 ms 24960 KB Output is correct
10 Correct 24 ms 24960 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 24960 KB Output is correct
2 Correct 24 ms 24960 KB Output is correct
3 Correct 25 ms 24960 KB Output is correct
4 Correct 27 ms 24960 KB Output is correct
5 Correct 24 ms 24960 KB Output is correct
6 Correct 24 ms 24960 KB Output is correct
7 Correct 24 ms 24960 KB Output is correct
8 Correct 25 ms 24960 KB Output is correct
9 Correct 25 ms 24960 KB Output is correct
10 Correct 24 ms 24960 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25344 KB Output is correct
2 Correct 28 ms 25336 KB Output is correct
3 Correct 26 ms 25472 KB Output is correct
4 Correct 26 ms 25728 KB Output is correct
5 Correct 26 ms 25464 KB Output is correct
6 Correct 27 ms 25984 KB Output is correct
7 Correct 26 ms 25856 KB Output is correct
8 Correct 26 ms 25728 KB Output is correct
9 Correct 27 ms 25720 KB Output is correct
10 Correct 26 ms 25344 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 387 ms 173048 KB Output is correct
2 Correct 397 ms 192632 KB Output is correct
3 Correct 403 ms 189816 KB Output is correct
4 Correct 434 ms 157688 KB Output is correct
5 Correct 478 ms 168416 KB Output is correct
6 Correct 410 ms 206584 KB Output is correct
7 Correct 458 ms 114552 KB Output is correct
8 Correct 423 ms 159608 KB Output is correct
9 Correct 470 ms 210168 KB Output is correct
10 Correct 327 ms 160888 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 458 ms 150776 KB Output is correct
2 Correct 534 ms 140212 KB Output is correct
3 Correct 425 ms 151972 KB Output is correct
4 Correct 467 ms 120784 KB Output is correct
5 Correct 378 ms 163192 KB Output is correct
6 Correct 380 ms 155000 KB Output is correct
7 Correct 402 ms 163704 KB Output is correct
8 Correct 479 ms 92188 KB Output is correct
9 Correct 513 ms 143864 KB Output is correct
10 Correct 343 ms 159624 KB Output is correct