oj.uz

Submission #155699

# Submission time Handle Problem Language Result Execution time Memory
155699 2019-09-30T00:01:57 Z Fischer Ruka (COI15_ruka) C++14
100 / 100
 1218 ms 13780 KB 
#include <bits/stdc++.h>
#include <unordered_map>
using namespace std;
const int maxn = 1e5 + 10;
const int maxS = 2e8 + 10; 
int axis_x = maxS/2, axis_y = maxS/2;
int n, q;
unordered_map<int, int> ft[2];
int x[maxn], y[maxn];
stack<int> Qx, Qy;
int left_ans;

void update(int t, int pos, int v) {
	pos += maxS/2;
	while (pos < maxS) {
		ft[t][pos] += v;
		pos += pos&-pos;
	}
}

int query(int t, int pos) {
	pos += t == 0 ? axis_x : axis_y;;
	int ans = 0;
	while (pos > 0) {
		ans += ft[t][pos];
		pos -= pos&-pos;
	}
	return ans;
}

void add_x(int l, int r) {
	if (l > r) swap(l, r);
	Qx.push(l); Qx.push(r);
	update(0, r+1, -1);
	update(0, l, 1);	
}

void add_y(int l, int r) {
	if (l > r) swap(l, r);
	Qy.push(l); Qy.push(r);
	update(1, r+1, -1);
	update(1, l, 1);
}

void remove_x() {
	int l = Qx.top(); Qx.pop();
	int r = Qx.top(); Qx.pop();
	if (l > r) swap(l, r);
	update(0, r+1, 1);
	update(0, l, -1);
}

void remove_y() {
	int l = Qy.top(); Qy.pop();
	int r = Qy.top(); Qy.pop();
	if (l > r) swap(l, r);
	update(1, r+1, 1);
	update(1, l, -1);
}

int sum_left_x, sum_left_y;
int sum_right_x, sum_right_y;
int cur_position;
void setup(int x[], int y[]) {
	sum_left_x = 1; sum_left_y = 1;
	sum_right_x = accumulate(x, x+n+1, 0);
	sum_right_y = accumulate(y, y+n+1, 0);
	for (int i = n; i >= 1; --i) {
		add_x(sum_right_x, sum_right_x - x[i]);
		add_y(sum_right_y, sum_right_y - y[i]);
		sum_right_x -= x[i]; sum_right_y -= y[i];
	}
	cur_position = 1;
}

void next_position() {
	remove_x();
	if ((sum_left_x^(sum_left_x + x[cur_position])) < 0) {
		left_ans += 1;
	}
	sum_left_x += x[cur_position];
	sum_right_x += x[cur_position];
	remove_y();
	if ((sum_left_y^(sum_left_y + y[cur_position])) < 0) {
		left_ans += 1;
	}
	sum_left_y += y[cur_position];
	sum_right_y += y[cur_position];
	cur_position += 1;
}

void prev_position() {	
	cur_position -= 1;		
	add_x(sum_right_x, sum_right_x - x[cur_position]);
	if ((sum_left_x ^ (sum_left_x - x[cur_position])) < 0) {
		left_ans -= 1;
	}
	sum_left_x -= x[cur_position];
	sum_right_x -= x[cur_position];
	add_y(sum_right_y, sum_right_y - y[cur_position]);
	if ((sum_left_y ^ (sum_left_y - y[cur_position])) < 0) {
		left_ans -= 1;
	}
	sum_left_y -= y[cur_position];
	sum_right_y -= y[cur_position];
}

void make_change(int _x, int _y) {
	remove_x();
	sum_right_x += x[cur_position];
	add_x(sum_right_x, sum_right_x - _x);
	sum_right_x -= _x;
	axis_x += x[cur_position] - _x;
	x[cur_position] = _x;
	remove_y();
	sum_right_y += y[cur_position];
	add_y(sum_right_y, sum_right_y - _y);
	sum_right_y -= _y;
	axis_y += y[cur_position] - _y;
	y[cur_position] = _y;
}	

int response() {
	return query(0, 0) + query(1, 0) + left_ans;	
}

int main() {
	cin >> n;
	x[0] = y[0] = 1;
	for (int i = 1; i <= n; ++i) {
		cin >> x[i] >> y[i];
	}
	setup(x, y);
	cin >> q; cin.get();
	while (q--) {
		int type = cin.get();
		if (type == 'Q') {
			cout << response() << endl;
		} else if (type == 'F') {
			if (cur_position < n) {	
				next_position();
			}
		} else if (type == 'B') {
			if (cur_position > 1) {
				prev_position();
			}
		} else {
			int x, y;
			cin >> x >> y;
			make_change(x, y);
		}
		cin.get();
	}
	return 0;
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 420 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 420 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 461 ms 5712 KB Output is correct
6 Correct 422 ms 6752 KB Output is correct
7 Correct 492 ms 5224 KB Output is correct
8 Correct 489 ms 5420 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 7 ms 420 KB Output is correct
3 Correct 8 ms 504 KB Output is correct
4 Correct 8 ms 504 KB Output is correct
5 Correct 461 ms 5712 KB Output is correct
6 Correct 422 ms 6752 KB Output is correct
7 Correct 492 ms 5224 KB Output is correct
8 Correct 489 ms 5420 KB Output is correct
9 Correct 1170 ms 11716 KB Output is correct
10 Correct 1218 ms 13780 KB Output is correct
11 Correct 1046 ms 11000 KB Output is correct
12 Correct 1081 ms 11420 KB Output is correct