Submission #140573

#	Time	Username	Problem	Language	Result	Execution time	Memory
140573		luciocf	Street Lamps (APIO19_street_lamps)	C++17	40 / 100	5085 ms	11000 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int maxn = 3e5+10;

struct Op
{
	int type;
	int ind;
} query[maxn];

struct E
{
	int type;
	int l, r;
} event[maxn];

int n, q;

int last[maxn];
int ans[maxn];

int pai[maxn], peso[maxn];
int edge[maxn], nivel[maxn];

bool on[maxn];
bool mark[maxn];

void init(void)
{
	for (int i = 1; i <= n+1; i++)
		pai[i] = i, peso[i] = 1;
}

int Find(int x)
{
	if (pai[x] == x) return x;
	return Find(pai[x]);
}

void Join(int x, int y, int t)
{
	x = Find(x), y = Find(y);
	if (x == y) return;

	if (peso[x] < peso[y]) swap(x, y);

	pai[y] = x, peso[x] += peso[y];
	edge[y] = t;
}

int dfs(int u, int p)
{
	if (u == p) return 0;

	return nivel[u] = dfs(pai[u], p)+1;
}

int lca(int u, int v)
{
	int ans = 0;

	while (u != v)
	{
		if (nivel[u] > nivel[v]) ans = max(ans, edge[u]), u = pai[u];
		else ans = max(ans, edge[v]), v = pai[v];
	}

	return ans;
}

void solve_small(void)
{
	for (int i = 1; i <= q; i++)
	{
		string op;
		cin >> op;

		if (op == "toggle")
		{
			int ind;
			scanf("%d", &ind);

			query[i] = {0, ind};
		}
		else
		{
			int l, r;
			scanf("%d %d", &l, &r);

			query[i] = {1, -1};

			int ans = 0;
			for (int j = 1; j <= n; j++)
				mark[j] = on[j];

			for (int j = 1; j <= i; j++)
			{
				if (query[j].type == 1)
				{
					bool ok = 1;
					for (int k = l; k < r; k++)
						if (!mark[k])
							ok = 0;

					if (ok) ans++;
				}
				else
				{

					bool ok = 1;
					for (int k = l; k < r; k++)
						if (!mark[k])
							ok = 0;

					if (ok) ans++;

					mark[query[j].ind] = !mark[query[j].ind];
				}
			}

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

void solve_two(void)
{
	for (int i = 1; i <= q; i++)
	{
		if (event[i].type == 0)
		{
			int ind = event[i].l;

			on[ind] = !on[ind];

			if (!on[ind])
				ans[ind] += (i-last[ind]);

			last[ind] = i;
		}
		else
		{
			int l = event[i].l, r = event[i].r;

			int tot = ans[l];

			if (on[l]) tot += (i-last[l]);

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

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

	init();

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

		if (x == '1')
		{
			on[i] = true;
			Join(i, i+1, 0);
		}
	}

	if (n <= 100 && q <= 100)
	{
		solve_small();
		return 0;
	}

	bool ok = 1;

	for (int i = 1; i <= q; i++)
	{
		string s;
		cin >> s;

		if (s == "toggle")
		{
			int ind;
			scanf("%d", &ind);

			event[i] = {0, ind, -1};

			Join(ind, ind+1, i);
		}
		else
		{
			int l, r;
			scanf("%d %d", &l, &r);

			event[i] = {1, l, r};

			if (r != l+1) ok = 0;
		}
	}

	if (ok)
	{
		solve_two();
		return 0;
	}

	for (int i = 1; i <= n+1; i++)
		dfs(i, Find(i));

	for (int i = 1; i <= q; i++)
	{
		if (event[i].type)
		{
			int l = event[i].l, r = event[i].r;

			int first = lca(l, r);

			if (first > i || Find(l) != Find(r)) printf("0\n");
			else printf("%d\n", i-first);
		}
	}
}

Compilation message (stderr)

street_lamps.cpp: In function 'void solve_two()':
street_lamps.cpp:147:24: warning: unused variable 'r' [-Wunused-variable]
    int l = event[i].l, r = event[i].r;
                        ^
street_lamps.cpp: In function 'void solve_small()':
street_lamps.cpp:85:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ind);
    ~~~~~^~~~~~~~~~~~
street_lamps.cpp:92:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp: In function 'int main()':
street_lamps.cpp:160:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~~
street_lamps.cpp:167:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &x);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:192:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ind);
    ~~~~~^~~~~~~~~~~~
street_lamps.cpp:201:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &l, &r);
    ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 20 / 20
• Subtask 2: 20 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20