Submission #1054572

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054572		onbert	Crayfish scrivener (IOI12_scrivener)	C++17	34 / 100	329 ms	262144 KiB

scrivener

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

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

void TypeLetter(char L) {
    // cout << L << " " << (int)seg[1].size()-1 << endl;
    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: 0 / 40