Submission #345497

#	Time	Username	Problem	Language	Result	Execution time	Memory
345497		patrikpavic2	Growing Trees (BOI11_grow)	C++17	100 / 100	293 ms	5100 KiB

grow

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 500;
const int OFF = (1 << 17);
const int INF = 0x3f3f3f3f;

int T[2 * OFF], prop[2 * OFF];

void refresh(int x){
	if(!prop[x]) return;
	T[x] += prop[x];
	if(x < OFF){
		prop[2 * x] += prop[x];
		prop[2 * x + 1] += prop[x];
	}
	prop[x] = 0;
}

void update(int i, int a, int b, int lo, int hi, int x){
	refresh(i);
	if(lo <= a && b <= hi){
		prop[i] += x; refresh(i);
		return;
	}
	if(a > hi || b < lo) return;
	update(2 * i, a, (a + b) / 2, lo, hi, x);
	update(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
	T[i] = min(T[2 * i], T[2 * i + 1]);
}

int get(int i, int a, int b, int x){
	refresh(i);
	if(a == b) return T[i];
	refresh(2 * i); refresh(2 * i + 1);
	int ans = 0;
	if(x <= (a + b) / 2) 
		ans = get(2 * i, a, (a + b) / 2, x);
	else
		ans = get(2 * i + 1, (a + b) / 2 + 1, b, x);
	T[i] = min(T[2 * i], T[2 * i + 1]);
	return ans;
}


int nadi(int i, int a, int b, int x){
	refresh(i);
	if(a == b) return a;
	refresh(2 * i); refresh(2 * i + 1);
	int ans = 0;
	if(T[2 * i + 1] <= x)
		ans = nadi(2 * i + 1, (a + b) / 2 + 1, b, x);
	else
		ans = nadi(2 * i, a, (a + b) / 2, x);
	T[i] = min(T[2 * i], T[2 * i + 1]);
	return ans;
}

int n, q, A[N];

int main(){
	for(int i = 1;i < OFF;i++) T[OFF + i] = INF;
	scanf("%d%d", &n, &q);
	for(int i = 1;i <= n;i++)
		scanf("%d", A + i);
	sort(A + 1, A + n + 1);
	for(int i = 1;i <= n;i++)
		T[OFF + i] = A[i];
	for(int i = OFF - 1; i ; i--)
		T[i] = min(T[2 * i], T[2 * i + 1]);
	for(int i = 0;i < q;i++){
		char ty; scanf(" %c", &ty);
		if(ty == 'C'){
			int l, r; scanf("%d%d", &l, &r);
			printf("%d\n", nadi(1, 0, OFF - 1, r) - nadi(1, 0, OFF - 1, l - 1));
		}
		if(ty == 'F'){
			int h, c; scanf("%d%d", &c, &h);
			int poc = nadi(1, 0, OFF - 1, h - 1) + 1;
			int krj = poc + c - 1;
			if(krj >= n){
				update(1, 0, OFF - 1, poc, n, 1);
			}
			else{
				int A_krj = get(1, 0, OFF - 1, krj);
				int krj2 = nadi(1, 0, OFF - 1, A_krj - 1);
				int krj3 = nadi(1, 0, OFF - 1, A_krj);
				update(1, 0, OFF - 1, poc, krj2, 1);
				update(1, 0, OFF - 1, krj3 - (c - (krj2 - poc + 1)) + 1, krj3, 1);
			}
		}
	}
	return 0;
}

Compilation message (stderr)

grow.cpp: In function 'int main()':
grow.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:68:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   68 |   scanf("%d", A + i);
      |   ~~~~~^~~~~~~~~~~~~
grow.cpp:75:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   75 |   char ty; scanf(" %c", &ty);
      |            ~~~~~^~~~~~~~~~~~
grow.cpp:77:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   77 |    int l, r; scanf("%d%d", &l, &r);
      |              ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:81:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |    int h, c; scanf("%d%d", &c, &h);
      |              ~~~~~^~~~~~~~~~~~~~~~

• 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