oj.uz

Submission #163954

# Submission time Handle Problem Language Result Execution time Memory
163954 2019-11-16T12:05:51 Z luciocf Street Lamps (APIO19_street_lamps) C++14
40 / 100
 294 ms 13300 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 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};
		}
	}

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

Compilation message

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:72: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:77:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &x);
   ~~~~~^~~~~~~~~~~
street_lamps.cpp:91:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &a);
    ~~~~~^~~~~~~~~~
street_lamps.cpp:98: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 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 4756 KB Output is correct
2 Correct 235 ms 8344 KB Output is correct
3 Correct 238 ms 8952 KB Output is correct
4 Correct 276 ms 12248 KB Output is correct
5 Correct 274 ms 11784 KB Output is correct
6 Correct 263 ms 12152 KB Output is correct
7 Correct 286 ms 11932 KB Output is correct
8 Correct 294 ms 13300 KB Output is correct

Subtask #3
0 / 20.0

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

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 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 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 380 KB Output is correct
8 Correct 229 ms 4756 KB Output is correct
9 Correct 235 ms 8344 KB Output is correct
10 Correct 238 ms 8952 KB Output is correct
11 Correct 276 ms 12248 KB Output is correct
12 Correct 274 ms 11784 KB Output is correct
13 Correct 263 ms 12152 KB Output is correct
14 Correct 286 ms 11932 KB Output is correct
15 Correct 294 ms 13300 KB Output is correct
16 Incorrect 4 ms 376 KB Output isn't correct
17 Halted 0 ms 0 KB -