oj.uz

Submission #56122

# Submission time Handle Problem Language Result Execution time Memory
56122 2018-07-10T05:02:39 Z 김세빈(#1581) Growing Trees (BOI11_grow) C++11
100 / 100
 214 ms 3324 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] = 2e9;
	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 116 ms 2648 KB Output is correct
2 Correct 214 ms 2648 KB Output is correct
3 Correct 159 ms 2648 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2648 KB Output is correct
2 Correct 6 ms 2648 KB Output is correct
3 Correct 6 ms 2648 KB Output is correct
4 Correct 5 ms 2648 KB Output is correct
5 Correct 64 ms 2648 KB Output is correct
6 Correct 106 ms 2648 KB Output is correct
7 Correct 9 ms 2648 KB Output is correct
8 Correct 50 ms 2648 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 2648 KB Output is correct
2 Correct 75 ms 2648 KB Output is correct
3 Correct 3 ms 2648 KB Output is correct
4 Correct 74 ms 2648 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 2648 KB Output is correct
2 Correct 100 ms 2648 KB Output is correct
3 Correct 14 ms 2648 KB Output is correct
4 Correct 106 ms 2648 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 2648 KB Output is correct
2 Correct 137 ms 2820 KB Output is correct
3 Correct 24 ms 2820 KB Output is correct
4 Correct 146 ms 2820 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 2820 KB Output is correct
2 Correct 159 ms 2820 KB Output is correct
3 Correct 138 ms 2820 KB Output is correct
4 Correct 26 ms 2820 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 2988 KB Output is correct
2 Correct 108 ms 2988 KB Output is correct
3 Correct 124 ms 2988 KB Output is correct
4 Correct 23 ms 2988 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 170 ms 2988 KB Output is correct
2 Correct 138 ms 2988 KB Output is correct
3 Correct 45 ms 2988 KB Output is correct
4 Correct 134 ms 2988 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 3032 KB Output is correct
2 Correct 176 ms 3032 KB Output is correct
3 Correct 202 ms 3068 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 3324 KB Output is correct