Submission #760676

#	Time	Username	Problem	Language	Result	Execution time	Memory
760676		NothingXD	Crayfish scrivener (IOI12_scrivener)	C++17	5 / 100	539 ms	45108 KiB

scrivener

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef complex<ld> point;

void debug_out(){cerr<<endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T){
	cout << H << ' ';
	debug_out(T...);
}

#define debug(...) cerr << "(" << #__VA_ARGS__ << "): ", debug_out(__VA_ARGS__)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define MP(x, y) make_pair(x, y)

const int maxn = 1e6 + 10;

int seg[maxn << 2][4], lazy[maxn << 2][3];
string s;
vector<pii> val;
void shift(int v, int l, int r);

void add(int v, int l, int r, int idx){
	if (idx < l || r <= idx) return;
	if (l + 1 == r){
		seg[v][1] = 1;
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	add(v << 1, l, mid, idx);
	add(v << 1 | 1, mid, r, idx);
	for (int i = 0; i < 4; i++){
		seg[v][i] = seg[v << 1][i] + seg[v << 1 | 1][i];
	}
}

void update(int v, int l, int r, int ql, int qr, int type){
	if (qr <= l || r <= ql) return;
	if (ql <= l && r <= qr){
		if (type == 0){
			swap(seg[v][0], seg[v][1]);
			lazy[v][0] ^= 1;
		}
		else if (type == 1){
			swap(seg[v][2], seg[v][3]);
			lazy[v][1] ^= 1;
		}
		else{
			swap(seg[v][0], seg[v][2]);
			swap(seg[v][1], seg[v][3]);
			swap(lazy[v][0], lazy[v][1]);
			lazy[v][2] ^= 1;
		}
		return;
	}
	shift(v, l, r);
	int mid = (l + r) >> 1;
	update(v << 1, l, mid, ql, qr, type);
	update(v << 1 | 1, mid, r, ql, qr, type);
	for (int i = 0; i < 4; i++){
		seg[v][i] = seg[v << 1][i] + seg[v << 1 | 1][i];
	}
}

int find(int v, int l, int r, int idx){
	if (seg[v][1] + seg[v][3] < idx) return -1;
	if (l + 1 == r) return l;
	shift(v, l, r);
	int mid = (l + r) >> 1;
	int tmp = find(v << 1, l, mid, idx);
	if (tmp == -1){
		idx -= seg[v << 1][1] + seg[v << 1][3];
		tmp = find(v << 1 | 1, mid, r, idx);
	}
	return tmp;
}

void shift(int v, int l, int r){
	int lc = v << 1;
	int rc = lc | 1;
	int mid = (l + r) >> 1;
	for (int i = 2; ~i; i--){
		if (lazy[v][i]){
			update(lc, l, mid, l, mid, i);
			update(rc, mid, r, mid, r, i);
			lazy[v][i] = 0;
		}
	}
}

void Init() {}

void TypeLetter(char L){
	s.push_back(L);
	add(1, 0, maxn, s.size()-1);
}

void UndoCommands(int U) {
	s.push_back('?');
	update(1, 0, maxn, s.size()-U, s.size(), 2);
	int tmp = s.size()-U;
	while(!val.empty() && val.back().S >= tmp){
		tmp = min(tmp, val.back().F);
		val.pop_back();
	}
	val.push_back({tmp, s.size()});
	update(1, 0, maxn, tmp, s.size(), 1);
}

char GetLetter(int P) {
	return s[find(1, 0, maxn, P+1)];
}

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