Submission #1550626
Source Code Expand
#include <bits/stdc++.h>
#define forn(i, n) for (llong i = 0ll; i < (llong) n; ++i)
#define fornn(i, l, r) for (llong i = (llong) l; i < (llong) r; ++i)
#define size(x) ((int) (x.size()))
using namespace std;
typedef long long llong;
const llong inf = (llong) 1e+9 + 7ll;
const llong linf = (llong) 1e+18 + 7ll;
const long double eps = (long double) 1e-9;
const long double pi = acosl((long double) -1.0);
const int alph = 26;
mt19937 mrand(random_device{} ());
template<typename T, typename U> inline llong umin(const T& a, const U& b) { return a < b ? a : b; }
template<typename T, typename U> inline llong umax(const T& a, const U& b) { return a > b ? a : b; }
static char buff[(int) 2e6 + 17]; // reads std::string
const int maxn = (1 << 22);
struct pt
{
int x, y;
pt() { }
};
int H[maxn], F[maxn], used[maxn];
struct hash_table
{
hash_table() { }
int getpos(int h) const
{
int i = h % maxn;
for (; used[i] && H[i] != h; ++i) if (i + 1 == maxn) i = -1;
return i;
}
int& operator[](int h)
{
int i = getpos(h);
H[i] = h;
used[i] = 1;
return F[i];
}
};
struct fenwick
{
int n;
hash_table F;
fenwick() { n = inf; }
void upd(int i, int x)
{
for (; i < n; i |= i + 1)
F[i] = max(F[i], x);
}
int get(int i)
{
int res = 0;
for (; i >= 0; i &= i + 1, --i)
res = max(res, F[i]);
return res;
}
};
int n;
pt s, f;
pt p[maxn];
bool read()
{
if (scanf("%d %d %d %d %d", &s.x, &s.y, &f.x, &f.y, &n) != 5)
return false;
forn (i, n)
scanf("%d %d", &p[i].x, &p[i].y);
return true;
}
bool cmp(pt a, pt b) { return make_pair(a.x, a.y) < make_pair(b.x, b.y); }
void solve()
{
if (s.x > f.x)
swap(s, f);
if (s.y > f.y)
{
f.y = 2 * s.y - f.y;
forn (i, n)
p[i].y = 2 * s.y - p[i].y;
}
vector<pt> pp;
forn (i, n)
if (s.x <= p[i].x && p[i].x <= f.x && s.y <= p[i].y && p[i].y <= f.y)
pp.push_back(p[i]);
sort(pp.begin(), pp.end(), cmp);
fenwick dp;
forn (i, size(pp))
dp.upd(pp[i].y, dp.get(pp[i].y) + 1);
int lis = dp.get(inf);
long double ans = 0;
if (lis != min(f.y - s.y, f.x - s.x) + 1)
ans = 100.0 * (f.y - s.y + f.x - s.x) - 20.0 * lis + 5 * M_PI * lis;
else
ans = 100.0 * (f.y - s.y + f.x - s.x) - 20.0 * lis + 5 * M_PI * (lis - 1) + 10 * M_PI;
printf("%.15f\n", (double) ans);
}
int main()
{
#if SEREZHKA
freopen("file.in", "r", stdin);
#endif
while (read())
solve();
return 0;
}
Submission Info
Submission Time
2017-08-28 23:19:52+0900
Task
C - Fountain Walk
User
serezhae
Language
C++14 (GCC 5.4.1)
Score
900
Code Size
2538 Byte
Status
AC
Exec Time
414 ms
Memory
52848 KB
Compile Error
./Main.cpp: In function ‘bool read()’:
./Main.cpp:86:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &p[i].x, &p[i].y);
^
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
7 ms
28928 KB
sample_02.txt
AC
4 ms
14592 KB
sample_03.txt
AC
7 ms
28928 KB
subtask_1_01.txt
AC
6 ms
28928 KB
subtask_1_02.txt
AC
6 ms
28928 KB
subtask_1_03.txt
AC
7 ms
28928 KB
subtask_1_04.txt
AC
7 ms
28928 KB
subtask_1_05.txt
AC
4 ms
14592 KB
subtask_1_06.txt
AC
4 ms
14592 KB
subtask_1_07.txt
AC
4 ms
14592 KB
subtask_1_08.txt
AC
4 ms
14592 KB
subtask_1_09.txt
AC
19 ms
25344 KB
subtask_1_10.txt
AC
36 ms
32128 KB
subtask_1_11.txt
AC
17 ms
49664 KB
subtask_1_12.txt
AC
331 ms
52720 KB
subtask_1_13.txt
AC
38 ms
32128 KB
subtask_1_14.txt
AC
21 ms
29440 KB
subtask_1_15.txt
AC
13 ms
29184 KB
subtask_1_16.txt
AC
173 ms
40432 KB
subtask_1_17.txt
AC
32 ms
32000 KB
subtask_1_18.txt
AC
25 ms
23552 KB
subtask_1_19.txt
AC
27 ms
31744 KB
subtask_1_20.txt
AC
174 ms
32112 KB
subtask_1_21.txt
AC
349 ms
52720 KB
subtask_1_22.txt
AC
165 ms
32240 KB
subtask_1_23.txt
AC
328 ms
52720 KB
subtask_1_24.txt
AC
4 ms
14592 KB
subtask_1_25.txt
AC
3 ms
14592 KB
subtask_1_26.txt
AC
4 ms
14592 KB
subtask_1_27.txt
AC
3 ms
14592 KB
subtask_1_28.txt
AC
47 ms
30592 KB
subtask_1_29.txt
AC
56 ms
51072 KB
subtask_1_30.txt
AC
414 ms
52720 KB
subtask_1_31.txt
AC
188 ms
32112 KB
subtask_1_32.txt
AC
181 ms
32112 KB
subtask_1_33.txt
AC
187 ms
32112 KB
subtask_1_34.txt
AC
186 ms
32240 KB
subtask_1_35.txt
AC
320 ms
52720 KB
subtask_1_36.txt
AC
412 ms
52720 KB
subtask_1_37.txt
AC
327 ms
52720 KB
subtask_1_38.txt
AC
335 ms
52720 KB
subtask_1_39.txt
AC
312 ms
52720 KB
subtask_1_40.txt
AC
315 ms
52720 KB
subtask_1_41.txt
AC
317 ms
52848 KB