oj.uz

Submission #616247

# Submission time Handle Problem Language Result Execution time Memory
616247 2022-08-01T04:00:09 Z GusterGoose27 Ruka (COI15_ruka) C++11
100 / 100
 649 ms 43192 KB 
#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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 203 ms 20004 KB Output is correct
6 Correct 85 ms 8588 KB Output is correct
7 Correct 152 ms 20804 KB Output is correct
8 Correct 163 ms 20800 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 724 KB Output is correct
3 Correct 3 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 203 ms 20004 KB Output is correct
6 Correct 85 ms 8588 KB Output is correct
7 Correct 152 ms 20804 KB Output is correct
8 Correct 163 ms 20800 KB Output is correct
9 Correct 393 ms 21024 KB Output is correct
10 Correct 649 ms 41316 KB Output is correct
11 Correct 527 ms 43192 KB Output is correct
12 Correct 561 ms 43172 KB Output is correct