oj.uz

Submission #118549

# Submission time Handle Problem Language Result Execution time Memory
118549 2019-06-19T07:59:03 Z Plurm Crayfish scrivener (IOI12_scrivener) C++11
74 / 100
 544 ms 153552 KB 
#include <vector>
using namespace std;
const int MXN = 1 << 20;
const int COEFF = 16;
char mem[COEFF*MXN];
int llink[COEFF*MXN];
int rlink[COEFF*MXN];
int root;
int nodesz;
vector<int> rootlist;
vector<int> lens;
inline int newnode(int o = -1){
    int c = ++nodesz;
    if(o != -1){
        llink[c] = llink[o];
        rlink[c] = rlink[o];
        mem[c] = mem[o];
    }
    return c;
}
inline int build(int l, int r){
    int c = newnode();
    if(l == r) return c;
    int k = (l+r)/2;
    llink[c] = build(l,k);
    rlink[c] = build(k+1,r);
    return c;
}
inline int update(int o, int idx, char upd, int lb, int rb){
    int nr = newnode(o);
    int b = nr;
    while(lb != rb){
        int k = (lb + rb)/2;
        if(idx <= k){
            rb = k;
            llink[nr] = newnode(llink[nr]);
            nr = llink[nr];
        }else{
            lb = k+1;
            rlink[nr] = newnode(rlink[nr]);
            nr = rlink[nr];
        }
    }
    mem[nr] = upd;
    return b;
}
inline char query(int c, int idx, int lb, int rb){
    while(lb != rb){
        int k = (lb + rb)/2;
        if(idx <= k){
            rb = k;
            c = llink[c];
        }else{
            lb = k+1;
            c = rlink[c];
        }
    }
    return mem[c];
}
void Init() {
    root = build(0, MXN-1);
    rootlist.push_back(root);
    lens.push_back(0);
}
void TypeLetter(char L) {
    int l = lens.back();
    int o = rootlist.back();
    int c = update(o, l, L, 0, MXN-1);
    rootlist.push_back(c);
    lens.push_back(l+1);
}
void UndoCommands(int U) {
    int vn = rootlist.size() - 1 - U;
    lens.push_back(lens[vn]);
    rootlist.push_back(rootlist[vn]);
}
char GetLetter(int P) {
    return query(rootlist.back(), P, 0, MXN-1);
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 16768 KB Output is correct
2 Correct 19 ms 16768 KB Output is correct
3 Correct 20 ms 16768 KB Output is correct
4 Correct 20 ms 16768 KB Output is correct
5 Correct 20 ms 16760 KB Output is correct
6 Correct 18 ms 16768 KB Output is correct
7 Correct 18 ms 16768 KB Output is correct
8 Correct 21 ms 16760 KB Output is correct
9 Correct 19 ms 16748 KB Output is correct
10 Correct 20 ms 16768 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 16768 KB Output is correct
2 Correct 21 ms 16740 KB Output is correct
3 Correct 19 ms 16760 KB Output is correct
4 Correct 19 ms 16732 KB Output is correct
5 Correct 19 ms 16760 KB Output is correct
6 Correct 19 ms 16768 KB Output is correct
7 Correct 24 ms 16760 KB Output is correct
8 Correct 20 ms 16768 KB Output is correct
9 Correct 19 ms 16768 KB Output is correct
10 Correct 20 ms 16760 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 17024 KB Output is correct
2 Correct 30 ms 17020 KB Output is correct
3 Correct 21 ms 17112 KB Output is correct
4 Correct 21 ms 17408 KB Output is correct
5 Correct 21 ms 17144 KB Output is correct
6 Correct 21 ms 17536 KB Output is correct
7 Correct 20 ms 17408 KB Output is correct
8 Correct 21 ms 17408 KB Output is correct
9 Correct 20 ms 17400 KB Output is correct
10 Correct 20 ms 17144 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 129752 KB Output is correct
2 Correct 327 ms 142208 KB Output is correct
3 Correct 356 ms 139588 KB Output is correct
4 Correct 384 ms 114284 KB Output is correct
5 Correct 447 ms 123384 KB Output is correct
6 Correct 359 ms 152700 KB Output is correct
7 Correct 437 ms 82024 KB Output is correct
8 Correct 386 ms 116456 KB Output is correct
9 Execution timed out 305 ms 153552 KB Time limit exceeded (wall clock)
10 Halted 0 ms 0 KB -

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 112824 KB Output is correct
2 Correct 544 ms 100836 KB Output is correct
3 Correct 392 ms 109900 KB Output is correct
4 Correct 444 ms 85212 KB Output is correct
5 Correct 327 ms 119244 KB Output is correct
6 Correct 344 ms 113668 KB Output is correct
7 Correct 343 ms 120260 KB Output is correct
8 Correct 472 ms 64976 KB Output is correct
9 Correct 541 ms 104092 KB Output is correct
10 Correct 257 ms 117272 KB Output is correct