oj.uz

Submission #361464

# Submission time Handle Problem Language Result Execution time Memory
361464 2021-01-30T09:27:38 Z pure_mem Growing Trees (BOI11_grow) C++14
90 / 100
 1000 ms 5100 KB 
#include <bits/stdc++.h>

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

using namespace std;

const int N = 2e5 + 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 tmpL = get_pos(get(1, 1, n, tmp, tmp + l - 1));
			int tmpR = get_pos(get(1, 1, n, tmp, tmp + l - 1) + 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:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d %d\n", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
grow.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d", a + i);
      |   ~~~~~^~~~~~~~~~~~~
grow.cpp:66:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |  scanf("\n"), sort(a + 1, a + n + 1);
      |  ~~~~~^~~~~~
grow.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |   scanf("%c %d %d\n", &tc, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 478 ms 4076 KB Output is correct
2 Correct 823 ms 4828 KB Output is correct
3 Correct 305 ms 4460 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 364 KB Output is correct
2 Correct 9 ms 492 KB Output is correct
3 Correct 10 ms 492 KB Output is correct
4 Correct 6 ms 364 KB Output is correct
5 Correct 295 ms 1592 KB Output is correct
6 Correct 295 ms 1772 KB Output is correct
7 Correct 20 ms 620 KB Output is correct
8 Correct 222 ms 1388 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 1772 KB Output is correct
2 Correct 344 ms 1900 KB Output is correct
3 Correct 5 ms 492 KB Output is correct
4 Correct 281 ms 1652 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 335 ms 2156 KB Output is correct
2 Correct 409 ms 1900 KB Output is correct
3 Correct 47 ms 620 KB Output is correct
4 Correct 369 ms 2028 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 601 ms 2924 KB Output is correct
2 Correct 773 ms 4104 KB Output is correct
3 Correct 102 ms 1388 KB Output is correct
4 Correct 259 ms 4076 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 3820 KB Output is correct
2 Correct 792 ms 4204 KB Output is correct
3 Correct 329 ms 4332 KB Output is correct
4 Correct 117 ms 1388 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 515 ms 3948 KB Output is correct
2 Correct 471 ms 4204 KB Output is correct
3 Correct 324 ms 4460 KB Output is correct
4 Correct 88 ms 1388 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 814 ms 4740 KB Output is correct
2 Correct 794 ms 4324 KB Output is correct
3 Correct 110 ms 3692 KB Output is correct
4 Correct 581 ms 4276 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 785 ms 4460 KB Output is correct
2 Correct 824 ms 4600 KB Output is correct
3 Execution timed out 1095 ms 4628 KB Time limit exceeded

Subtask #10
10.0 / 10.0

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