oj.uz

Submission #218985

# Submission time Handle Problem Language Result Execution time Memory
218985 2020-04-03T10:43:02 Z dung11112003 Crayfish scrivener (IOI12_scrivener) C++11
100 / 100
 503 ms 211064 KB 
#include <bits/stdc++.h>

#define taskname ""
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex <ld> cd;
typedef vector <cd> vcd;
typedef vector <int> vi;

template<class T> using v2d = vector <vector <T> >;
template<class T> bool uin(T &a, T b)
{
    return a > b ? (a = b, true) : false;
}
template<class T> bool uax(T &a, T b)
{
    return a < b ? (a = b, true) : false;
}

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int maxS = 1e6 + 10;
const int maxT = 20e6 + 10;

struct node
{
    int left, right;
    char c;
    node() {}
    node(char c) : c(c) {}
} f[maxT];
int cnt[maxS], pos[maxS], pt = 0, ver = 0;
int idx;
char val;

int build(int lo, int hi)
{
    if (lo == hi)
    {
        return ++pt;
    }
    int mid = (lo + hi) / 2;
    int cur = ++pt;
    f[cur].left = build(lo, mid);
    f[cur].right = build(mid + 1, hi);
    return cur;
}

void Init()
{
    pos[ver] = build(1, 1000000);
}

int add(int x, int lo, int hi)
{
    if (lo == hi && lo == idx)
    {
        f[++pt] = node(val);
        return pt;
    }
    int mid = (lo + hi) / 2;
    int cur = ++pt;
    if (idx <= mid)
    {
        f[cur].left = add(f[x].left, lo, mid);
        f[cur].right = f[x].right;
    }
    else
    {
        f[cur].left = f[x].left;
        f[cur].right = add(f[x].right, mid + 1, hi);
    }
    return cur;
}

void TypeLetter(char L)
{
    val = L;
    idx = cnt[ver + 1] = cnt[ver] + 1;
    pos[ver + 1] = add(pos[ver], 1, 1000000);
    ++ver;
}

void UndoCommands(int U)
{
    ++pt;
    f[pt] = f[pos[ver - U]];
    cnt[ver + 1] = cnt[ver - U];
    pos[++ver] = pt;
}

char query(int x, int lo, int hi)
{
    if (lo == hi && lo == idx)
    {
        return f[x].c;
    }
    int mid = (lo + hi) / 2;
    if (idx <= mid)
    {
        return query(f[x].left, lo, mid);
    }
    return query(f[x].right, mid + 1, hi);
}

char GetLetter(int P)
{
    idx = ++P;
    return query(pos[ver], 1, 1000000);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23808 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 22 ms 23808 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23804 KB Output is correct
6 Correct 26 ms 23800 KB Output is correct
7 Correct 23 ms 23936 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 23 ms 23808 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 24192 KB Output is correct
2 Correct 24 ms 24312 KB Output is correct
3 Correct 26 ms 24440 KB Output is correct
4 Correct 24 ms 24696 KB Output is correct
5 Correct 24 ms 24320 KB Output is correct
6 Correct 24 ms 24832 KB Output is correct
7 Correct 24 ms 24832 KB Output is correct
8 Correct 24 ms 24576 KB Output is correct
9 Correct 24 ms 24576 KB Output is correct
10 Correct 24 ms 24320 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 173556 KB Output is correct
2 Correct 371 ms 194168 KB Output is correct
3 Correct 418 ms 191480 KB Output is correct
4 Correct 463 ms 161528 KB Output is correct
5 Correct 438 ms 170360 KB Output is correct
6 Correct 402 ms 208504 KB Output is correct
7 Correct 456 ms 119160 KB Output is correct
8 Correct 430 ms 163320 KB Output is correct
9 Correct 457 ms 211064 KB Output is correct
10 Correct 320 ms 165368 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 429 ms 151476 KB Output is correct
2 Correct 502 ms 140536 KB Output is correct
3 Correct 442 ms 153592 KB Output is correct
4 Correct 469 ms 122872 KB Output is correct
5 Correct 378 ms 165880 KB Output is correct
6 Correct 384 ms 158460 KB Output is correct
7 Correct 390 ms 166648 KB Output is correct
8 Correct 480 ms 96904 KB Output is correct
9 Correct 503 ms 145656 KB Output is correct
10 Correct 311 ms 164088 KB Output is correct