oj.uz

Submission #711556

# Submission time Handle Problem Language Result Execution time Memory
711556 2023-03-17T08:37:11 Z Pherokung Growing Trees (BOI11_grow) C++14
0 / 100
 1000 ms 3404 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],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 = l + x - 1;
			if(query(r) != query(r+1)) update(l,1), update(r,-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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1073 ms 1652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 4 ms 320 KB Output is correct
3 Runtime error 2 ms 468 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 1032 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 596 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 20 ms 1960 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 48 ms 2296 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1079 ms 1212 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 131 ms 2624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 2224 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 158 ms 3404 KB Output isn't correct
2 Halted 0 ms 0 KB -