oj.uz

Submission #156428

# Submission time Handle Problem Language Result Execution time Memory
156428 2019-10-05T15:35:44 Z MetB Ruka (COI15_ruka) C++14
100 / 100
 162 ms 9840 KB 
#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <queue>
 
using namespace std;
 
typedef long long ll;
 
const ll INF = 1e9, MOD = 1e9 + 7, MOD2 = 1e6 + 3;

int n, m, ptr;

struct vect {
	int x, y;
} a[100000];

struct segment {
	int l, r;
} current_x, current_y;

struct segment_set {
	vector <segment> v;
	int t[10000000];
	int center;

	void update (int x, int d) {
		x += 5000000;

		for (; x < 10000000; x |= (x + 1))
			t[x] += d;
	}

	int sum (int x) {
		int sum = 0;
		x += 5000000;

		for (; x >= 0; x = (x & (x + 1)) - 1)
			sum += t[x];

		return sum;
	}

	void add (segment x) {
		x.l += center;
		x.r += center;

		if (x.l != x.r) {
			if (x.l > x.r) {
				update (x.r, 1);
				update (x.l, -1);
			}
			else {
				update (x.l + 1, 1);
				update (x.r + 1, -1);
			}
		}

		v.push_back (x);
	}

	segment pull () {
		auto x = v.back ();

		if (x.l != x.r) {
			if (x.l > x.r) {
				update (x.r, -1);
				update (x.l, 1);
			}
			else {
				update (x.l + 1, -1);
				update (x.r + 1, 1);
			}
		}
		v.pop_back ();

		x.l -= center;
		x.r -= center;
		return x;
	}

	int get () {
		return sum (center);
	}
} fixed_x, dynamic_x, fixed_y, dynamic_y;

void forward () {
	fixed_x.add (current_x);
	current_x = dynamic_x.pull ();

	fixed_y.add (current_y);
	current_y = dynamic_y.pull ();
	ptr++;
}

void backward () {
	dynamic_x.add (current_x);
	current_x = fixed_x.pull ();

	dynamic_y.add (current_y);
	current_y = fixed_y.pull ();
	ptr--;
}

void change (vect v) {
	vect delta = {v.x - a[ptr].x, v.y - a[ptr].y};
	a[ptr] = v;
	current_x.r += delta.x;
	current_y.r += delta.y;
	dynamic_x.center -= delta.x;
	dynamic_y.center -= delta.y;
}

int answer () {
	int sum = 0;
	sum = fixed_x.get () + fixed_y.get () + dynamic_x.get () + dynamic_y.get ();
	if (current_x.l != current_x.r) {
		if (current_x.l > current_x.r && current_x.r <= 0 && 0 <= current_x.l - 1) sum++;
		if (current_x.l < current_x.r && current_x.l + 1 <= 0 && 0 <= current_x.r) sum++;
	}

	if (current_y.l != current_y.r) {
		if (current_y.l > current_y.r && current_y.r <= 0 && 0 <= current_y.l - 1) sum++;
		if (current_y.l < current_y.r && current_y.l + 1 <= 0 && 0 <= current_y.r) sum++;
	}

	return sum;
}

int main () {
	cin >> n;

	int x = 1, y = 1;

	vector <segment> s_x, s_y;

	for (int i = 0; i < n; i++) {
		scanf ("%d%d", &a[i].x, &a[i].y);
		s_x.push_back ({x, x + a[i].x});
		s_y.push_back ({y, y + a[i].y});
		x += a[i].x;
		y += a[i].y;
	}

	while (s_x.size () != 1) {
		dynamic_x.add (s_x.back ());
		s_x.pop_back ();
		dynamic_y.add (s_y.back ());
		s_y.pop_back ();
	}
	current_x = s_x[0];
	current_y = s_y[0];

	cin >> m;

	for (int i = 0; i < m; i++) {
		char c[10];
		scanf ("%s", c);

		if (c[0] == 'F' && ptr < n - 1) forward ();
		if (c[0] == 'B' && ptr) backward ();
		if (c[0] == 'C') {
			vect f;
			scanf ("%d%d", &f.x, &f.y);
			change (f);
		}
		if (c[0] == 'Q') {
			printf ("%d\n", answer ());
		}

		/*cout << current_x.l << ' ' << current_x.r << endl << endl;

		for (auto a : dynamic_x.v) {
			cout << a.l << ' ' << a.r << endl;
		}
		cout << endl;
		for (auto a : fixed_x.v) {
			cout << a.l << ' ' << a.r << endl;
		}

		for (int i = -10; i <= 10; i++)
			cout << dynamic_y.sum (i) << (i == dynamic_y.center ? "!" : ""); 
		cout << endl;
		for (int i = -10; i <= 10; i++)
			cout << fixed_y.sum (i) << (i == fixed_y.center ? "!" : ""); 
		cout << endl;

		for (int i = -10; i <= 10; i++)
			cout << dynamic_x.sum (i) << (i == dynamic_x.center ? "!" : ""); 
		cout << endl;
		for (int i = -10; i <= 10; i++)
			cout << fixed_x.sum (i) << (i == fixed_x.center ? "!" : ""); 
		cout << endl;*/
	}
}

Compilation message

ruka.cpp: In function 'int main()':
ruka.cpp:142:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%d%d", &a[i].x, &a[i].y);
   ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:162:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s", c);
   ~~~~~~^~~~~~~~~
ruka.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf ("%d%d", &f.x, &f.y);
    ~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 60 ms 4332 KB Output is correct
6 Correct 45 ms 3228 KB Output is correct
7 Correct 60 ms 4484 KB Output is correct
8 Correct 58 ms 4584 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 3 ms 632 KB Output is correct
4 Correct 3 ms 632 KB Output is correct
5 Correct 60 ms 4332 KB Output is correct
6 Correct 45 ms 3228 KB Output is correct
7 Correct 60 ms 4484 KB Output is correct
8 Correct 58 ms 4584 KB Output is correct
9 Correct 134 ms 7116 KB Output is correct
10 Correct 162 ms 9840 KB Output is correct
11 Correct 148 ms 9648 KB Output is correct
12 Correct 158 ms 8440 KB Output is correct