oj.uz

Submission #917439

# Submission time Handle Problem Language Result Execution time Memory
917439 2024-01-28T08:00:40 Z jhnah917 Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 371 ms 210736 KB 
#include <bits/stdc++.h>
using namespace std;
constexpr int LG = 20, SZ = 1 << LG, NODES = SZ * (LG + 3);

int Root[SZ], Len[SZ], L[NODES], R[NODES], V[NODES], C, Pos;
void Init(int node, int s, int e){
    if(s == e) return;
    int m = (s + e) / 2;
    L[node] = ++C; R[node] = ++C;
    Init(L[node], s, m);
    Init(R[node], m+1, e);
}
void Update(int prv, int now, int s, int e, int x, int v){
    if(s == e){ V[now] = v; return; }
    int m = (s + e) / 2;
    if(x <= m){
        L[now] = ++C; R[now] = R[prv];
        Update(L[prv], L[now], s, m, x, v);
    }
    else{
        L[now] = L[prv]; R[now] = ++C;
        Update(R[prv], R[now], m+1, e, x, v);
    }
}
char Get(int node, int s, int e, int x){
    if(s == e) return V[node];
    int m = (s + e) / 2;
    if(x <= m) return Get(L[node], s, m, x);
    else return Get(R[node], m+1, e, x);
}
void Print(int node, int s, int e, int sz){
    if(s >= sz) return;
    if(s == e){ cout << char(V[node]); return; }
    int m = (s + e) / 2;
    Print(L[node], s, m, sz);
    Print(R[node], m+1, e, sz);
}

void Init(){
    Root[0] = ++C;
    Init(Root[0], 0, SZ-1);
}

void TypeLetter(char c){
    Root[++Pos] = ++C; Len[Pos] = Len[Pos-1] + 1;
    Update(Root[Pos-1], Root[Pos], 0, SZ-1, Len[Pos-1], c);
}

void UndoCommands(int k){
    Root[++Pos] = ++C; Len[Pos] = Len[Pos-k-1];
    L[Root[Pos]] = L[Root[Pos-k-1]];
    R[Root[Pos]] = R[Root[Pos-k-1]];
}

char GetLetter(int k){
    return Get(Root[Pos], 0, SZ-1, k);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25016 KB Output is correct
2 Correct 7 ms 24924 KB Output is correct
3 Correct 7 ms 24924 KB Output is correct
4 Correct 8 ms 25048 KB Output is correct
5 Correct 7 ms 24924 KB Output is correct
6 Correct 7 ms 24924 KB Output is correct
7 Correct 7 ms 25048 KB Output is correct
8 Correct 8 ms 25080 KB Output is correct
9 Correct 7 ms 25124 KB Output is correct
10 Correct 7 ms 24924 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 24912 KB Output is correct
2 Correct 8 ms 24924 KB Output is correct
3 Correct 8 ms 24924 KB Output is correct
4 Correct 9 ms 31232 KB Output is correct
5 Correct 8 ms 24924 KB Output is correct
6 Correct 8 ms 31236 KB Output is correct
7 Correct 9 ms 31064 KB Output is correct
8 Correct 9 ms 31320 KB Output is correct
9 Correct 9 ms 31068 KB Output is correct
10 Correct 8 ms 24924 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 177276 KB Output is correct
2 Correct 207 ms 193700 KB Output is correct
3 Correct 231 ms 191312 KB Output is correct
4 Correct 313 ms 166244 KB Output is correct
5 Correct 261 ms 170064 KB Output is correct
6 Correct 215 ms 207736 KB Output is correct
7 Correct 353 ms 122780 KB Output is correct
8 Correct 292 ms 165424 KB Output is correct
9 Correct 249 ms 210736 KB Output is correct
10 Correct 142 ms 164268 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 288 ms 157828 KB Output is correct
2 Correct 330 ms 146204 KB Output is correct
3 Correct 276 ms 158920 KB Output is correct
4 Correct 314 ms 123108 KB Output is correct
5 Correct 202 ms 165716 KB Output is correct
6 Correct 195 ms 158288 KB Output is correct
7 Correct 208 ms 166232 KB Output is correct
8 Correct 343 ms 98000 KB Output is correct
9 Correct 371 ms 146772 KB Output is correct
10 Correct 150 ms 163540 KB Output is correct