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