Submission #116193

#	Time	Username	Problem	Language	Result	Execution time	Memory
116193		Mercenary	Crayfish scrivener (IOI12_scrivener)	C++14	100 / 100	829 ms	180092 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;

const int maxn = 1e6 + 5;
const int logn = log2(maxn) + 1;

template<class T = char>
struct node{
    node* pre[logn];
    T val;
    int len;
    node(){
//        cout << 1;
        for(int j = 0 ; j < logn ; ++j)pre[j] = 0;
        len = 0;
    }
    void add(node* par , T val){
        len = par->len + 1;
        this->val = val;
        pre[0] = par;
//        cout << pre[0] << endl;
        for(int j = 1 ; j < logn ; ++j){
            if(pre[j - 1])pre[j] = pre[j - 1]->pre[j - 1];
            else break;
        }
    }
    T GetValAt(int pos){
        pos = len - pos - 1;
        node* now = this;
//        cout << now << endl;
        for(int j = 0 ; j < logn ; ++j){
            if((pos >> j) & 1)now = now->pre[j];
        }
//        cout << now << endl;
        return now->val;
    }
};
node<char> preorder[maxn];
node<char>* a[maxn];

int now = 0;

void Init() {
    for(int i = 0 ; i < maxn ; ++i)a[i] = &preorder[i];
}

void TypeLetter(char L) {
    ++now;
    a[now]->add(a[now - 1] , L);
}

void UndoCommands(int U) {
    ++now;
    a[now] = a[now - U - 1];
}

char GetLetter(int P) {
    return a[now]->GetValAt(P);
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 40 / 40