oj.uz

Submission #345497

# Submission time Handle Problem Language Result Execution time Memory
345497 2021-01-07T13:35:23 Z patrikpavic2 Growing Trees (BOI11_grow) C++17
100 / 100
 293 ms 5100 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 200 ms 3820 KB Output is correct
2 Correct 220 ms 4204 KB Output is correct
3 Correct 146 ms 4096 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1388 KB Output is correct
2 Correct 6 ms 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 4 ms 1388 KB Output is correct
5 Correct 105 ms 2452 KB Output is correct
6 Correct 149 ms 2796 KB Output is correct
7 Correct 15 ms 1516 KB Output is correct
8 Correct 79 ms 2284 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 2796 KB Output is correct
2 Correct 151 ms 2924 KB Output is correct
3 Correct 5 ms 1388 KB Output is correct
4 Correct 91 ms 2412 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 2924 KB Output is correct
2 Correct 150 ms 2764 KB Output is correct
3 Correct 20 ms 1516 KB Output is correct
4 Correct 137 ms 2832 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 3344 KB Output is correct
2 Correct 198 ms 3564 KB Output is correct
3 Correct 35 ms 2028 KB Output is correct
4 Correct 116 ms 3692 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 3436 KB Output is correct
2 Correct 197 ms 3692 KB Output is correct
3 Correct 146 ms 3820 KB Output is correct
4 Correct 28 ms 2028 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 3564 KB Output is correct
2 Correct 165 ms 3860 KB Output is correct
3 Correct 132 ms 4076 KB Output is correct
4 Correct 27 ms 2028 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 219 ms 4288 KB Output is correct
2 Correct 204 ms 3564 KB Output is correct
3 Correct 53 ms 3308 KB Output is correct
4 Correct 153 ms 3564 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 3948 KB Output is correct
2 Correct 205 ms 4120 KB Output is correct
3 Correct 293 ms 4460 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 5100 KB Output is correct