oj.uz

Submission #156427

# Submission time Handle Problem Language Result Execution time Memory
156427 2019-10-05T15:30:09 Z MetB Ruka (COI15_ruka) C++14
9 / 100
 2000 ms 5788 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;
	vector < pair <int, int> > treap;
	int center;

	void update (int x, int d) {
		treap.push_back ({x, d});
	}

	int sum (int x) {
		int sum = 0;
		for (auto a : treap) {
			if (a.first <= x) sum += a.second;
		}

		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:138: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:158:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf ("%s", c);
   ~~~~~~^~~~~~~~~
ruka.cpp:164: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 380 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 376 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Execution timed out 2048 ms 5788 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 380 KB Output is correct
2 Correct 5 ms 504 KB Output is correct
3 Correct 4 ms 504 KB Output is correct
4 Correct 4 ms 376 KB Output is correct
5 Execution timed out 2048 ms 5788 KB Time limit exceeded
6 Halted 0 ms 0 KB -