QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#26553#1880. Nikanor Loves GamesCrysfly#WA 3ms15992kbC++111.7kb2022-04-07 18:34:012022-04-29 03:57:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 03:57:43]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:15992kb
  • [2022-04-07 18:34:01]
  • 提交

answer

#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
    char c=getchar();int x=0;bool f=0;
    for(;!isdigit(c);c=getchar())f^=!(c^45);
    for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
    if(f)x=-x;return x;
}
  
#define x first
#define y second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
 
#define maxn 2000005
#define inf 0x3f3f3f3f

int n,res;
int a[maxn],b[maxn],x[maxn];
int t[maxn],len,y[maxn];

int c[maxn];

pii stk[maxn];
int top;
void ins(int x,int y){
	while(top>1 && (y-stk[top].y)*(stk[top].x-stk[top-1].x) > (stk[top].y-stk[top-1].y)*(x-stk[top].x)) --top;
	stk[++top]=mkp(x,y); 
}

inline int F(pii f,int x){
	return f.y-x*f.x;
} 

signed main()
{
	n=read();
	For(i,1,n){
		a[i]=read(),b[i]=read(),x[i]=read();
		if(a[i]>b[i])swap(a[i],b[i]);
		t[++len]=a[i],t[++len]=b[i];
	}
	sort(t+1,t+len+1),len=unique(t+1,t+len+1)-t-1;
	int now=0;
	For(i,1,n)now-=x[i];
	res=now;
	For(i,1,n){
		int p=lower_bound(t+1,t+len+1,a[i])-t;
		c[p]+=x[i];
		p=lower_bound(t+1,t+len+1,b[i])-t;
		c[p]+=x[i];
	}
	ins(0,now);
	For(i,1,len){
		now+=c[i];
		y[i]=now;
		cout<<t[i]<<' '<<y[i]<<endl;
		ins(t[i],y[i]);
	}
	int pos=top;
	For(i,1,len){
		// A = t[i]
		while(pos>1 && F(stk[pos-1],2*t[i])>=F(stk[pos],2*t[i])) --pos;
	//	cout<<"ans: "<<t[i]<<' '<<stk[pos].x<<' '<<y[i]+F(stk[pos],2*t[i])<<endl;
		res=max(res,y[i]+F(stk[pos],2*t[i]));
	}
	printf("%lld.%lld",res>>1,(res%2)*5);
    return 0;
}

/*
a<a[i] -x/2
a[i]<=a<b[i] 0
b[i]>=a x/2

f(A) + f(B) - 2*A*B
枚举 A
tmp + F(B) - A*B 
*/

詳細信息

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 15992kb

input:

2
1 4 15
3 5 10

output:

1 -10
3 0
4 15
5 25
2.5

result:

wrong answer 1st numbers differ - expected: '2.5000000', found: '1.0000000', error = '0.6000000'