oj.uz

Submission #56181

# Submission time Handle Problem Language Result Execution time Memory
56181 2018-07-10T07:45:41 Z 정원준(#1583) Growing Trees (BOI11_grow) C++11
100 / 100
 893 ms 4028 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 460 ms 3464 KB Output is correct
2 Correct 776 ms 3464 KB Output is correct
3 Correct 285 ms 3464 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3464 KB Output is correct
2 Correct 10 ms 3464 KB Output is correct
3 Correct 12 ms 3464 KB Output is correct
4 Correct 7 ms 3464 KB Output is correct
5 Correct 247 ms 3464 KB Output is correct
6 Correct 364 ms 3464 KB Output is correct
7 Correct 19 ms 3464 KB Output is correct
8 Correct 111 ms 3464 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 3464 KB Output is correct
2 Correct 318 ms 3464 KB Output is correct
3 Correct 6 ms 3464 KB Output is correct
4 Correct 166 ms 3464 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 3464 KB Output is correct
2 Correct 442 ms 3464 KB Output is correct
3 Correct 60 ms 3464 KB Output is correct
4 Correct 342 ms 3464 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 3464 KB Output is correct
2 Correct 777 ms 3692 KB Output is correct
3 Correct 90 ms 3692 KB Output is correct
4 Correct 204 ms 3692 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 3692 KB Output is correct
2 Correct 760 ms 3712 KB Output is correct
3 Correct 260 ms 3712 KB Output is correct
4 Correct 123 ms 3712 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 3712 KB Output is correct
2 Correct 580 ms 3756 KB Output is correct
3 Correct 231 ms 3756 KB Output is correct
4 Correct 100 ms 3756 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 761 ms 3756 KB Output is correct
2 Correct 622 ms 3756 KB Output is correct
3 Correct 118 ms 3756 KB Output is correct
4 Correct 314 ms 3756 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 588 ms 3824 KB Output is correct
2 Correct 748 ms 3824 KB Output is correct
3 Correct 781 ms 3824 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 893 ms 4028 KB Output is correct