oj.uz

Submission #218956

# Submission time Handle Problem Language Result Execution time Memory
218956 2020-04-03T09:56:51 Z dung11112003 Crayfish scrivener (IOI12_scrivener) C++11
34 / 100
 359 ms 162680 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 = 10e6 + 10;

struct node
{
    int cnt, left, right;
    char c;
    node() : cnt(0) {}
    node(int cnt, char c) : cnt(cnt), c(c) {}
} f[maxT];
int 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)
    {
        f[++pt] = node(1, val);
        return pt;
    }
    int mid = (lo + hi) / 2;
    int cur = ++pt;
    if (f[f[x].left].cnt < mid - lo + 1)
    {
        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);
    }
    f[cur].cnt = f[f[cur].left].cnt + f[f[cur].right].cnt;
    return cur;
}

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

void UndoCommands(int U)
{
    ++pt;
    f[pt] = f[pos[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 82 ms 156920 KB Output is correct
2 Correct 83 ms 156920 KB Output is correct
3 Correct 83 ms 156920 KB Output is correct
4 Correct 84 ms 156920 KB Output is correct
5 Correct 82 ms 156920 KB Output is correct
6 Correct 82 ms 156920 KB Output is correct
7 Correct 85 ms 156920 KB Output is correct
8 Correct 86 ms 156844 KB Output is correct
9 Correct 85 ms 156920 KB Output is correct
10 Correct 90 ms 156916 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 156920 KB Output is correct
2 Correct 83 ms 156920 KB Output is correct
3 Correct 85 ms 156920 KB Output is correct
4 Correct 83 ms 156920 KB Output is correct
5 Correct 91 ms 156920 KB Output is correct
6 Correct 86 ms 156920 KB Output is correct
7 Correct 84 ms 156920 KB Output is correct
8 Correct 83 ms 156920 KB Output is correct
9 Correct 83 ms 156920 KB Output is correct
10 Correct 84 ms 156920 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 156920 KB Output is correct
2 Correct 85 ms 156940 KB Output is correct
3 Correct 86 ms 156920 KB Output is correct
4 Correct 85 ms 156920 KB Output is correct
5 Correct 86 ms 156920 KB Output is correct
6 Correct 86 ms 156920 KB Output is correct
7 Correct 86 ms 156920 KB Output is correct
8 Correct 85 ms 156924 KB Output is correct
9 Correct 83 ms 156924 KB Output is correct
10 Correct 90 ms 157048 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 238 ms 160888 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 359 ms 162680 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -