oj.uz

Submission #56148

# Submission time Handle Problem Language Result Execution time Memory
56148 2018-07-10T06:05:36 Z 정원준(#1583) Growing Trees (BOI11_grow) C++11
80 / 100
 1000 ms 3904 KB 
#include <bits/stdc++.h>
#define L long long

using namespace std;

L tr[400040];
L n,m;

void update(L now,L S,L E,L s,L e,L val){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		tr[now]+=val;
		return;
	}
	L mid=(S+E)/2;
	update(now*2,S,mid,s,e,val);
	update(now*2+1,mid+1,E,s,e,val);
}

L get(L now,L S,L E,L loc){
	if(S>loc||E<loc) return 0;
	if(S==E) return tr[now];
	L mid=(S+E)/2;
	return tr[now]+get(now*2,S,mid,loc)+get(now*2+1,mid+1,E,loc);
}

L a[100010];

char str[11];

void biryo(L num,L least){
	L s=1,e=n;
	if(get(1,1,n,n)<least) return;
	while(s<e)
	{
		L mid=(s+e)/2;
		if(get(1,1,n,mid)>=least) e=mid;
		else s=mid+1;
	}
	L start=s;
	if(s+num-1>=n) update(1,1,n,s,n,1);
	else
	{
		L last=s+num-1;
		//printf("%lld %lld\n",start,last);
		L val=get(1,1,n,last);
		L laststarts=1,laststarte=n;
		while(laststarts<laststarte)
		{
			L mid=(laststarts+laststarte)/2;
			if(get(1,1,n,mid)>=val) laststarte=mid;
			else laststarts=mid+1;
		}
		L lastends=1,lastende=n;
		while(lastends<lastende)
		{
			L mid=(lastends+lastende+1)/2;
			if(get(1,1,n,mid)>val) lastende=mid-1;
			else lastends=mid;
		}
		//printf("%lld %lld\n",laststarts,lastends);
		update(1,1,n,start,laststarts-1,1);
		start=laststarts;
		L end=lastends;
		L middle=last;
		middle=end-(middle-start);
		update(1,1,n,middle,end,1);
	}
}

L fin(L x,L y){
	if(get(1,1,n,1)>y||get(1,1,n,n)<x) return 0;
	L laststarts=1,laststarte=n;
	while(laststarts<laststarte)
	{
		L mid=(laststarts+laststarte)/2;
		if(get(1,1,n,mid)>=x) laststarte=mid;
		else laststarts=mid+1;
	}
	L lastends=1,lastende=n;
	while(lastends<lastende)
	{
		L mid=(lastends+lastende+1)/2;
		if(get(1,1,n,mid)>y) lastende=mid-1;
		else lastends=mid;
	}
	return lastends-laststarts+1;		
}

int main()
{
	scanf("%lld %lld",&n,&m);
	L i,j;
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&a[i]);
	}
	sort(a+1,a+n+1);
	for(i=1;i<=n;i++)
	{
		update(1,1,n,i,i,a[i]);
	}
	/*for(j=1;j<=n;j++)
	{
		printf("%lld ",get(1,1,n,j));
	}
	puts("");*/
	for(i=1;i<=m;i++)
	{
		L x,y;
		scanf("%s %lld %lld",str,&x,&y);
		if(str[0]=='F')
		{
			biryo(x,y);
	/*for(j=1;j<=n;j++)
	{
		printf("%lld ",get(1,1,n,j));
	}
	puts("");*/
		}
		else
		{
			printf("%lld\n",fin(x,y));
		}
	}
}

Compilation message

grow.cpp: In function 'int main()':
grow.cpp:94:6: warning: unused variable 'j' [-Wunused-variable]
  L i,j;
      ^
grow.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld %lld",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~
grow.cpp:97:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld",&a[i]);
   ~~~~~^~~~~~~~~~~~~~
grow.cpp:112:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s %lld %lld",str,&x,&y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 3312 KB Output is correct
2 Correct 946 ms 3312 KB Output is correct
3 Correct 329 ms 3312 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3312 KB Output is correct
2 Correct 14 ms 3312 KB Output is correct
3 Correct 7 ms 3312 KB Output is correct
4 Correct 8 ms 3312 KB Output is correct
5 Correct 318 ms 3312 KB Output is correct
6 Correct 432 ms 3312 KB Output is correct
7 Correct 27 ms 3312 KB Output is correct
8 Correct 172 ms 3312 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 3312 KB Output is correct
2 Correct 472 ms 3312 KB Output is correct
3 Correct 9 ms 3312 KB Output is correct
4 Correct 219 ms 3312 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 417 ms 3312 KB Output is correct
2 Correct 462 ms 3312 KB Output is correct
3 Correct 42 ms 3312 KB Output is correct
4 Correct 378 ms 3312 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 621 ms 3312 KB Output is correct
2 Correct 821 ms 3548 KB Output is correct
3 Correct 125 ms 3548 KB Output is correct
4 Correct 258 ms 3548 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 734 ms 3548 KB Output is correct
2 Correct 881 ms 3548 KB Output is correct
3 Correct 332 ms 3548 KB Output is correct
4 Correct 108 ms 3548 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 663 ms 3628 KB Output is correct
2 Correct 602 ms 3628 KB Output is correct
3 Correct 297 ms 3628 KB Output is correct
4 Correct 140 ms 3628 KB Output is correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 3820 KB Output is correct
2 Execution timed out 1032 ms 3820 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 951 ms 3904 KB Output is correct