Submission #5793964


Source Code Expand

#include<iostream>
#include<iomanip>
//#include<cstdio>
#include<vector>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#include<cassert>
using namespace std;
typedef long long ll;
ll Xs, Ys, Xg, Yg;
int N;
const int Nmax = 2e5;
const double PI = 3.1415926535897;
ll X[Nmax], Y[Nmax];

template <class T>
class SegmentTree{
	vector<T> v;
	T def;
	int n;
	public:
	template<class I>
	SegmentTree(I first, I last, T default_value){
		n = 1;
		def = default_value;
		while(n < last-first) n <<= 1;
		v = vector<T>(2*n-1, default_value);
		copy(first, last, v.begin()+n-1);
		for(int i=n-2; i>=0; i--) v[i] = merge(v[2*i+1], v[2*i+2]);
	}
	SegmentTree(int length, T default_value){
		n = 1;
		def = default_value;
		while(n < length) n <<= 1;
		v = vector<T>(2*n-1, default_value);
		for(int i=n-2; i>=0; i--) v[i] = merge(v[2*i+1], v[2*i+2]);
	}
	SegmentTree(vector<T> initial_data, T default_value):
	SegmentTree(initial_data.begin(), initial_data.end(), default_value){}
	void update(int idx, T val){
		idx += n-1;
		v[idx] = val;
		while(idx > 0){
			idx = (idx-1)/2;
			v[idx] = merge(v[2*idx+1], v[2*idx+2]);
		}
	}
	T q(int a, int b, int k, int l, int r){
		if(a<=l&&r<=b) return v[k];
		if(b<=l||r<=a) return def;
		return merge(q(a, b, 2*k+1, l, (l+r)/2), q(a, b, 2*k+2, (l+r)/2, r));
	}
	T query(int a, int b){
		return q(a, b, 0, 0, n);
	}
	T merge(T left, T right);
};

template <>
int SegmentTree<int>::merge(int a, int b){
	return max(a, b);
}

int main(){
	cin >> Xs >> Ys >> Xg >> Yg;
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> X[i] >> Y[i];
	}

	vector<pair<ll, int> > xs, ys;
	for(int i=0; i<N; i++){
		if(Xs <= X[i] && X[i] <= Xg){
			if(Ys <= Y[i] && Y[i] <= Yg){
				xs.push_back({X[i], i});
				ys.push_back({Y[i], i});
			} else if(Yg <= Y[i] && Y[i] <= Ys){
				xs.push_back({X[i], i});
				ys.push_back({-Y[i], i});
			}
		} else if(Xg <= X[i] && X[i] <= Xs){
			if(Ys <= Y[i] && Y[i] <= Yg){
				xs.push_back({-X[i], i});
				ys.push_back({Y[i], i});
			} else if(Yg <= Y[i] && Y[i] <= Ys){
				xs.push_back({-X[i], i});
				ys.push_back({-Y[i], i});
			}
		}
	}
	if(Xs > Xg){
		Xs = -Xs;
		Xg = -Xg;
	}
	if(Ys > Yg){
		Ys = -Ys;
		Yg = -Yg;
	}

	sort(xs.begin(), xs.end());
	sort(ys.begin(), ys.end());

	vector<int> xc(N), yc(N);

	for(int i=0; i<xs.size(); i++){
		xc[xs[i].second] = i;
		yc[ys[i].second] = i;
	}

	cout << setprecision(15);
	if(Xs == Xg){
		auto it = lower_bound(xs.begin(), xs.end(), make_pair(Xs, 0));
		double ans = 100*abs(Xs-Xg);
		if(it != xs.end() && it->first == Xs){
			ll yi = Y[it->second];
			if((Ys < yi && yi < Yg) || (Ys < -yi && -yi < Yg)){
				ans += 10*PI-20;
			}
		}
		cout << ans << endl;
		return 0;
	}

	if(Ys == Yg){
		auto it = lower_bound(ys.begin(), ys.end(), make_pair(Ys, 0));
		double ans = 100*abs(Xs-Xg);
		if(it != ys.end() && it->first == Ys){
			ll xi = X[it->second];
			if((Xs < xi && xi < Xg) || (Xs < -xi && -xi < Xg)){
				ans += 10*PI-20;
			}
		}
		cout << ans << endl;
		return 0;
	}
	//cout << xs.size() << endl;

	SegmentTree<int> st_max(N+1, 0);
	for(auto p: xs){
		//cout << p.first << " " << yc[p.second] << " " << st_max.query(0, yc[p.second]) << endl;
		st_max.update(yc[p.second], st_max.query(0, yc[p.second]) + 1);
	}

	int k = st_max.query(0, N);
	//cout << k << endl;

	cout << 100*(abs(Xs-Xg) + abs(Ys-Yg)) - k * (20 - 5*PI) << endl;

	return 0;
}

Submission Info

Submission Time
Task C - Fountain Walk
User emak
Language C++14 (Clang 3.8.0)
Score 0
Code Size 3520 Byte
Status WA
Exec Time 538 ms
Memory 14812 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 38
WA × 9
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 6 ms 760 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt WA 141 ms 1920 KB
subtask_1_10.txt WA 296 ms 5760 KB
subtask_1_11.txt WA 77 ms 1664 KB
subtask_1_12.txt WA 487 ms 14172 KB
subtask_1_13.txt AC 314 ms 3968 KB
subtask_1_14.txt WA 145 ms 2944 KB
subtask_1_15.txt WA 70 ms 1536 KB
subtask_1_16.txt WA 487 ms 13276 KB
subtask_1_17.txt AC 260 ms 4352 KB
subtask_1_18.txt AC 203 ms 3584 KB
subtask_1_19.txt AC 199 ms 3712 KB
subtask_1_20.txt AC 467 ms 14812 KB
subtask_1_21.txt AC 489 ms 13276 KB
subtask_1_22.txt AC 486 ms 13276 KB
subtask_1_23.txt AC 488 ms 14556 KB
subtask_1_24.txt WA 1 ms 256 KB
subtask_1_25.txt WA 1 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 1 ms 256 KB
subtask_1_28.txt AC 331 ms 7296 KB
subtask_1_29.txt AC 407 ms 7296 KB
subtask_1_30.txt AC 500 ms 13532 KB
subtask_1_31.txt AC 372 ms 13276 KB
subtask_1_32.txt AC 367 ms 13532 KB
subtask_1_33.txt AC 370 ms 14812 KB
subtask_1_34.txt AC 371 ms 13276 KB
subtask_1_35.txt AC 538 ms 13404 KB
subtask_1_36.txt AC 482 ms 13276 KB
subtask_1_37.txt AC 452 ms 13532 KB
subtask_1_38.txt AC 453 ms 14428 KB
subtask_1_39.txt AC 452 ms 13276 KB
subtask_1_40.txt AC 450 ms 13532 KB
subtask_1_41.txt AC 458 ms 13660 KB