oj.uz

Submission #361468

# Submission time Handle Problem Language Result Execution time Memory
361468 2021-01-30T09:31:55 Z pure_mem Growing Trees (BOI11_grow) C++14
100 / 100
 920 ms 3256 KB 
#pragma GCC optimize("Ofast")

#include <cstdio>
#include <algorithm>

#define X first
#define Y second
#define MP make_pair
#define ll long long

using namespace std;

const int N = 1e5 + 3;

int n, q, a[N], t[N * 4], tt[N * 4];

void build(int v, int tl, int tr){
	if(tl == tr){
		t[v] = a[tl];
		return;
	}
	int tm = (tl + tr) / 2;
	build(v * 2, tl, tm), build(v * 2 + 1, tm + 1, tr);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
void push(int v){
	if(tt[v] == 0)
		return;
	t[v * 2] += tt[v], t[v * 2 + 1] += tt[v];
	tt[v * 2] += tt[v], tt[v * 2 + 1] += tt[v], tt[v] = 0;
}
void upd(int v, int tl, int tr, int l, int r, int val){
	if(tl > r || l > tr)
		return;
	if(tl >= l && tr <= r){
		t[v] += val, tt[v] += val;
		return;
	}
	push(v);
	int tm = (tl + tr) / 2;
	upd(v * 2, tl, tm, l, r, val), upd(v * 2 + 1, tm + 1, tr, l, r, val);
	t[v] = max(t[v * 2], t[v * 2 + 1]);
}
int get(int v, int tl, int tr, int l, int r){
	if(tl > r || l > tr)
		return 0;
	if(tl >= l && tr <= r)
		return t[v];
	push(v);
	int tm = (tl + tr) / 2;
	return max(get(v * 2, tl, tm, l, r), get(v * 2 + 1, tm + 1, tr, l, r));
}
int get_pos(int val){
	int tl = 1, tr = n;
	while(tl <= tr){
		int tm = (tl + tr) / 2;
		if(get(1, 1, n, 1, tm) >= val)
			tr = tm - 1;
		else
			tl = tm + 1;
	}
	return tr + 1;
}

int main () {
	scanf("%d %d\n", &n, &q);
	for(int i = 1;i <= n;i++)
		scanf("%d", a + i);
	scanf("\n"), sort(a + 1, a + n + 1);
	build(1, 1, n);
	for(;q--;){
		char tc;
		int l, r;
		scanf("%c %d %d\n", &tc, &l, &r);
		if(tc == 'F'){
			int tmp = get_pos(r);
			if(tmp + l - 1 >= n){
				upd(1, 1, n, tmp, n, 1);
				continue;
			}		
			int pet = get(1, 1, n, tmp, tmp + l - 1);
			int tmpL = get_pos(pet);
			int tmpR = get_pos(pet + 1) - 1;
			upd(1, 1, n, tmp, tmpL - 1, 1);
			tmpL = tmpR - ((tmp + l - 1) - tmpL + 1) + 1;
			upd(1, 1, n, tmpL, tmpR, 1);
		}
		else{
			printf("%d\n", get_pos(r + 1) - get_pos(l));
		}
	}
}

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", &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:69:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |  scanf("\n"), sort(a + 1, a + n + 1);
      |  ~~~~~^~~~~~
grow.cpp:74:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   74 |   scanf("%c %d %d\n", &tc, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 3040 KB Output is correct
2 Correct 622 ms 2924 KB Output is correct
3 Correct 237 ms 2796 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 364 KB Output is correct
2 Correct 6 ms 364 KB Output is correct
3 Correct 7 ms 364 KB Output is correct
4 Correct 4 ms 364 KB Output is correct
5 Correct 216 ms 676 KB Output is correct
6 Correct 207 ms 876 KB Output is correct
7 Correct 15 ms 492 KB Output is correct
8 Correct 147 ms 748 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 876 KB Output is correct
2 Correct 239 ms 876 KB Output is correct
3 Correct 4 ms 364 KB Output is correct
4 Correct 185 ms 748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 229 ms 1004 KB Output is correct
2 Correct 278 ms 876 KB Output is correct
3 Correct 32 ms 492 KB Output is correct
4 Correct 236 ms 876 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 1840 KB Output is correct
2 Correct 617 ms 2924 KB Output is correct
3 Correct 72 ms 1160 KB Output is correct
4 Correct 209 ms 2696 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 2868 KB Output is correct
2 Correct 591 ms 3052 KB Output is correct
3 Correct 273 ms 2724 KB Output is correct
4 Correct 72 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 3160 KB Output is correct
2 Correct 358 ms 2924 KB Output is correct
3 Correct 254 ms 2668 KB Output is correct
4 Correct 64 ms 1004 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 654 ms 2924 KB Output is correct
2 Correct 592 ms 3112 KB Output is correct
3 Correct 86 ms 2924 KB Output is correct
4 Correct 434 ms 2924 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 570 ms 3052 KB Output is correct
2 Correct 595 ms 3052 KB Output is correct
3 Correct 920 ms 2796 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 3256 KB Output is correct