oj.uz

Submission #290220

# Submission time Handle Problem Language Result Execution time Memory
290220 2020-09-03T13:56:39 Z stoyan_malinin Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 570 ms 262148 KB 
//#include "grader.cpp"

#include <vector>
#include <iostream>

using namespace std;

const int MAXN = 1e6 + 5;

struct SegmentTree
{
    char val;
    SegmentTree *L, *R;

    void build(int l, int r)
    {
        if(l==r) return;

        L = new SegmentTree();
        R = new SegmentTree();

        L->build(l, (l+r)/2);
        R->build((l+r)/2+1, r);
    }

    void update(int q, char c, int l, int r, SegmentTree *other)
    {
        val = other->val;

        if(l==r && q==l)
        {
            val = c;
            return;
        }

        if(l<=q && q<=(l+r)/2)
        {
            L = new SegmentTree();
            L->update(q, c, l, (l+r)/2, other->L);
        }
        else
        {
            L = other->L;
        }

        if((l+r)/2+1<=q && q<=r)
        {
            R = new SegmentTree();
            R->update(q, c, (l+r)/2+1, r, other->R);
        }
        else
        {
            R = other->R;
        }
    }

    char getChar(int q, int l, int r)
    {
        if(l==r) return val;

        if(l<=q && q<=(l+r)/2) return L->getChar(q, l, (l+r)/2);
        return R->getChar(q, (l+r)/2+1, r);
    }
};

struct String
{
    int sz;
    SegmentTree *s;

    String(){}
    String(int sz)
    {
        this->sz = sz;
        this->s = new SegmentTree();
    }
};

int COMMAND = 0;
String state[MAXN];

void Init()
{
    state[0] = String(0);
    state[0].s->build(0, MAXN);
}

void TypeLetter(char L)
{
    COMMAND++;
    state[COMMAND].sz = state[COMMAND-1].sz + 1;

    state[COMMAND].s = new SegmentTree();
    state[COMMAND].s->update(state[COMMAND].sz-1, L, 0, MAXN, state[COMMAND-1].s);
}

void UndoCommands(int U)
{
    COMMAND++;
    state[COMMAND] = state[COMMAND-1-U];
}

char GetLetter(int P)
{
    return state[COMMAND].s->getChar(P, 0, MAXN);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 62968 KB Output is correct
2 Correct 90 ms 62972 KB Output is correct
3 Correct 91 ms 62968 KB Output is correct
4 Correct 90 ms 62968 KB Output is correct
5 Correct 89 ms 63096 KB Output is correct
6 Correct 86 ms 62968 KB Output is correct
7 Correct 89 ms 62968 KB Output is correct
8 Correct 88 ms 62972 KB Output is correct
9 Correct 88 ms 63096 KB Output is correct
10 Correct 87 ms 62968 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 63096 KB Output is correct
2 Correct 86 ms 62912 KB Output is correct
3 Correct 89 ms 63096 KB Output is correct
4 Correct 93 ms 62968 KB Output is correct
5 Correct 88 ms 62968 KB Output is correct
6 Correct 87 ms 62944 KB Output is correct
7 Correct 86 ms 63096 KB Output is correct
8 Correct 92 ms 62972 KB Output is correct
9 Correct 97 ms 63076 KB Output is correct
10 Correct 86 ms 62968 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 63864 KB Output is correct
2 Correct 93 ms 63996 KB Output is correct
3 Correct 95 ms 64252 KB Output is correct
4 Correct 91 ms 64888 KB Output is correct
5 Correct 88 ms 64120 KB Output is correct
6 Correct 90 ms 65400 KB Output is correct
7 Correct 90 ms 65400 KB Output is correct
8 Correct 91 ms 64760 KB Output is correct
9 Correct 89 ms 64888 KB Output is correct
10 Correct 92 ms 63884 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 446 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 570 ms 262148 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -