oj.uz

Submission #91807

# Submission time Handle Problem Language Result Execution time Memory
91807 2018-12-30T06:18:09 Z ics0503 Growing Trees (BOI11_grow) C++17
100 / 100
 578 ms 4680 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 318 ms 3460 KB Output is correct
2 Correct 483 ms 3904 KB Output is correct
3 Correct 285 ms 3580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 7 ms 376 KB Output is correct
3 Correct 8 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 190 ms 1528 KB Output is correct
6 Correct 241 ms 1776 KB Output is correct
7 Correct 15 ms 420 KB Output is correct
8 Correct 119 ms 1208 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 1784 KB Output is correct
2 Correct 218 ms 2040 KB Output is correct
3 Correct 5 ms 504 KB Output is correct
4 Correct 146 ms 1400 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 1912 KB Output is correct
2 Correct 258 ms 1824 KB Output is correct
3 Correct 28 ms 504 KB Output is correct
4 Correct 270 ms 1912 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 2780 KB Output is correct
2 Correct 423 ms 3192 KB Output is correct
3 Correct 63 ms 1144 KB Output is correct
4 Correct 227 ms 3192 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 386 ms 2948 KB Output is correct
2 Correct 452 ms 3320 KB Output is correct
3 Correct 287 ms 3448 KB Output is correct
4 Correct 65 ms 1016 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 3200 KB Output is correct
2 Correct 329 ms 3576 KB Output is correct
3 Correct 296 ms 3576 KB Output is correct
4 Correct 62 ms 1144 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 3912 KB Output is correct
2 Correct 455 ms 3320 KB Output is correct
3 Correct 82 ms 3064 KB Output is correct
4 Correct 276 ms 3320 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 3644 KB Output is correct
2 Correct 436 ms 3704 KB Output is correct
3 Correct 578 ms 4184 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 4680 KB Output is correct