Submission #163957

#	Time	Username	Problem	Language	Result	Execution time	Memory
163957		luciocf	Street Lamps (APIO19_street_lamps)	C++14	40 / 100	384 ms	14072 KiB

street_lamps

#include <bits/stdc++.h>

using namespace std;

const int maxn = 3e5+10;

struct Event
{
	int op, a, b;
} event[maxn];

int n, q;

bool mark[maxn], aux[maxn];

void sub_1(void)
{
	for (int i = 1; i <= q; i++)
	{
		if (event[i].op == 0) continue;

		int ans = 0;

		for (int j = 1; j <= n; j++)
			aux[j] = mark[j];

		for (int j = 1; j <= i; j++)
		{
			bool ok = 1;
			for (int l = event[i].a; l < event[i].b; l++)
				if (!aux[l])
					ok = 0;

			if (ok) ans++;

			if (event[j].op == 0)
				aux[event[j].a] = !aux[event[j].a];
		}

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

int last[maxn];
int tot[maxn];

void sub_2(void)
{
	for (int i = 1; i <= n; i++)
	{
		if (mark[i]) last[i] = 0;
		else last[i] = -1;
	}

	for (int i = 1; i <= q; i++)
	{
		if (event[i].op == 0)
		{
			if (last[event[i].a] == -1) last[event[i].a] = i;
			else tot[event[i].a] += i-last[event[i].a], last[event[i].a] = -1;
		}
		else
		{
			if (last[event[i].a] == -1) printf("%d\n", tot[event[i].a]);
			else printf("%d\n", tot[event[i].a]+i-last[event[i].a]);
		}
	}
}

int tree[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		if (!mark[l]) tree[node] = 1e9+10;
		else tree[node] = 0;
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

void upd(int node, int l, int r, int pos, int v)
{
	if (l == r)
	{
		tree[node] = v;
		return;
	}

	int mid = (l+r)>>1;

	if (pos <= mid) upd(2*node, l, mid, pos, v);
	else upd(2*node+1, mid+1, r, pos, v);

	tree[node] = max(tree[2*node], tree[2*node+1]);
}

int query(int node, int l, int r, int a, int b)
{
	if (l > b || r < a) return 0;
	if (l >= a && r <= b) return tree[node];

	int mid = (l+r)>>1;

	return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b));
}

void sub_3(void)
{
	build(1, 1, n);

	for (int i = 1; i <= q; i++)
	{
		if (event[i].op == 0) upd(1, 1, n, event[i].a, i);
		else printf("%d\n", max(0, i-query(1, 1, n, event[i].a, event[i].b-1)));
	}
}

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

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

		if (x == '1') mark[i] = 1;
		else mark[i] = 0;
	}

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

		if (op[0] == 't')
		{
			int a;
			scanf("%d", &a);

			event[i] = {0, a, -1};
		}
		else
		{
			int a, b;
			scanf("%d %d", &a, &b);

			event[i] = {1, a, b};
		}
	}

	bool check_2 = 1;
	for (int i = 1; i <= q; i++)
		if (event[i].op == 0 && event[i].a != event[i].b-1)
			check_2 = 0;

	if (n <= 100 && q <= 100) sub_1();
	else if (check_2) sub_2();
	else sub_3();
}

Compilation message (stderr)

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:127: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:132:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &x);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:146:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:153:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &a, &b);
    ~~~~~^~~~~~~~~~~~~~~~~

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