Submission #6346248
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
using ld = long double;
using pii = pair<int,int>;
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)
#define Max(a,b) a=max(a,b)
#define IN(i,a,b) (a<=i&&i<=b)
#define pb push_back
const int mxn = 3e5;
struct BIT {
int tree[mxn];
BIT() {
f(i,0,mxn) tree[i] = 0;
}
void add(int i, int v) {
for (; i<mxn; i|=i+1)
Max(tree[i],v);
}
int sum(int i) {
int ans = 0;
for (; i >= 0; i = (i&(i+1))-1) {
Max(ans,tree[i]);
}
return ans;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
clock_t start = clock();
#endif
int x1,x2,y1,y2,n;
cin>>x1>>y1>>x2>>y2>>n;
vector<pii> points;
f(i,0,n) {
int x,y; cin>>x>>y;
if ((IN(x,x1,x2)||IN(x,x2,x1))&&
(IN(y,y1,y2)||IN(y,y2,y1)))
points.pb({x,y});
}
n = points.size();
if (x1>x2) {
x1 *= -1; x2 *= -1;
f(i,0,n) points[i].first *= -1;
}
if (y1>y2) {
y1 *= -1; y2 *= -1;
f(i,0,n) points[i].second *= -1;
}
sort(begin(points),end(points));
map<int,int> fi;
f(i,0,n) fi[points[i].second] = 0;
int t = 0;
for (pii pp : fi)
fi[pp.first] = t++;
bool inc = 1;
f(i,1,n) if (points[i].first < points[i-1].first)
inc = 0;
ld ans = 100LL*(abs(x1-x2)+abs(y1-y2));
if (inc && n && ((x1==points[0].first&&x2==points[n-1].first)
|| (y1 == points[0].second && y2 == points[n-1].second))) {
ans += M_PI*5;
}
int num = 0;
BIT ds;
f(i,0,n) {
int z = ds.sum(fi[points[i].second])+1;
ds.add(fi[points[i].second],z);
Max(num,z);
}
ans += 1LL*num*(M_PI*5-20);
cout << setprecision(30) << ans << endl;
#ifdef LOCAL
cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
m1sch3f |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1911 Byte |
Status |
WA |
Exec Time |
222 ms |
Memory |
12400 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 |
2 ms |
1408 KB |
sample_02.txt |
AC |
2 ms |
1408 KB |
sample_03.txt |
AC |
2 ms |
1408 KB |
subtask_1_01.txt |
AC |
2 ms |
1408 KB |
subtask_1_02.txt |
AC |
2 ms |
1408 KB |
subtask_1_03.txt |
AC |
2 ms |
1408 KB |
subtask_1_04.txt |
WA |
2 ms |
1408 KB |
subtask_1_05.txt |
AC |
2 ms |
1408 KB |
subtask_1_06.txt |
AC |
2 ms |
1408 KB |
subtask_1_07.txt |
AC |
2 ms |
1408 KB |
subtask_1_08.txt |
AC |
2 ms |
1408 KB |
subtask_1_09.txt |
AC |
15 ms |
1408 KB |
subtask_1_10.txt |
AC |
29 ms |
1408 KB |
subtask_1_11.txt |
AC |
9 ms |
1408 KB |
subtask_1_12.txt |
AC |
198 ms |
12400 KB |
subtask_1_13.txt |
AC |
31 ms |
1408 KB |
subtask_1_14.txt |
AC |
15 ms |
1408 KB |
subtask_1_15.txt |
AC |
8 ms |
1408 KB |
subtask_1_16.txt |
AC |
195 ms |
12400 KB |
subtask_1_17.txt |
AC |
25 ms |
1408 KB |
subtask_1_18.txt |
WA |
20 ms |
1408 KB |
subtask_1_19.txt |
WA |
21 ms |
1536 KB |
subtask_1_20.txt |
WA |
195 ms |
12400 KB |
subtask_1_21.txt |
WA |
196 ms |
12400 KB |
subtask_1_22.txt |
WA |
188 ms |
12400 KB |
subtask_1_23.txt |
WA |
141 ms |
12400 KB |
subtask_1_24.txt |
AC |
2 ms |
1408 KB |
subtask_1_25.txt |
AC |
2 ms |
1408 KB |
subtask_1_26.txt |
AC |
2 ms |
1408 KB |
subtask_1_27.txt |
AC |
2 ms |
1408 KB |
subtask_1_28.txt |
AC |
40 ms |
1792 KB |
subtask_1_29.txt |
AC |
42 ms |
1792 KB |
subtask_1_30.txt |
AC |
222 ms |
12400 KB |
subtask_1_31.txt |
WA |
182 ms |
12400 KB |
subtask_1_32.txt |
WA |
195 ms |
12400 KB |
subtask_1_33.txt |
WA |
174 ms |
12400 KB |
subtask_1_34.txt |
WA |
114 ms |
12400 KB |
subtask_1_35.txt |
AC |
121 ms |
12400 KB |
subtask_1_36.txt |
AC |
216 ms |
12400 KB |
subtask_1_37.txt |
AC |
162 ms |
12400 KB |
subtask_1_38.txt |
AC |
154 ms |
12400 KB |
subtask_1_39.txt |
AC |
140 ms |
12400 KB |
subtask_1_40.txt |
AC |
169 ms |
12400 KB |
subtask_1_41.txt |
AC |
162 ms |
12400 KB |