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 |
|
|
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 |