oj.uz

Submission #139000

# Submission time Handle Problem Language Result Execution time Memory
139000 2019-07-31T07:18:44 Z tinjyu Sails (IOI07_sails) C++14
60 / 100
 1000 ms 2632 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 380 KB Output is correct
2 Correct 113 ms 1120 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 888 KB Output is correct
2 Correct 172 ms 1032 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 791 ms 1404 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1067 ms 1836 KB Time limit exceeded

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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