AtCoder Grand Contest 019

Submission #5795022

Source codeソースコード

#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(20);
	if(Xs == Xg){
		auto it = lower_bound(xs.begin(), xs.end(), make_pair(Xs, 0));
		double ans = 100*abs(Ys-Yg);
		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;

	if(k==min(abs(Xs-Xg), abs(Ys-Yg))+1){
		cout << 100*(abs(Xs-Xg) + abs(Ys-Yg)) - (k-1) * (20 - 5*PI) + (10*PI - 20) << endl;
	} else {
		cout << 100*(abs(Xs-Xg) + abs(Ys-Yg)) - k * (20 - 5*PI) << endl;
	}

	return 0;
}

Submission

Task問題 C - Fountain Walk
User nameユーザ名 emak
Created time投稿日時
Language言語 C++14 (Clang 3.8.0)
Status状態 AC
Score得点 900
Source lengthソースコード長 3663 Byte
File nameファイル名
Exec time実行時間 502 ms
Memory usageメモリ使用量 15068 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_01.txt,sample_02.txt,sample_03.txt
All 900 / 900 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_01.txt AC 3 ms 512 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 AC 141 ms 1920 KB
subtask_1_10.txt AC 296 ms 5760 KB
subtask_1_11.txt AC 77 ms 1664 KB
subtask_1_12.txt AC 491 ms 13276 KB
subtask_1_13.txt AC 315 ms 3968 KB
subtask_1_14.txt AC 146 ms 2944 KB
subtask_1_15.txt AC 71 ms 1536 KB
subtask_1_16.txt AC 490 ms 13276 KB
subtask_1_17.txt AC 260 ms 4352 KB
subtask_1_18.txt AC 204 ms 3584 KB
subtask_1_19.txt AC 200 ms 3712 KB
subtask_1_20.txt AC 463 ms 13276 KB
subtask_1_21.txt AC 493 ms 14044 KB
subtask_1_22.txt AC 494 ms 13276 KB
subtask_1_23.txt AC 492 ms 13276 KB
subtask_1_24.txt AC 1 ms 256 KB
subtask_1_25.txt AC 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 339 ms 7296 KB
subtask_1_29.txt AC 409 ms 7296 KB
subtask_1_30.txt AC 502 ms 14428 KB
subtask_1_31.txt AC 374 ms 13276 KB
subtask_1_32.txt AC 368 ms 14172 KB
subtask_1_33.txt AC 377 ms 14172 KB
subtask_1_34.txt AC 380 ms 13276 KB
subtask_1_35.txt AC 459 ms 13276 KB
subtask_1_36.txt AC 482 ms 14044 KB
subtask_1_37.txt AC 454 ms 14172 KB
subtask_1_38.txt AC 452 ms 13276 KB
subtask_1_39.txt AC 459 ms 13660 KB
subtask_1_40.txt AC 457 ms 15068 KB
subtask_1_41.txt AC 452 ms 13276 KB