oj.uz

Submission #56170

# Submission time Handle Problem Language Result Execution time Memory
56170 2018-07-10T07:23:43 Z 핵아싸^^(#2105) Growing Trees (BOI11_grow) C++11
100 / 100
 775 ms 3204 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[121212];
struct node {
	int lazy, g;
}tree[815151];
void lazy(int w) {
	int c1 = w * 2, c2 = w * 2 + 1;
	tree[c1].lazy += tree[w].lazy; tree[c2].lazy += tree[w].lazy;
	tree[c1].g += tree[w].lazy; tree[c2].g += tree[w].lazy;
	tree[w].lazy = 0;
}
int min(int a, int b) { if (a < b)return a; return b; }
int max(int a, int b) { if (a > b)return a; return b; }
void insert_g(int w, int s, int e, int l, int r, int g) {
	int m = (s + e) / 2;
	if (s != e)lazy(w);
	if (s == l&&e == r) {
		tree[w].lazy += g;
		tree[w].g += g;
		return;
	}
	if (l <= m)insert_g(w * 2, s, m, l, min(m, r), g);
	if (m + 1 <= r)insert_g(w * 2 + 1, m + 1, e, max(l, m + 1), r, g);
}
int get_x(int w, int s, int e, int x) {
	if (s == e)return tree[w].g;
	lazy(w);
	int m = (s + e) / 2;
	if (x <= m)return get_x(w * 2, s, m, x);
	else return get_x(w * 2 + 1, m + 1, e, x);
}
int n, m, tn;
void print_state() {
	for (int i = 1; i <= n; i++) {
		printf("%d ", get_x(1, 1, tn, i));
	}
	puts("");
}
void q1(int h, int c) {
	int s = 1, e = n, hw = -1;
	while (s <= e) {
		int m = (s + e) / 2;
		int k = get_x(1, 1, tn, m);
		if (k >= h) {
			hw = m;
			e = m - 1;
		}
		else s = m + 1;
	}
	if (hw == -1)return;
	h = get_x(1, 1, tn, hw);
	if (hw + c - 1 > n) {
		insert_g(1, 1, tn, hw, n + 1, 1);
		return;
	}
	int x = get_x(1, 1, tn, hw + c - 1);
	s = hw, e = hw+c-2; int xm1w = hw-1;
	while (s <= e) {
		int m = (s + e) / 2;
		int k = get_x(1, 1, tn, m);
		if (k == x)e = m - 1;
		else s = m + 1, xm1w = m;
	}
	s = hw + c - 1, e = n; int xw;
	while (s <= e) {
		int m = (s + e) / 2;
		int k = get_x(1, 1, tn, m);
		if (k == x)s = m + 1, xw = m;
		else e = m - 1;
	}
	if (xm1w - hw + 1 != 0) insert_g(1, 1, tn, hw, xm1w, 1);
	c -= xm1w - hw + 1;
	insert_g(1, 1, tn, xw - c + 1, xw, 1);
}
int q2(int l, int r) {
	int s = 1, e = n, lw = n+1;
	while (s <= e) {
		int m = (s + e) / 2;
		int k = get_x(1, 1, tn, m);
		if (l <= k)e = m - 1, lw = m;
		else s = m + 1;
	}
	s = 1, e = n; int rw = 0;
	while (s <= e) {
		int m = (s + e) / 2;
		int k = get_x(1, 1, tn, m);
		if (k <= r)s = m + 1, rw = m;
		else e = m - 1;
	}
	return rw - lw + 1;
}
int main() {
	scanf("%d%d", &n, &m);
	int i, j;
	for (tn = 1; tn < (n+1); tn *= 2);
	for (i = 1; i <= n; i++)scanf("%d", &a[i]);
	sort(a + 1, a + n + 1);
	for (i = 1; i <= n; i++)insert_g(1, 1, tn, i, i, a[i]);
	for (i = 1; i <= m; i++) {
		char x; scanf(" %c", &x);
		if (x == 'F') {
			int h, c; scanf("%d%d", &c, &h);
			q1(h, c);
		}
		else {
			int l, r; scanf("%d%d", &l, &r);
			printf("%d\n",q2(l, r));
		}
	}
	return 0;
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:96:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j;
         ^
grow.cpp:95:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:98:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++)scanf("%d", &a[i]);
                          ~~~~~^~~~~~~~~~~~~
grow.cpp:102:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   char x; scanf(" %c", &x);
           ~~~~~^~~~~~~~~~~
grow.cpp:104:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int h, c; scanf("%d%d", &c, &h);
              ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:108:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int l, r; scanf("%d%d", &l, &r);
              ~~~~~^~~~~~~~~~~~~~~~
grow.cpp: In function 'void q1(int, int)':
grow.cpp:75:24: warning: 'xw' may be used uninitialized in this function [-Wmaybe-uninitialized]
  insert_g(1, 1, tn, xw - c + 1, xw, 1);
                     ~~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 404 ms 2296 KB Output is correct
2 Correct 775 ms 2532 KB Output is correct
3 Correct 376 ms 2532 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2532 KB Output is correct
2 Correct 9 ms 2532 KB Output is correct
3 Correct 13 ms 2532 KB Output is correct
4 Correct 6 ms 2532 KB Output is correct
5 Correct 263 ms 2532 KB Output is correct
6 Correct 325 ms 2532 KB Output is correct
7 Correct 19 ms 2532 KB Output is correct
8 Correct 164 ms 2532 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 250 ms 2532 KB Output is correct
2 Correct 287 ms 2532 KB Output is correct
3 Correct 9 ms 2532 KB Output is correct
4 Correct 183 ms 2532 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 2532 KB Output is correct
2 Correct 332 ms 2532 KB Output is correct
3 Correct 36 ms 2532 KB Output is correct
4 Correct 294 ms 2532 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 2532 KB Output is correct
2 Correct 713 ms 2532 KB Output is correct
3 Correct 100 ms 2532 KB Output is correct
4 Correct 386 ms 2532 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 2532 KB Output is correct
2 Correct 566 ms 2532 KB Output is correct
3 Correct 386 ms 2532 KB Output is correct
4 Correct 90 ms 2532 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 2532 KB Output is correct
2 Correct 509 ms 2876 KB Output is correct
3 Correct 408 ms 2876 KB Output is correct
4 Correct 82 ms 2876 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 569 ms 2876 KB Output is correct
2 Correct 678 ms 2876 KB Output is correct
3 Correct 139 ms 2876 KB Output is correct
4 Correct 414 ms 2876 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 2876 KB Output is correct
2 Correct 599 ms 2876 KB Output is correct
3 Correct 763 ms 2876 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 628 ms 3204 KB Output is correct