比赛 聪明的工作员 评测结果 AAAAWWWWAWAWWWWWWWWW
题目名称 聪明的质监员 最终得分 30
用户昵称 补魔 运行时间 0.493 s
代码语言 C++ 内存使用 6.42 MiB
提交时间 2017-03-21 20:06:03
显示代码纯文本
#include<cstdlib>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m;
long long S,Y;
long long ans;
int l[200010],r[200010],w[200010],y[200010];
long long s[200010],d[200010]; 
long long Abs(long long x,long long y)
{
	if (x>y) return (x-y);
	else return (y-x);
} 

int Main()
{
	long long left=0,right=0,mid;
	ans=100;ans*=100000;
	for (int i=1;i<=n;i++) 
	if (w[i]>right) right=w[i];
	right+=100;
	while (left<right)
	{
		mid=(left+right)/2;
		memset(s,0,sizeof(s));
		memset(d,0,sizeof(d));
		for (int i=1;i<=n;i++)
		if (w[i]>=mid) s[i]=s[i-1]+y[i],d[i]=d[i-1]+1;
		else s[i]=s[i-1],d[i]=d[i-1];Y=0;  
		for (int i=1;i<=m;i++)
		{
			long long temp_x=s[r[i]]-s[l[i]-1];
			long long temp_y=d[r[i]]-d[l[i]-1];
			long long temp_z=temp_x*temp_y;  
			Y+=temp_z;
		}
		if (Abs(Y,S)<ans) 
		ans=Abs(Y,S);
		if (Y>S) 
		left=mid+1;
		else right=mid;
	 }
	 cout<<ans;
} 
int main()
{
	freopen("qc.in","r",stdin);
	freopen("qc.out","w",stdout);  
	cin>>n>>m>>S;
	for (int i=1;i<=n;i++) 
	scanf("%d%d",&w[i],&y[i]);
	for (int i=1;i<=m;i++) 
	scanf("%d%d",&l[i],&r[i]);
	
	Main();
	fclose(stdin); 
	fclose(stdout);
	return 0; 
}