Submission #1054671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054671		onbert	Crayfish scrivener (IOI12_scrivener)	C++17	74 / 100	574 ms	262144 KiB

scrivener

#include <bits/stdc++.h>
using namespace std;
struct node {
    int lpt, rpt;
};
const int maxn = 1e6, maxN = 2e6 + 10;
vector<node> seg[maxN];
vector<char> leaf[maxn+5];
vector<int> sz = {0};
void build(int id, int l, int r) {
    if (l==r) {
        leaf[l] = {'.'};
        return;
    }
    seg[id] = {{0, 0}};
    int mid = (l+r)/2;
    build(id*2, l, mid); build(id*2+1, mid+1, r);
}
void update(int id, int pt, int l, int r, int target, char val) {
    if (l==r) {
        leaf[l].push_back(val);
        return;
    }
    int mid = (l+r)/2;
    seg[id].push_back(seg[id][pt]);
    if (l<=target && target<=mid) {
        update(id*2, seg[id][pt].lpt, l, mid, target, val);
        if (l!=mid) seg[id].back().lpt = (int)seg[id*2].size() - 1;
        else seg[id].back().lpt = (int)leaf[l].size() - 1;
    } else {
        update(id*2+1, seg[id][pt].rpt, mid+1, r, target, val);
        if (mid+1!=r) seg[id].back().rpt = (int)seg[id*2+1].size() - 1;
        else seg[id].back().rpt = (int)leaf[r].size() - 1;
    }
}
char qry(int id, int pt, int l, int r, int target) {
    if (r<target || target<l) return '.';
    if (l==r) return leaf[l][pt];
    int mid = (l+r)/2;
    return max(qry(id*2, seg[id][pt].lpt, l, mid, target), qry(id*2+1, seg[id][pt].rpt, mid+1, r, target));
}

void Init() {
    build(1, 0, maxn);
}

void TypeLetter(char L) {
    update(1, (int)seg[1].size()-1, 0, maxn, sz.back(), L);
    sz.push_back(sz.back() + 1);
}

void UndoCommands(int U) {
    seg[1].push_back(seg[1][(int)seg[1].size() - U - 1]);
    sz.push_back(sz[(int)sz.size() - U - 1]);
}

char GetLetter(int P) {
    return qry(1, (int)seg[1].size() - 1, 0, maxn, P);
}

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