Submission #5893030


Source Code Expand

#include <bits/stdc++.h>
#define clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define fi first
#define se second
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"---------------"#x"---------------"<<endl
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
						For(_x,L,R)cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> vi;
LL read(){
	LL x=0,f=0;
	char ch=getchar();
	while (!isdigit(ch))
		f|=ch=='-',ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return f?-x:x;
}
const int N=2e5+5;
int n;
struct Point{
	int x,y;
	void get(){
		x=read(),y=read();
	}
}p[N],p1,p2;
bool cmp(Point a,Point b){
	if (a.y!=b.y)
		return a.y<b.y;
	return a.x<b.x;
}
int lim=1e8;
int Ha[N],hs;
void LSH(){
	int c=0;
	For(i,1,n)
		if (p1.x<=p[i].x&&p[i].x<=p2.x&&p1.y<=p[i].y&&p[i].y<=p2.y)
			p[++c]=p[i];
	n=c,hs=0;
	For(i,1,n)	
		Ha[++hs]=p[i].x;
	Ha[++hs]=p1.x,Ha[++hs]=p2.x;
	sort(Ha+1,Ha+hs+1);
	hs=unique(Ha+1,Ha+hs+1)-Ha-1;
	For(i,1,n)
		p[i].x=lower_bound(Ha+1,Ha+hs+1,p[i].x)-Ha;
	p1.x=lower_bound(Ha+1,Ha+hs+1,p1.x)-Ha;
	p2.x=lower_bound(Ha+1,Ha+hs+1,p2.x)-Ha;
}
namespace bit{
	int c[N];
	void init(){
		clr(c);
	}
	void Add(int x,int d){
		for (;x<=n+2;x+=x&-x)
			c[x]=max(c[x],d);
	}
	int Ask(int x){
		int ans=0;
		for (;x;x-=x&-x)
			ans=max(ans,c[x]);
		return ans;
	}
}
double PI=acos(-1.0);
int main(){
	p1.get(),p2.get();
	n=read();
	For(i,1,n)
		p[i].get();
	if (p1.x>p2.x)
		swap(p1,p2);
	if (p1.y>p2.y){
		p1.y=lim-p1.y-1;
		p2.y=lim-p2.y-1;
		For(i,1,n)
			p[i].y=lim-p[i].y-1;
	}
	LSH();
	bit::init();
	sort(p+1,p+n+1,cmp);
	For(i,1,n){
		int v=bit::Ask(p[i].x)+1;
		bit::Add(p[i].x,v);
	}
	int len=bit::Ask(p2.x);
	double ans=100.0*(Ha[p2.x]+p2.y-Ha[p1.x]-p1.y);
	ans+=(PI/2-2)*10*len;
	if (len==min(Ha[p2.x]-Ha[p1.x],p2.y-p1.y)+1)
		ans+=PI/2*10*len;
	printf("%.13lf\n",ans);
	return 0;
}

Submission Info

Submission Time
Task C - Fountain Walk
User zhouzhendong
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2155 Byte
Status WA
Exec Time 100 ms
Memory 3328 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 41
WA × 6
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_01.txt, subtask_1_02.txt, subtask_1_03.txt, subtask_1_04.txt, subtask_1_05.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_41.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 1024 KB
sample_02.txt AC 2 ms 1024 KB
sample_03.txt AC 2 ms 1024 KB
subtask_1_01.txt AC 2 ms 1024 KB
subtask_1_02.txt AC 2 ms 1024 KB
subtask_1_03.txt AC 2 ms 1024 KB
subtask_1_04.txt AC 2 ms 1024 KB
subtask_1_05.txt AC 2 ms 1024 KB
subtask_1_06.txt AC 2 ms 1024 KB
subtask_1_07.txt AC 2 ms 1024 KB
subtask_1_08.txt AC 2 ms 1024 KB
subtask_1_09.txt AC 12 ms 1536 KB
subtask_1_10.txt WA 23 ms 2176 KB
subtask_1_11.txt WA 7 ms 1280 KB
subtask_1_12.txt WA 96 ms 3328 KB
subtask_1_13.txt AC 25 ms 2304 KB
subtask_1_14.txt WA 12 ms 1536 KB
subtask_1_15.txt WA 6 ms 1280 KB
subtask_1_16.txt WA 96 ms 3328 KB
subtask_1_17.txt AC 20 ms 2048 KB
subtask_1_18.txt AC 16 ms 1792 KB
subtask_1_19.txt AC 16 ms 1792 KB
subtask_1_20.txt AC 93 ms 3328 KB
subtask_1_21.txt AC 96 ms 3328 KB
subtask_1_22.txt AC 96 ms 3328 KB
subtask_1_23.txt AC 96 ms 3328 KB
subtask_1_24.txt AC 2 ms 1024 KB
subtask_1_25.txt AC 2 ms 1024 KB
subtask_1_26.txt AC 2 ms 1024 KB
subtask_1_27.txt AC 2 ms 1024 KB
subtask_1_28.txt AC 27 ms 2560 KB
subtask_1_29.txt AC 32 ms 2560 KB
subtask_1_30.txt AC 100 ms 3328 KB
subtask_1_31.txt AC 53 ms 3328 KB
subtask_1_32.txt AC 57 ms 3328 KB
subtask_1_33.txt AC 55 ms 3328 KB
subtask_1_34.txt AC 62 ms 3328 KB
subtask_1_35.txt AC 71 ms 3328 KB
subtask_1_36.txt AC 75 ms 3328 KB
subtask_1_37.txt AC 73 ms 3328 KB
subtask_1_38.txt AC 60 ms 3328 KB
subtask_1_39.txt AC 80 ms 3328 KB
subtask_1_40.txt AC 61 ms 3328 KB
subtask_1_41.txt AC 61 ms 3328 KB