Submission #616247

#	Time	Username	Problem	Language	Result	Execution time	Memory
616247		GusterGoose27	Ruka (COI15_ruka)	C++11	100 / 100	649 ms	43192 KiB

ruka

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;

typedef pair<ll, ll> pii;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> ostree;

const ll MAXN = 1e5;
ll n, q;
ll l_cross = 0;
ll xelems[MAXN+1];
ll yelems[MAXN+1];
pii vecs[MAXN+1];
ll pos = 0;

void er(ostree &s, pii v) {
	s.erase(s.find(v));
}

void prll(ostree &s) {
	for (pii p: s) cout << p.first << " ";
	cout << endl;
}

ll get_cross(ll a, ll b) {
	return (min(a, b) <= 0 && max(a, b) > 0);
}

class right_ds {
public:
	ll lz = 0;
	ostree mn_elems;
	ostree mx_elems;
	right_ds() {}
	right_ds(ll elems[]) {
		for (ll i = 0; i < n; i++) {
			mn_elems.insert(pii(min(elems[i], elems[i+1]), i));
			mx_elems.insert(pii(max(elems[i], elems[i+1]), i));
		}
	}
	ll query() {
		pii qelem(-lz+1, -1);
		return mn_elems.order_of_key(qelem)-mx_elems.order_of_key(qelem);
	}
	ll get_cross(ll elems[], ll pos) {
		ll mne = min(elems[pos], elems[pos+1]);
		ll mxe = max(elems[pos], elems[pos+1]);
		return (mne <= -lz && mxe > -lz);
	}
	void del(ll elems[], ll pos) { // del, then ++
		ll mne = min(elems[pos], elems[pos+1]);
		ll mxe = max(elems[pos], elems[pos+1]);
		er(mn_elems, pii(mne, pos));
		er(mx_elems, pii(mxe, pos));
		l_cross += get_cross(elems, pos);
		elems[pos] += lz;
	}
	void ins(ll elems[], ll pos) { // --, then ins
		elems[pos] -= lz;
		ll mne = min(elems[pos], elems[pos+1]);
		ll mxe = max(elems[pos], elems[pos+1]);
		mn_elems.insert(pii(mne, pos));
		mx_elems.insert(pii(mxe, pos));
		l_cross -= get_cross(elems, pos);
	}
};

right_ds xds;
right_ds yds;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	xelems[0] = 1;
	yelems[0] = 1;
	for (ll i = 1; i <= n; i++) {
		ll x, y; cin >> x >> y;
		xelems[i] = xelems[i-1]+x;
		yelems[i] = yelems[i-1]+y;
		vecs[i] = pii(x, y);
	}
	xds = right_ds(xelems);
	yds = right_ds(yelems);
	cin >> q;
	xds.del(xelems, pos);
	yds.del(yelems, pos);
	pos++;
	for (ll i = 0; i < q; i++) {
		char c; cin >> c;
		// prll(xds.mn_elems);
		// prll(xds.mx_elems);
		if (c == 'F') {
			if (pos == n) continue;
			xds.del(xelems, pos);
			yds.del(yelems, pos);
			pos++;
		}
		if (c == 'B') {
			if (pos == 1) continue;
			pos--;
			xds.ins(xelems, pos);
			yds.ins(yelems, pos);
		}
		if (c == 'Q') {
			cout << (l_cross+xds.query()+yds.query()) << "\n";
		}
		if (c == 'C') {
			ll x, y; cin >> x >> y;
			ll xsh = x-vecs[pos].first;
			ll ysh = y-vecs[pos].second;
			vecs[pos] = pii(x, y);
			l_cross -= (get_cross(xelems[pos-1], xelems[pos]+xds.lz)+get_cross(yelems[pos-1], yelems[pos]+yds.lz));
			xds.lz += xsh;
			yds.lz += ysh;
			l_cross += (get_cross(xelems[pos-1], xelems[pos]+xds.lz)+get_cross(yelems[pos-1], yelems[pos]+yds.lz));
		}
	}
};

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56