Submission #122649

#	Time	Username	Problem	Language	Result	Execution time	Memory
122649		luciocf	Ruka (COI15_ruka)	C++17	44 / 100	2063 ms	20928 KiB

ruka

#include <bits/stdc++.h>

using namespace std;

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

const int maxn = 1e5+10;

struct node
{
	node *l, *r;
	int v, w, sz;

	node(int vv)
	{
		v = vv, w = rand(), sz = 1;
		l = r = NULL;
	}
};

typedef node*& node_t;

stack<int> stk_x[2], stk_y[2];

int vx[maxn], vy[maxn];

int sz(node *t) {return (t ? t->sz : 0);}

void op(node *t)
{
	if (t) t->sz = sz(t->l)+sz(t->r)+1;
}

void split(node *t, node_t l, node_t r, int v)
{
	if (!t) return void(l=r=NULL);

	if (t->v > v) split(t->l, l, t->l, v), r = t;
	else split(t->r, t->r, r, v), l = t;

	op(t);
}

void merge(node_t t, node *l, node *r)
{
	if (!l || !r) t = (l ? l : r);
	else if (l->w > r->w) merge(l->r, l->r, r), t = l;
	else merge(r->l, l, r->l), t = r;

	op(t);
}

void insert(node_t t, node *aux)
{
	if (!t) t = aux;
	else if (aux->w > t->w) split(t, aux->l, aux->r, aux->v), t = aux;
	else insert((aux->v > t->v ? t->r : t->l), aux);

	op(t);
}

void erase(node_t t, int v)
{
	if (t->v == v) merge(t, t->l, t->r);
	else erase((v > t->v ? t->r : t->l), v);

	op(t); 
}

int query(node *t, int v)
{
	if (!t) return 0;

	if (t->v < v) return (1+sz(t->l)+query(t->r, v));
	return query(t->l, v);
}

int main(void)
{
	int n;
	scanf("%d", &n);

	int pref_x = 1, pref_y = 1;
	node *root_x[2], *root_y[2];

	root_x[0] = root_x[1] = root_y[0] = root_y[1] = NULL;

	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &vx[i], &vy[i]);
		pref_x += vx[i], pref_y += vy[i];
	}

	for (int i = n; i > 1; i--)
	{
		pref_x -= vx[i]; pref_y -= vy[i];

		int mn = min(pref_x, pref_x+vx[i]), mx = max(pref_x, pref_x+vx[i]);
		node *aux1 = new node(mn), *aux2 = new node(mx);

		insert(root_x[0], aux1); insert(root_x[1], aux2);
		stk_x[0].push(mn); stk_x[1].push(mx);

		mn = min(pref_y, pref_y+vy[i]), mx = max(pref_y, pref_y+vy[i]);
		aux1 = new node(mn), aux2 = new node(mx);

		insert(root_y[0], aux1); insert(root_y[1], aux2);
		stk_y[0].push(mn); stk_y[1].push(mx);
	}

	pref_x = 1, pref_y = 1;

	int ptr = 1, ans = 0, delta_x = 0, delta_y = 0;

	if (min(1+vx[1], 1) < 0 && max(1+vx[1], 1) > 0) ans++;
	if (min(1+vy[1], 1) < 0 && max(1+vy[1], 1) > 0) ans++;

	int m;
	scanf("%d", &m);

	for (int i = 1; i <= m; i++)
	{
		char op;
		scanf(" %c", &op);

		if (op == 'B' && ptr != 1)
		{
			int mn = min(pref_x, pref_x+vx[ptr]), mx = max(pref_x, pref_x+vx[ptr]);
			if (mn < 0 && mx > 0) ans--;

			node *aux1 = new node(mn-delta_x), *aux2 = new node(mx-delta_x);

			insert(root_x[0], aux1); insert(root_x[1], aux2);
			stk_x[0].push(mn-delta_x); stk_x[1].push(mx-delta_x);

			mn = min(pref_y, pref_y+vy[ptr]), mx = max(pref_y, pref_y+vy[ptr]);
			if (mn < 0 && mx > 0) ans--;

			aux1 = new node(mn-delta_y), aux2 = new node(mx-delta_y);

			insert(root_y[0], aux1); insert(root_y[1], aux2);
			stk_y[0].push(mn-delta_y); stk_y[1].push(mx-delta_y);

			ptr--;
			pref_x -= vx[ptr], pref_y -= vy[ptr];
		}
		else if (op == 'F' && ptr != n)
		{
			int mn = stk_x[0].top(), mx = stk_x[1].top();
			stk_x[0].pop(); stk_x[1].pop();

			erase(root_x[0], mn); erase(root_x[1], mx);

			mn = stk_y[0].top(), mx = stk_y[1].top();
			stk_y[0].pop(); stk_y[1].pop();

			erase(root_y[0], mn); erase(root_y[1], mx);

			pref_x += vx[ptr], pref_y += vy[ptr], ptr++;

			if (min(pref_x, pref_x+vx[ptr]) < 0 && max(pref_x, pref_x+vx[ptr]) > 0) ans++;
			if (min(pref_y, pref_y+vy[ptr]) < 0 && max(pref_y, pref_y+vy[ptr]) > 0) ans++;
		}
		else if (op == 'C')
		{
			int nx, ny;
			scanf("%d %d", &nx, &ny);

			if (min(pref_x, pref_x+vx[ptr]) < 0 && max(pref_x, pref_x+vx[ptr]) > 0) ans--;
			if (min(pref_y, pref_y+vy[ptr]) < 0 && max(pref_y, pref_y+vy[ptr]) > 0) ans--;

			delta_x += (nx - vx[ptr]), delta_y += (ny - vy[ptr]);
			vx[ptr] = nx, vy[ptr] = ny;

			if (min(pref_x, pref_x+vx[ptr]) < 0 && max(pref_x, pref_x+vx[ptr]) > 0) ans++;
			if (min(pref_y, pref_y+vy[ptr]) < 0 && max(pref_y, pref_y+vy[ptr]) > 0) ans++;
		}
		else if (op == 'Q')
		{
			int tot = ans + query(root_x[0], -delta_x) + query(root_y[0], -delta_y);
			tot -= (query(root_x[1], -delta_x) + query(root_y[1], -delta_y));

			printf("%d\n", tot);
		}
	}
}

Compilation message (stderr)

ruka.cpp:6:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("O3")
 
ruka.cpp:7:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization ("unroll-loops")
 
ruka.cpp: In function 'int main()':
ruka.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
ruka.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &vx[i], &vy[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ruka.cpp:121:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &m);
  ~~~~~^~~~~~~~~~
ruka.cpp:126:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &op);
   ~~~~~^~~~~~~~~~~~
ruka.cpp:169:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &nx, &ny);
    ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 0 / 56