oj.uz

답안 #163959

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
163959 2019-11-16T12:14:37 Z luciocf 가로등 (APIO19_street_lamps) C++14
60 / 100
 447 ms 11384 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 == 1 && 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 242 ms 7364 KB Output is correct
2 Correct 233 ms 7796 KB Output is correct
3 Correct 241 ms 7824 KB Output is correct
4 Correct 283 ms 10196 KB Output is correct
5 Correct 275 ms 8288 KB Output is correct
6 Correct 317 ms 9380 KB Output is correct
7 Correct 286 ms 7416 KB Output is correct
8 Correct 290 ms 8696 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 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 315 ms 10596 KB Output is correct
6 Correct 349 ms 10496 KB Output is correct
7 Correct 389 ms 9692 KB Output is correct
8 Correct 447 ms 11384 KB Output is correct
9 Correct 212 ms 6524 KB Output is correct
10 Correct 233 ms 6776 KB Output is correct
11 Correct 233 ms 6904 KB Output is correct
12 Correct 434 ms 9976 KB Output is correct
13 Correct 438 ms 11384 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 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 380 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 242 ms 7364 KB Output is correct
9 Correct 233 ms 7796 KB Output is correct
10 Correct 241 ms 7824 KB Output is correct
11 Correct 283 ms 10196 KB Output is correct
12 Correct 275 ms 8288 KB Output is correct
13 Correct 317 ms 9380 KB Output is correct
14 Correct 286 ms 7416 KB Output is correct
15 Correct 290 ms 8696 KB Output is correct
16 Correct 3 ms 376 KB Output is correct
17 Correct 3 ms 376 KB Output is correct
18 Correct 3 ms 376 KB Output is correct
19 Correct 3 ms 376 KB Output is correct
20 Correct 315 ms 10596 KB Output is correct
21 Correct 349 ms 10496 KB Output is correct
22 Correct 389 ms 9692 KB Output is correct
23 Correct 447 ms 11384 KB Output is correct
24 Correct 212 ms 6524 KB Output is correct
25 Correct 233 ms 6776 KB Output is correct
26 Correct 233 ms 6904 KB Output is correct
27 Correct 434 ms 9976 KB Output is correct
28 Correct 438 ms 11384 KB Output is correct
29 Correct 3 ms 376 KB Output is correct
30 Incorrect 3 ms 376 KB Output isn't correct
31 Halted 0 ms 0 KB -