Submission #1257050

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257050		terracottalite	Growing Trees (BOI11_grow)	C++20	100 / 100	85 ms	1676 KiB

grow

#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 100005;
int n, m;
int b[N] = { 0 };
int a[N] = { 0 };

void update(int p, int v) {
	while (p <= n) {
		b[p] += v;
		p += p&-p;
	}
}

int query(int r) {
	r = min(r, n);
	int res = 0;
	while (r > 0) {
		res += b[r];
		r -= r&-r;
	}
	return res;
}

int bs(int h) {
	int l = 0;
	int r = n+1;

	while (r-l>1) {
		int m = (l+r)/2;
		if (query(m) < h) {
			l = m;
		} else {
			r = m;
		}
	}

	return r;
}

int main()
{
	scanf("%d %d", &n, &m);

	for (int i=1;i<=n;i++) {
		scanf("%d", &a[i]);
	}

	sort(a+1, a+n+1);

	for (int i=1;i<=n;i++) {
		update(i, a[i]-a[i-1]);
	}

	/*
	map<int, int> mp;

	for (int i=n;i>0;i--) {
		mp[a[i]] = i;
	}
	*/

	char ty[4];
	while (m--) {
		scanf("%s", ty);

		if (ty[0] == 'F') {
			int c, h;
			scanf("%d %d", &c, &h);

			int r = bs(h);
			int lm = bs(query(r+c)+1)-1;
			int nm = bs(query(r+c));
			int nc = c-(nm-r);

			if (r+c > n) {
				update(r, 1);
				continue;
			}

			if (query(r) != query(r+c)) {
				update(r, 1);
				update(nm, -1);
			}

			update(lm+1, -1);
			update(lm-nc+1, 1);

			//printf("%d %d %d %d\n", r ,lm ,nm, nc);

			/*
			putchar('x');
			for (int i=1;i<=n;i++) {
				printf(" %d", query(i));
			}
			putchar('\n');
			*/
		} else {
			int l, r;
			scanf("%d %d", &l, &r);

			printf("%d\n", bs(r+1) - bs(l));
		}
	}
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:45:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   45 |         scanf("%d %d", &n, &m);
      |         ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:48:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |                 scanf("%d", &a[i]);
      |                 ~~~~~^~~~~~~~~~~~~
grow.cpp:67:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |                 scanf("%s", ty);
      |                 ~~~~~^~~~~~~~~~
grow.cpp:71:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |                         scanf("%d %d", &c, &h);
      |                         ~~~~~^~~~~~~~~~~~~~~~~
grow.cpp:102:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  102 |                         scanf("%d %d", &l, &r);
      |                         ~~~~~^~~~~~~~~~~~~~~~~

• 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