Submission #91807

#	Time	Username	Problem	Language	Result	Execution time	Memory
91807		ics0503	Growing Trees (BOI11_grow)	C++17	100 / 100	578 ms	4680 KiB

grow

#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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10