oj.uz

Submission #616244

# Submission time Handle Problem Language Result Execution time Memory
616244 2022-08-01T03:59:13 Z GusterGoose27 Ruka (COI15_ruka) C++11
44 / 100
 669 ms 41208 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];
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 2 ms 724 KB Output is correct
3 Correct 2 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 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 175 ms 19988 KB Output is correct
6 Correct 96 ms 8700 KB Output is correct
7 Correct 180 ms 20756 KB Output is correct
8 Correct 145 ms 20724 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 724 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Correct 175 ms 19988 KB Output is correct
6 Correct 96 ms 8700 KB Output is correct
7 Correct 180 ms 20756 KB Output is correct
8 Correct 145 ms 20724 KB Output is correct
9 Correct 366 ms 21128 KB Output is correct
10 Incorrect 669 ms 41208 KB Output isn't correct
11 Halted 0 ms 0 KB -