oj.uz

Submission #591571

# Submission time Handle Problem Language Result Execution time Memory
591571 2022-07-07T15:26:39 Z stevancv Crayfish scrivener (IOI12_scrivener) C++14
100 / 100
 439 ms 185408 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6;
int st[20 * N], lc[20 * N], rc[20 * N], root[N], tsz;
void Add(int& node, int pnode, int l, int r, int x, int y) {
    node = ++tsz;
    if (l == r) {st[node] = y; return; }
    lc[node] = lc[pnode]; rc[node] = rc[pnode];
    int mid = l + r >> 1;
    if (x <= mid) Add(lc[node], lc[pnode], l, mid, x, y);
    else Add(rc[node], rc[pnode], mid + 1, r, x, y);
}
int Get(int node, int l, int r, int p) {
    if (l == r) return st[node];
    int mid = l + r >> 1;
    if (p <= mid) return Get(lc[node], l, mid, p);
    else return Get(rc[node], mid + 1, r, p);
}
int sz[N], ind;
void TypeLetter(char c) {
    ind += 1;
    sz[ind] = sz[ind - 1] + 1;
    int br = c - 'a' + 1;
    Add(root[ind], root[ind - 1], 1, N, sz[ind], br);
}
void UndoCommands(int u) {
    ind += 1;
    u += 1;
    sz[ind] = sz[ind - u];
    root[ind] = root[ind - u];
}
char GetLetter(int p) {
    p += 1;
    int x = Get(root[ind], 1, N, p);
    return (char)(x + 'a' - 1);
}
void Init() {}

Compilation message

scrivener.cpp: In function 'void Add(int&, int, int, int, int, int)':
scrivener.cpp:15:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   15 |     int mid = l + r >> 1;
      |               ~~^~~
scrivener.cpp: In function 'int Get(int, int, int, int)':
scrivener.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |     int mid = l + r >> 1;
      |               ~~^~~

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 3 ms 712 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 1236 KB Output is correct
7 Correct 3 ms 1236 KB Output is correct
8 Correct 2 ms 972 KB Output is correct
9 Correct 2 ms 1108 KB Output is correct
10 Correct 3 ms 724 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 148428 KB Output is correct
2 Correct 288 ms 167828 KB Output is correct
3 Correct 305 ms 165124 KB Output is correct
4 Correct 295 ms 132976 KB Output is correct
5 Correct 372 ms 143748 KB Output is correct
6 Correct 326 ms 181780 KB Output is correct
7 Correct 383 ms 89828 KB Output is correct
8 Correct 374 ms 134708 KB Output is correct
9 Correct 357 ms 185408 KB Output is correct
10 Correct 245 ms 136236 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 349 ms 125980 KB Output is correct
2 Correct 418 ms 115576 KB Output is correct
3 Correct 328 ms 127232 KB Output is correct
4 Correct 348 ms 95860 KB Output is correct
5 Correct 318 ms 138568 KB Output is correct
6 Correct 291 ms 130440 KB Output is correct
7 Correct 332 ms 138936 KB Output is correct
8 Correct 358 ms 67396 KB Output is correct
9 Correct 439 ms 119156 KB Output is correct
10 Correct 242 ms 134948 KB Output is correct