oj.uz

Submission #31470

# Submission time Handle Problem Language Result Execution time Memory
31470 2017-08-28T02:25:52 Z top34051 Crayfish scrivener (IOI12_scrivener) C++14
34 / 100
 43 ms 59204 KB 
#include<bits/stdc++.h>
using namespace std;
#define maxn 2000005

int n,cur,sz;
int len[1000005], root[1000005];
vector<int> L, R;
vector<char> val;

int newnode() {
    val.push_back('0');
    L.push_back(0); R.push_back(0);
    return sz++;
}

void build(int pos,int l,int r) {
    if(l==r) return ;
    int mid = (l+r)/2, t1, t2;
    t1 = newnode(); t2 = newnode();
    L[pos] = t1; R[pos] = t2;
    build(L[pos],l,mid); build(R[pos],mid+1,r);
}

void upgrade(int pos,int last,int l,int r,int x,char temp) {
    if(l==r) {
        val[pos] = temp;
        return ;
    }
    int mid = (l+r)/2;
    if(x<=mid) {
        L[pos] = newnode();
        R[pos] = R[last];
        upgrade(L[pos],L[last],l,mid,x,temp);
    }
    else {
        L[pos] = L[last];
        R[pos] = newnode();
        upgrade(R[pos],R[last],mid+1,r,x,temp);
    }
}

char query(int pos,int l,int r,int x) {
    if(l==r) return val[pos];
    int mid = (l+r)/2;
    if(x<=mid) return query(L[pos],l,mid,x);
    return query(R[pos],mid+1,r,x);
}

void Init() {
    root[0] = newnode();
    len[0] = -1;
    build(root[0],0,1000000);
}

void TypeLetter(char L) {
    cur++;
    root[cur] = newnode();
    len[cur] = len[cur-1] + 1;
    upgrade(root[cur],root[cur-1],0,1000000,len[cur],L);
}

void UndoCommands(int U) {
    cur++;
    root[cur] = root[cur-U-1];
    len[cur] = len[cur-U-1];
}

char GetLetter(int P) {
    return query(root[cur],0,1000000,P);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 34628 KB Output is correct
2 Correct 26 ms 34628 KB Output is correct
3 Correct 29 ms 34628 KB Output is correct
4 Correct 19 ms 34628 KB Output is correct
5 Correct 16 ms 34628 KB Output is correct
6 Correct 26 ms 34628 KB Output is correct
7 Correct 33 ms 34628 KB Output is correct
8 Correct 16 ms 34628 KB Output is correct
9 Correct 36 ms 34628 KB Output is correct
10 Correct 19 ms 34628 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 34628 KB Output is correct
2 Correct 23 ms 34628 KB Output is correct
3 Correct 19 ms 34628 KB Output is correct
4 Correct 39 ms 34628 KB Output is correct
5 Correct 29 ms 34628 KB Output is correct
6 Correct 26 ms 34628 KB Output is correct
7 Correct 33 ms 34628 KB Output is correct
8 Correct 29 ms 34628 KB Output is correct
9 Correct 29 ms 34628 KB Output is correct
10 Correct 26 ms 34628 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 34628 KB Output is correct
2 Correct 23 ms 34628 KB Output is correct
3 Correct 33 ms 34628 KB Output is correct
4 Correct 23 ms 34628 KB Output is correct
5 Correct 36 ms 34628 KB Output is correct
6 Correct 29 ms 34628 KB Output is correct
7 Correct 26 ms 34628 KB Output is correct
8 Correct 23 ms 34628 KB Output is correct
9 Correct 26 ms 34628 KB Output is correct
10 Correct 23 ms 34628 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 43 ms 59204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 36 ms 59204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -