oj.uz

Submission #56120

# Submission time Handle Problem Language Result Execution time Memory
56120 2018-07-10T04:58:06 Z 김세빈(#1581) Growing Trees (BOI11_grow) C++11
80 / 100
 171 ms 3280 KB 
#include <bits/stdc++.h>

using namespace std;

int A[101010];
int T[303030], L[303030];
int n, sz;

int get_idx(int p, int s, int e, int v)
{
	if(s == e) return s - 1;
	
	if(T[p<<1] > v - L[p]) return get_idx(p<<1, s, (s+e>>1), v - L[p]);
	else return get_idx(p<<1|1, (s+e>>1)+1, e, v - L[p]);
}

int get_val(int p, int s, int e, int v)
{
	if(s == e) return T[p];
	
	if(v <= (s+e>>1)) return get_val(p<<1, s, (s+e>>1), v) + L[p];
	else return get_val(p<<1|1, (s+e>>1)+1, e, v) + L[p];
}

void grow(int p, int s, int e, int l, int r)
{
	if(r < s || e < l) return;
	if(l <= s && e <= r){
		T[p] ++, L[p] ++;
		return;
	}
	
	grow(p<<1, s, (s+e>>1), l, r);
	grow(p<<1|1, (s+e>>1)+1, e, l, r);
	
	T[p] = T[p<<1|1] + L[p];
}

int main()
{
	int i, q, a, b, v, l, r;
	char str[3];
	
	scanf("%d%d", &n, &q);
	
	for(sz=1;sz<=n;sz<<=1);
	
	for(i=0;i<n;i++){
		scanf("%d", A+i);
	}
	
	sort(A, A+n);
	
	for(i=0;i<n;i++) T[sz+i] = A[i];
	for(;i<sz;i++) T[sz+i] = 1e9;
	for(i=sz-1;i;i--) T[i] = T[i<<1|1];
	
	for(;q--;){
		scanf("%s%d%d", str, &a, &b);
		if(*str == 'F'){
			l = get_idx(1, 0, sz-1, b - 1) + 1;
			if(l >= n) continue;
			
			if(l + a - 1 < n){
				v = get_val(1, 0, sz-1, l + a - 1);
				r = get_idx(1, 0, sz-1, v - 1);
			}
			else r = n - 1;
			
			if(l <= r){
				grow(1, 0, sz-1, l, r);
				a -= r - l + 1;
				if(a == 0 || r == n - 1) continue;
			}
			
			r = get_idx(1, 0, sz-1, v);
			l = r - a + 1;
			grow(1, 0, sz-1, l, r);
		}
		else{
			r = get_idx(1, 0, sz-1, b);
			l = get_idx(1, 0, sz-1, a - 1);
			printf("%d\n", r - l);
		}
	}
	
	return 0;
}

Compilation message

grow.cpp: In function 'int get_idx(int, int, int, int)':
grow.cpp:13:51: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(T[p<<1] > v - L[p]) return get_idx(p<<1, s, (s+e>>1), v - L[p]);
                                                  ~^~
grow.cpp:14:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else return get_idx(p<<1|1, (s+e>>1)+1, e, v - L[p]);
                               ~^~
grow.cpp: In function 'int get_val(int, int, int, int)':
grow.cpp:21:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)) return get_val(p<<1, s, (s+e>>1), v) + L[p];
           ~^~
grow.cpp:21:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  if(v <= (s+e>>1)) return get_val(p<<1, s, (s+e>>1), v) + L[p];
                                             ~^~
grow.cpp:22:32: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  else return get_val(p<<1|1, (s+e>>1)+1, e, v) + L[p];
                               ~^~
grow.cpp: In function 'void grow(int, int, int, int, int)':
grow.cpp:33:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  grow(p<<1, s, (s+e>>1), l, r);
                 ~^~
grow.cpp:34:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  grow(p<<1|1, (s+e>>1)+1, e, l, r);
                ~^~
grow.cpp: In function 'int main()':
grow.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &q);
  ~~~~~^~~~~~~~~~~~~~~~
grow.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", A+i);
   ~~~~~^~~~~~~~~~~
grow.cpp:59:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s%d%d", str, &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:13:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
  if(T[p<<1] > v - L[p]) return get_idx(p<<1, s, (s+e>>1), v - L[p]);
               ~~^~~~~~
grow.cpp:41:18: note: 'v' was declared here
  int i, q, a, b, v, l, r;
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 2552 KB Output is correct
2 Correct 145 ms 2632 KB Output is correct
3 Correct 88 ms 2632 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2632 KB Output is correct
2 Correct 7 ms 2632 KB Output is correct
3 Correct 5 ms 2632 KB Output is correct
4 Correct 5 ms 2632 KB Output is correct
5 Correct 59 ms 2632 KB Output is correct
6 Correct 69 ms 2632 KB Output is correct
7 Incorrect 7 ms 2632 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 2632 KB Output is correct
2 Correct 77 ms 2632 KB Output is correct
3 Correct 3 ms 2632 KB Output is correct
4 Correct 42 ms 2632 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2632 KB Output is correct
2 Correct 64 ms 2632 KB Output is correct
3 Correct 10 ms 2632 KB Output is correct
4 Correct 69 ms 2632 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 2632 KB Output is correct
2 Correct 171 ms 2728 KB Output is correct
3 Correct 22 ms 2728 KB Output is correct
4 Correct 84 ms 2728 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 2728 KB Output is correct
2 Correct 111 ms 2824 KB Output is correct
3 Correct 132 ms 2824 KB Output is correct
4 Correct 20 ms 2824 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 2856 KB Output is correct
2 Correct 89 ms 2984 KB Output is correct
3 Correct 99 ms 2984 KB Output is correct
4 Correct 21 ms 2984 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 128 ms 2984 KB Output is correct
2 Correct 114 ms 2984 KB Output is correct
3 Incorrect 39 ms 2984 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 2984 KB Output is correct
2 Correct 130 ms 3032 KB Output is correct
3 Correct 156 ms 3032 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 3280 KB Output is correct