oj.uz

답안 #382656

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
382656 2021-03-28T01:38:28 Z rainboy 가로등 (APIO19_street_lamps) C
20 / 100
 611 ms 20716 KB 
#include <stdio.h>
#include <string.h>

#define N	300000
#define Q	300000
#define M	(Q * 3)

int ft[N], n;

void update(int i, int x) {
	while (i < n) {
		ft[i] += x;
		i |= i + 1;
	}
}

int query(int i) {
	int x = 0;

	while (i >= 0) {
		x += ft[i];
		i &= i + 1, i--;
	}
	return x;
}

int type[Q], ll_[Q], rr_[Q], ans[Q];
int ll[M], rr[M], xx[M], hh[M], hh_[M];

void merge(int l, int m, int r) {
	int i, j, k;

	i = l, j = m, k = l;
	while (i < m && j < r)
		hh_[k++] = rr[hh[i]] < rr[hh[j]] ? hh[i++] : hh[j++];
	while (i < m)
		hh_[k++] = hh[i++];
	while (j < r)
		hh_[k++] = hh[j++];
	memcpy(hh + l, hh_ + l, (r - l) * sizeof *hh_);
}

void solve(int l, int r) {
	int m, l_, m_, r_, i, j;

	if (r - l == 1)
		return;
	m = (l + r) / 2;
	solve(l, m), solve(m, r);
	l_ = ll_[l], m_ = ll_[m], r_ = rr_[r - 1];
	for (j = r_ - 1, i = m_ - 1; j >= m_; j--) {
		int hi, hj = hh[j];

		while (i >= l_ && rr[hi = hh[i]] >= rr[hj]) {
			if (xx[hi] < 0 || type[xx[hi] - 1] == 1)
				update(ll[hi], xx[hi]);
			i--;
		}
		if (xx[hj] > 0 && type[xx[hj] - 1] == 2)
			ans[xx[hj] - 1] += query(ll[hj]);
	}
	while (++i < m_) {
		int hi = hh[i];

		if (xx[hi] < 0 || type[xx[hi] - 1] == 1)
			update(ll[hi], -xx[hi]);
	}
	merge(l_, m_, r_);
}

int main() {
	static char cc[N + 1];
	static int pp[N], qq[N];
	int q, m, h, i;

	scanf("%d%d%s", &n, &q, cc);
	for (i = 0; i < n; i++)
		if (cc[i] == '1') {
			int p = i > 0 && cc[i - 1] == '1' ? pp[i - 1] : i;

			pp[i] = p, qq[p] = i;
			update(i, 1);
		}
	m = 0;
	for (h = 0; h < q; h++) {
		static char s[8];

		scanf("%s", s);
		ll_[h] = m;
		if (s[0] == 't') {
			int p, q;

			scanf("%d", &i), i--;
			type[h] = 1;
			if (cc[i] == '0') {
				cc[i] = '1';
				p = i > 0 && cc[i - 1] == '1' ? pp[i - 1] : i, q = i + 1 < n && cc[i + 1] == '1' ? qq[i + 1] : i;
				if (p < i)
					ll[m] = p, rr[m] = i - 1, xx[m] = h + 1, m++;
				ll[m] = p, rr[m] = q, xx[m] = -(h + 1), m++;
				qq[p] = q, pp[q] = p;
				if (i < q)
					ll[m] = i + 1, rr[m] = q, xx[m] = h + 1, m++;
				update(i, 1);
			} else {
				cc[i] = '0';
				p = pp[i], q = qq[i];
				if (p < i) {
					ll[m] = p, rr[m] = i - 1, xx[m] = -(h + 1), m++;
					qq[p] = i - 1, pp[i - 1] = p;
				}
				ll[m] = p, rr[m] = q, xx[m] = h + 1, m++;
				if (i < q) {
					ll[m] = i + 1, rr[m] = q, xx[m] = -(h + 1), m++;
					qq[i + 1] = q, pp[q] = i + 1;
				}
				update(i, -1);
			}
		} else {
			int l, r;

			scanf("%d%d", &l, &r), l--, r -= 2;
			type[h] = 2;
			ll[m] = l, rr[m] = r, xx[m] = h + 1, m++;
			if (query(r) - query(l - 1) == r - l + 1)
				ans[h] += h + 1;
		}
		rr_[h] = m;
	}
	for (h = 0; h < m; h++)
		hh[h] = h;
	memset(ft, 0, n * sizeof *ft);
	solve(0, q);
	for (h = 0; h < q; h++)
		if (type[h] == 2)
			printf("%d\n", ans[h]);
	return 0;
}

Compilation message

street_lamps.c: In function 'main':
street_lamps.c:76:2: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   76 |  scanf("%d%d%s", &n, &q, cc);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.c:88:3: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   88 |   scanf("%s", s);
      |   ^~~~~~~~~~~~~~
street_lamps.c:93:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
   93 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~
street_lamps.c:122:4: warning: ignoring return value of 'scanf', declared with attribute warn_unused_result [-Wunused-result]
  122 |    scanf("%d%d", &l, &r), l--, r -= 2;
      |    ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 388 ms 15320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 492 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 2 ms 364 KB Output is correct
5 Correct 559 ms 20716 KB Output is correct
6 Correct 611 ms 20356 KB Output is correct
7 Correct 551 ms 19052 KB Output is correct
8 Correct 346 ms 15596 KB Output is correct
9 Correct 150 ms 9836 KB Output is correct
10 Correct 163 ms 10604 KB Output is correct
11 Correct 162 ms 10860 KB Output is correct
12 Correct 328 ms 13036 KB Output is correct
13 Correct 347 ms 15724 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 364 KB Output isn't correct
2 Halted 0 ms 0 KB -