Submission #139000

#	Time	Username	Problem	Language	Result	Execution time	Memory
139000		tinjyu	Sails (IOI07_sails)	C++14	60 / 100	1070 ms	2632 KiB

sails

#include <iostream>
using namespace std;
int tmp[100005],n,high[100005],h[100005],k[100005];
int qs(int s,int e)
{
	if(s>=e)return 0;
	int l=s,r=e,mid=(h[l]+h[r])/2;
	while(l<=r)
	{
		while(h[l]<mid)l++;
		while(h[r]>mid)r--;
		if(l<=r)
		{
			swap(h[l],h[r]);
			swap(k[l],k[r]);
			l++;
			r--;
		}
	}
	qs(s,r);
	qs(l,e);
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>h[i]>>k[i];
	qs(1,n);
	long long maxhigh=0;
	for(int i=1;i<=n;i++)
	{
		
		for(int j=h[i];j>=h[i]-k[i]+1;j--)high[j]++;
		if(h[i]==k[i])continue;
		int l=1,r=h[i]-k[i]+1,mid=r-1,p=1;
		while(l<=mid && r<=h[i])
		{
			if(high[l]>high[r])
			{
				tmp[p]=high[l];
				p++;
				l++;
			}
			else
			{
				tmp[p]=high[r];
				p++;
				r++;
			}
		}
		while(l<=mid)
		{
			tmp[p]=high[l];
			p++;
			l++;
		}
		while(r<=h[i])
		{
			tmp[p]=high[r];
			p++;
			r++;
		}
		for(int j=1;j<=h[i];j++)high[j]=tmp[j];
	}
	long long int ans=0;
	for(int i=1;i<=h[n];i++)
	{
		ans+=high[i]*(high[i]-1)/2;
	}
	cout<<ans;
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:28:12: warning: unused variable 'maxhigh' [-Wunused-variable]
  long long maxhigh=0;
            ^~~~~~~
sails.cpp: In function 'int qs(int, int)':
sails.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10