oj.uz

Submission #711564

# Submission time Handle Problem Language Result Execution time Memory
711564 2023-03-17T08:47:55 Z Pherokung Growing Trees (BOI11_grow) C++14
100 / 100
 273 ms 2848 KB 
#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define F first
#define S second
int n,m,a[MAXN],x,y,fen[MAXN*8],l,r,l2,r2;
char ch[5];

void update(int pos,int v){
	for(;pos<=n;pos+=(pos&(-pos))) fen[pos] += v;
}

int query(int pos){
	int sum = 0;
	for(;pos>0;pos-=(pos&(-pos))) sum += fen[pos];
	return sum;
}

pair<int,int> find_bound(int v){
	int be,ed,mid,l,r;
	
	be = 1, ed = n;
	while(be <= ed){
		mid = (be+ed)/2;
		if(query(mid) < v) be = mid+1;
		else ed = mid-1;
	}
	l = be;
	
	be = 1, ed = n;
	while(be <= ed){
		mid = (be+ed)/2;
		if(query(mid) <= v) be = mid+1;
		else ed = mid-1;
	}
	r = ed;
	return {l,r};
}

void debug(){
	printf("========\n");
	for(int i=1;i<=n;i++) printf("%d ",query(i));
	printf("\n========\n");
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++) update(i,a[i]-a[i-1]);
	
	//debug();
	for(int i=1;i<=m;i++){
		scanf("%s%d%d",ch,&x,&y);
		if(ch[0] == 'F'){
			l = find_bound(y).F;
			r = min(l + x - 1, n);
			if(query(r) != query(r+1) || r == n) update(l,1), update(r+1,-1);
			else{
				pair<int,int> LR2 = find_bound(query(r));
				l2 = LR2.F, r2 = LR2.S;
				update(l,1), update(l2,-1);
				update(r2-(x-(l2-l))+1,1), update(r2+1,-1);
				//printf("??? %d %d , %d %d : %d\n",l,r,l2,r2,r2-(x-(l2-l))+1);
			}
		}
		else{
			l = find_bound(x).F;
			r = find_bound(y).S;
			printf("%d\n",r-l+1);
		}
		//debug();
	}
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |  scanf("%d%d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~
grow.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
grow.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   scanf("%s%d%d",ch,&x,&y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1092 KB Output is correct
2 Correct 132 ms 2712 KB Output is correct
3 Correct 49 ms 2580 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 212 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 4 ms 212 KB Output is correct
4 Correct 2 ms 356 KB Output is correct
5 Correct 167 ms 1412 KB Output is correct
6 Correct 273 ms 1520 KB Output is correct
7 Correct 5 ms 324 KB Output is correct
8 Correct 45 ms 1100 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 688 KB Output is correct
2 Correct 91 ms 1652 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 55 ms 1264 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 1740 KB Output is correct
2 Correct 119 ms 1612 KB Output is correct
3 Correct 6 ms 436 KB Output is correct
4 Correct 87 ms 1704 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 1380 KB Output is correct
2 Correct 134 ms 2356 KB Output is correct
3 Correct 36 ms 844 KB Output is correct
4 Correct 55 ms 2240 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 1468 KB Output is correct
2 Correct 134 ms 2344 KB Output is correct
3 Correct 49 ms 2508 KB Output is correct
4 Correct 25 ms 832 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 1672 KB Output is correct
2 Correct 87 ms 2316 KB Output is correct
3 Correct 67 ms 2580 KB Output is correct
4 Correct 25 ms 836 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 2108 KB Output is correct
2 Correct 133 ms 2144 KB Output is correct
3 Correct 30 ms 1804 KB Output is correct
4 Correct 85 ms 2168 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 1232 KB Output is correct
2 Correct 130 ms 2652 KB Output is correct
3 Correct 89 ms 2848 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 2704 KB Output is correct