oj.uz

Submission #218986

# Submission time Handle Problem Language Result Execution time Memory
218986 2020-04-03T10:46:31 Z KoalaMuch Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 478 ms 181216 KB 
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+5;
struct A
{
    int l,r;
    char C;
};
A sm[N*30];
int root[N];
int cur;
int n;
int len[N];
int opr;
int clone(int idx)  {sm[++cur] = sm[idx];return cur;}
int update(int l,int r,int idx,int now,char v)
{
    int newnode = clone(now);
    if(l==r)
    {
        sm[newnode].C = v;
        return newnode;
    }
    int mid = (l+r) >> 1;
    if(idx<=mid)    sm[newnode].l = update(l,mid,idx,sm[newnode].l,v);
    else            sm[newnode].r = update(mid+1,r,idx,sm[newnode].r,v);
    return newnode;
}
char query(int l,int r,int now,int idx)
{
    if(l==r)    return sm[now].C;
    int mid = (l+r) >> 1;
    if(idx<=mid)    return query(l,mid,sm[now].l,idx);
    return query(mid+1,r,sm[now].r,idx);
}
void Init() {}
void TypeLetter(char L) {
    ++opr;
    ++n;
    len[opr] = n;
    root[opr] = update(0,1000000,n-1,root[opr-1],L);
}
void UndoCommands(int U) {
    ++opr;
    len[opr] = n = len[max(0,opr-U-1)];
    root[opr] = root[max(0,opr-U-1)];
}
char GetLetter(int P) {
    return P>=n ? '\0' : query(0,1000000,root[opr],P);
}
/*
int main()
{
    while(1)
    {
        int cmd,U,P;
        char L;
        scanf("%d",&cmd);
        if(cmd==1)  scanf(" %c",&L),TypeLetter(L);
        else if(cmd==2) scanf("%d",&U),UndoCommands(U);
        else            scanf("%d",&P),printf("%c\n",GetLetter(P));
    }

}
1 a
1 b
3 1
1 d
2 2
2 1
3 2
1 e
2 1
2 5
1 c
3 2
2 2
3 2
*/

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 4 ms 384 KB Output is correct
8 Correct 5 ms 288 KB Output is correct
9 Correct 4 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 768 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 6 ms 1152 KB Output is correct
5 Correct 6 ms 768 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 8 ms 1280 KB Output is correct
8 Correct 7 ms 1024 KB Output is correct
9 Correct 6 ms 1024 KB Output is correct
10 Correct 6 ms 768 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 148472 KB Output is correct
2 Correct 358 ms 163960 KB Output is correct
3 Correct 373 ms 160376 KB Output is correct
4 Correct 398 ms 126968 KB Output is correct
5 Correct 413 ms 139132 KB Output is correct
6 Correct 390 ms 177764 KB Output is correct
7 Correct 414 ms 83960 KB Output is correct
8 Correct 393 ms 129656 KB Output is correct
9 Correct 400 ms 181216 KB Output is correct
10 Correct 329 ms 132216 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 434 ms 126072 KB Output is correct
2 Correct 473 ms 110304 KB Output is correct
3 Correct 404 ms 121848 KB Output is correct
4 Correct 436 ms 89404 KB Output is correct
5 Correct 364 ms 134008 KB Output is correct
6 Correct 355 ms 125944 KB Output is correct
7 Correct 373 ms 134648 KB Output is correct
8 Correct 428 ms 61560 KB Output is correct
9 Correct 478 ms 113860 KB Output is correct
10 Correct 321 ms 130936 KB Output is correct