oj.uz

Submission #163957

# Submission time Handle Problem Language Result Execution time Memory
163957 2019-11-16T12:13:50 Z luciocf Street Lamps (APIO19_street_lamps) C++14
40 / 100
 384 ms 14072 KB 
#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

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.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 4688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 313 ms 9092 KB Output is correct
6 Correct 351 ms 13304 KB Output is correct
7 Correct 384 ms 14072 KB Output is correct
8 Correct 294 ms 13344 KB Output is correct
9 Correct 213 ms 6904 KB Output is correct
10 Correct 233 ms 7432 KB Output is correct
11 Correct 232 ms 7672 KB Output is correct
12 Correct 288 ms 11948 KB Output is correct
13 Correct 295 ms 13268 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Incorrect 260 ms 4688 KB Output isn't correct
9 Halted 0 ms 0 KB -