Submission #1542505


Source Code Expand

#include <bits/stdc++.h>

#define FOR(i,b,e) for(int i=(b); i <= (e); ++i)
#define FORD(i,b,e) for(int i=(b); i >= (e); --i)
#define REP(i,n) for(int i=0; i < (n); ++i)
#define SIZE(c) (int) (c).size()
#define ALL(c) (c).begin(), (c).end()
#define PB push_back
#define MP make_pair
#define ST first
#define ND second
#define FWD(i,a,b) for (int i=(a); i<(b); ++i)
#define BCK(i,a,b) for (int i=(a); i>(b); --i)
#define PI 3.14159265358979311600
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

typedef vector < int > VI;
typedef vector<ll> VL;

typedef long double K;

const int N = 400005;
const K pi = acos(-1.0);
const int inf = 1000 * 1000 * 1000 + 7;

int n;
pll s, f, a[N];

vector<int> cmp;

K result = 0.0;

int calc[N];

int t[4*N];

int go(int v, int tl, int tr, int l, int r) {
	if (l > tr || r < tl) return -inf;
	if (l <= tl && r >= tr) return t[v];
	int tm = (tl + tr) / 2;
	return max(go(2*v, tl, tm, l, r), go(2*v+1, tm+1, tr, l, r));
}

void update(int v, int tl, int tr, int pos, int val) {
	if (tl == tr) {
		t[v] = max(t[v], val);
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos <= tm) {
		update(2*v, tl, tm, pos, val);
	} else {
		update(2*v+1, tm+1, tr, pos, val);
	}
	t[v] = max(t[2*v], t[2*v+1]);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> s.x >> s.y;
	cin >> f.x >> f.y;
	cin >> n;

	ll total = abs(s.x - f.x) + abs(s.y - f.y);
	total *= 100;

	if (s > f) swap(s, f);

	REP(i, 4*N) t[i] = -inf;

	int mul = +1;

	if (s.y > f.y) mul = -1;

	f.x *= mul;
	s.x *= mul;
	if (mul == -1) swap(f, s);

	FOR (i, 1, n) {
		cin >> a[i].x >> a[i].y;
		a[i].x *= mul;
		if (a[i] < s || a[i] > f) {
			--i; --n;
		}
	}

	n += 2;
	a[0] = s;
	a[n - 1] = f;

	sort(a, a + n);

	REP(i, n) cmp.push_back(a[i].y);
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end());

	int here = lower_bound(cmp.begin(), cmp.end(), a[0].y) - cmp.begin();
	update(1, 0, SIZE(cmp), here, 0);

	FOR (i, 1, n - 1) {
		here = lower_bound(cmp.begin(), cmp.end(), a[i].y) - cmp.begin();
		calc[i] = go(1, 0, SIZE(cmp), 0, here) + 1;
		update(1, 0, SIZE(cmp), here, calc[i]);
	}
	ll cnt = calc[n - 1] - 1;

	result += (K)cnt*(-20.0 + pi*5.0);
	if (cnt == min(abs(s.x - f.x), abs(s.y - f.y)) + 1) {
		result += pi*5.0;
	}

	cout << setprecision(15) << fixed << total + result << '\n';

	return 0;
}

Submission Info

Submission Time
Task C - Fountain Walk
User nobik
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2594 Byte
Status AC
Exec Time 166 ms
Memory 13688 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 47
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 4 ms 8448 KB
sample_02.txt AC 4 ms 8448 KB
sample_03.txt AC 4 ms 8448 KB
subtask_1_01.txt AC 4 ms 8448 KB
subtask_1_02.txt AC 4 ms 8448 KB
subtask_1_03.txt AC 4 ms 8448 KB
subtask_1_04.txt AC 4 ms 8448 KB
subtask_1_05.txt AC 4 ms 8448 KB
subtask_1_06.txt AC 4 ms 8448 KB
subtask_1_07.txt AC 4 ms 8448 KB
subtask_1_08.txt AC 4 ms 8448 KB
subtask_1_09.txt AC 16 ms 8448 KB
subtask_1_10.txt AC 30 ms 8448 KB
subtask_1_11.txt AC 10 ms 8448 KB
subtask_1_12.txt AC 120 ms 13688 KB
subtask_1_13.txt AC 89 ms 11132 KB
subtask_1_14.txt AC 42 ms 10880 KB
subtask_1_15.txt AC 26 ms 10752 KB
subtask_1_16.txt AC 119 ms 13688 KB
subtask_1_17.txt AC 26 ms 8448 KB
subtask_1_18.txt AC 76 ms 11132 KB
subtask_1_19.txt AC 77 ms 11132 KB
subtask_1_20.txt AC 117 ms 13688 KB
subtask_1_21.txt AC 119 ms 13688 KB
subtask_1_22.txt AC 119 ms 13688 KB
subtask_1_23.txt AC 122 ms 13688 KB
subtask_1_24.txt AC 4 ms 8448 KB
subtask_1_25.txt AC 4 ms 8448 KB
subtask_1_26.txt AC 4 ms 8448 KB
subtask_1_27.txt AC 4 ms 8448 KB
subtask_1_28.txt AC 89 ms 11132 KB
subtask_1_29.txt AC 61 ms 10880 KB
subtask_1_30.txt AC 166 ms 13688 KB
subtask_1_31.txt AC 117 ms 13688 KB
subtask_1_32.txt AC 104 ms 13688 KB
subtask_1_33.txt AC 105 ms 13688 KB
subtask_1_34.txt AC 107 ms 13688 KB
subtask_1_35.txt AC 113 ms 13688 KB
subtask_1_36.txt AC 156 ms 13688 KB
subtask_1_37.txt AC 120 ms 13688 KB
subtask_1_38.txt AC 122 ms 13688 KB
subtask_1_39.txt AC 117 ms 13688 KB
subtask_1_40.txt AC 115 ms 13688 KB
subtask_1_41.txt AC 115 ms 13688 KB