oj.uz

Submission #361465

# Submission time Handle Problem Language Result Execution time Memory
361465 2021-01-30T09:28:43 Z pure_mem Growing Trees (BOI11_grow) C++14
90 / 100
 1000 ms 3372 KB 
#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 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:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |  scanf("%d %d\n", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
grow.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |   scanf("%d", a + i);
      |   ~~~~~^~~~~~~~~~~~~
grow.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   67 |  scanf("\n"), sort(a + 1, a + n + 1);
      |  ~~~~~^~~~~~
grow.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |   scanf("%c %d %d\n", &tc, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 474 ms 3052 KB Output is correct
2 Correct 810 ms 2896 KB Output is correct
3 Correct 318 ms 2668 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 492 KB Output is correct
2 Correct 9 ms 364 KB Output is correct
3 Correct 10 ms 364 KB Output is correct
4 Correct 8 ms 384 KB Output is correct
5 Correct 282 ms 748 KB Output is correct
6 Correct 319 ms 876 KB Output is correct
7 Correct 24 ms 492 KB Output is correct
8 Correct 224 ms 744 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 876 KB Output is correct
2 Correct 347 ms 876 KB Output is correct
3 Correct 6 ms 364 KB Output is correct
4 Correct 311 ms 748 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 876 KB Output is correct
2 Correct 424 ms 876 KB Output is correct
3 Correct 47 ms 492 KB Output is correct
4 Correct 331 ms 1132 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 617 ms 1900 KB Output is correct
2 Correct 789 ms 3068 KB Output is correct
3 Correct 100 ms 1004 KB Output is correct
4 Correct 279 ms 2796 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 2972 KB Output is correct
2 Correct 796 ms 2924 KB Output is correct
3 Correct 317 ms 2668 KB Output is correct
4 Correct 99 ms 1004 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 510 ms 2924 KB Output is correct
2 Correct 481 ms 3096 KB Output is correct
3 Correct 318 ms 2668 KB Output is correct
4 Correct 91 ms 1132 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 2964 KB Output is correct
2 Correct 795 ms 2924 KB Output is correct
3 Correct 107 ms 2796 KB Output is correct
4 Correct 574 ms 3052 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 3136 KB Output is correct
2 Correct 791 ms 3052 KB Output is correct
3 Execution timed out 1054 ms 2924 KB Time limit exceeded

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 739 ms 3372 KB Output is correct