Submission #5795022
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(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 Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
emak |
Language |
C++14 (Clang 3.8.0) |
Score |
900 |
Code Size |
3663 Byte |
Status |
AC |
Exec Time |
502 ms |
Memory |
15068 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 |
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 |