Submission #211233

#	Time	Username	Problem	Language	Result	Execution time	Memory
211233		mode149256	Crayfish scrivener (IOI12_scrivener)	C++14	34 / 100	680 ms	262148 KiB

scrivener

/*input

*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<ld, ld> pd;

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<vl> vll;
typedef vector<pi> vpi;
typedef vector<vpi> vpii;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<pd> vpd;
typedef vector<bool> vb;
typedef vector<vb> vbb;
typedef std::string str;
typedef std::vector<str> vs;

#define x first
#define y second
#define debug(...) cout<<"["<<#__VA_ARGS__<<": "<<__VA_ARGS__<<"]\n"

const int MOD = 1000000007;
const ll INF = std::numeric_limits<ll>::max();
const int MX = 100101;
const ld PI = 3.14159265358979323846264338327950288419716939937510582097494L;

template<typename T>
pair<T, T> operator+(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x + b.x, a.y + b.y); }
template<typename T>
pair<T, T> operator-(const pair<T, T> &a, const pair<T, T> &b) { return pair<T, T>(a.x - b.x, a.y - b.y); }
template<typename T>
T operator*(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.x + a.y * b.y); }
template<typename T>
T operator^(const pair<T, T> &a, const pair<T, T> &b) { return (a.x * b.y - a.y * b.x); }

template<typename T>
void print(vector<T> vec, string name = "") {
	cout << name;
	for (auto u : vec)
		cout << u << ' ';
	cout << '\n';
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node {
	char val;
	int prior;
	int cnt;
	node *left = NULL, *right = NULL;

	node(char a) : val(a), prior(rng()), cnt(1) { }
	node(node *kit) {
		val = kit->val;
		prior = kit->prior;
		cnt = kit->cnt;
		left = kit->left;
		right = kit->right;
	}
};

inline int cnt(node *t) { return (t ? t->cnt : 0); }
inline void upd_cnt(node *t) { if (t) t->cnt = cnt(t->left) + cnt(t->right) + 1; }

void merge(node *&t, node *l, node *r) {
	if (!l or !r)
		t = (l ? l : r);
	else if (l->prior < r->prior)
		merge(r->left, l, r->left), t = r;
	else
		merge(l->right, l->right, r), t = l;

	upd_cnt(t);
}

void split(node *t, int key, node *&l, node *&r, int add = 0) {
	if (!t)
		return void(l = r = NULL);

	int imp_key = add + cnt(t->left);

	if (key <= imp_key)
		split(t->left, key, l, t->left, add), r = t;
	else
		split(t->right, key, t->right, r, imp_key + 1), l = t;

	upd_cnt(t);
}

void insert(node *&curr, node *ka) {
	if (!curr) curr = ka;
	else if (ka->prior > curr->prior) {
		ka->left = curr;
		curr = ka;
		// split(curr, ka->key, ka->left, ka->right), curr = ka;
	} else {
		if (!curr->right) {
			insert(curr->right, ka);
		} else {
			node *naujas = new node(curr->right);
			insert(naujas, ka);
			curr->right = naujas;
		}
	}
	upd_cnt(curr);
}

// void insert(node *&curr, node *ka) {
// 	if (!curr)
// 		curr = ka;
// 	else if (ka->prior > curr->prior)
// 		split(curr, ka->key, ka->left, ka->right), curr = ka;
// 	else
// 		insert(ka->key < curr->key ? curr->left : curr->right, ka);
// }

char gauk(node *curr, int k) {
	int imp_key = cnt(curr->left);

	// printf("k = %d, imp_key = %d, currval = %c\n", k, imp_key, curr->val);
	if (imp_key == k) return curr->val;
	else if (imp_key < k)
		return gauk(curr->right, k - imp_key - 1);
	else
		return gauk(curr->left, k);
}

vector<node*> buvo;
char last;

void Init() {
	// buvo.push_back(new node(' '));
}

void TypeLetter(char L) {
	// printf("type L = %c\n", L);
	if (buvo.empty()) {
		buvo.push_back(new node(L));
	} else {
		buvo.push_back(new node(buvo.back()));
		insert(buvo.back(), new node(L));
	}

	last = L;
}

void UndoCommands(int U) {
	// printf("Undo U = %d\n", U);
	// printf("kit = %d\n", (int)buvo.size() - 1 - U);
	node *naujas = new node(buvo[buvo.size() - 1 - U]);
	buvo.push_back(naujas);
}

char GetLetter(int P) {
	// printf("gaunu P = %d\n", P);
	assert(buvo.size());
	return gauk(buvo.back(), P);
}

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