Submission #4316121
Source Code Expand
// includes {{{
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <tuple>
#include <vector>
// #include<deque>
// #include<multiset>
// #include<bitset>
// #include<cstring>
// #include<bits/stdc++.h>
// }}}
using namespace std;
using ll = long long;
const int N = 2e5;
int fromX, fromY, toX, toY;
int n;
int x[N], y[N];
// SegmentTree( size [, initial] )
// SegmentTree( <data> )
/// --- SegmentTree {{{ ///
#include <cassert>
#include <initializer_list>
#include <iostream>
#include <iterator>
#include <vector>
template < class Monoid >
struct SegmentTree {
private:
using T = typename Monoid::T;
size_t n;
vector< T > data;
// call after touch data[i]
void prop(int i) { data[i] = Monoid::op(data[2 * i], data[2 * i + 1]); }
public:
SegmentTree() : n(0) {}
SegmentTree(int n, T initial = Monoid::identity()) : n(n) {
data.resize(n * 2, initial);
for(int i = n - 1; i > 0; i--) data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]);
}
template < class InputIter, class = typename iterator_traits< InputIter >::value_type >
SegmentTree(InputIter first, InputIter last) : SegmentTree(distance(first, last)) {
copy(first, last, begin(data) + n);
// fill from deep
for(int i = n - 1; i > 0; i--) prop(i);
}
SegmentTree(vector< T > v) : SegmentTree(v.begin(), v.end()) {}
SegmentTree(initializer_list< T > v) : SegmentTree(v.begin(), v.end()) {}
void set(size_t i, const T &v) {
assert(i < n);
data[i += n] = v;
while(i >>= 1) prop(i); // propUp
}
T get(size_t i) {
assert(i < n);
return data[i + n];
}
T query(int l, int r) {
if(l < 0) l = 0;
if(l >= r) return Monoid::identity();
if(r > (int) n) r = n;
T tmpL = Monoid::identity(), tmpR = Monoid::identity();
for(l += n, r += n; l < r; l >>= 1, r >>= 1) {
if(l & 1) tmpL = Monoid::op(tmpL, data[l++]);
if(r & 1) tmpR = Monoid::op(data[--r], tmpR);
}
return Monoid::op(tmpL, tmpR);
}
inline void dum(int r = -1) {
#ifdef DEBUG
if(r < 0) r = n;
DEBUG_OUT << "{";
for(int i = 0; i < min(r, (int) n); i++) DEBUG_OUT << (i ? ", " : "") << get(i);
DEBUG_OUT << "}" << endl;
#endif
}
};
/// }}}--- ///
/// --- Monoid examples {{{ ///
constexpr long long inf = 1e18 + 100;
#include <algorithm>
struct Nothing {
using T = char;
using Monoid = Nothing;
using M = T;
static constexpr T op(const T &, const T &) { return T(); }
static constexpr T identity() { return T(); }
template < class X >
static constexpr X actInto(const M &, ll, ll, const X &x) {
return x;
}
};
template < class U = long long >
struct RangeMin {
using T = U;
static T op(const T &a, const T &b) { return min(a, b); }
static constexpr T identity() { return T(inf); }
};
template < class U = long long >
struct RangeMax {
using T = U;
static T op(const T &a, const T &b) { return max(a, b); }
static constexpr T identity() { return -T(inf); }
};
template < class U = long long >
struct RangeSum {
using T = U;
static T op(const T &a, const T &b) { return a + b; }
static constexpr T identity() { return T(0); }
};
template < class U >
struct RangeProd {
using T = U;
static T op(const T &a, const T &b) { return a * b; }
static constexpr T identity() { return T(1); }
};
template < class U = long long >
struct RangeOr {
using T = U;
static T op(const T &a, const T &b) { return a | b; }
static constexpr T identity() { return T(0); }
};
#include <bitset>
template < class U = long long >
struct RangeAnd {
using T = U;
static T op(const T &a, const T &b) { return a & b; }
static constexpr T identity() { return T(-1); }
};
template < size_t N >
struct RangeAnd< bitset< N > > {
using T = bitset< N >;
static T op(const T &a, const T &b) { return a & b; }
static constexpr T identity() { return bitset< N >().set(); }
};
/// }}}--- ///
using Seg = SegmentTree< RangeMax<> >;
// constructor(H)
// index(y, x)
// === init(doUnique) ===
// set(y, x, val) // index(y, x) must be done
// query(yl, yr, xl, xr)
// === --- ===
// only offline
/// --- Fractional Cascading SegmentTree {{{ ///
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
template < class T, class U, class Index = ll >
struct FractionalCascadingSegmentTree {
int h;
vector< T > dat;
vector< vector< Index > > indices;
vector< vector< int > > L, R;
U identity;
function< void(T &, int x, const U &) > setX;
function< void(T &, vector< Index > &) > initX;
function< U(T &, int x1, int x2) > queryX;
function< U(const U &, const U &) > mergeY;
FractionalCascadingSegmentTree() {}
FractionalCascadingSegmentTree(int tempH, //
function< void(T &, int, const U &) > const &setX,
function< void(T &, vector< Index > &) > const &initX,
function< U(T &, int, int) > const &queryX,
function< U(const U &, const U &) > const &mergeY,
U identity = U(), T initial = T())
: identity(identity), setX(setX), initX(initX), queryX(queryX), mergeY(mergeY) {
h = 1;
while(h < tempH) h <<= 1;
dat = vector< T >(2 * h, initial);
indices = vector< vector< Index > >(2 * h);
L = R = vector< vector< int > >(2 * h);
}
void index(int i, Index j) {
assert(0 <= i && i < h);
indices[i + h - 1].emplace_back(j);
}
void init(bool doUnique) {
for(int i = h * 2 - 2; i >= 0; i--) {
if(i >= h - 1) {
sort(begin(indices[i]), end(indices[i]));
if(doUnique)
indices[i].erase(unique(begin(indices[i]), end(indices[i])), end(indices[i]));
initX(dat[i], indices[i]);
continue;
}
size_t lsz = indices[i * 2 + 1].size();
size_t rsz = indices[i * 2 + 2].size();
size_t nsz = lsz + rsz;
indices[i].resize(nsz);
L[i].resize(nsz + 1, lsz);
R[i].resize(nsz + 1, rsz);
size_t p1 = 0, p2 = 0;
while(p1 < lsz || p2 < rsz) {
L[i][p1 + p2] = p1;
R[i][p1 + p2] = p2;
if(p1 < lsz && (p2 == rsz || indices[i * 2 + 1][p1] <= indices[i * 2 + 2][p2])) {
indices[i][p1 + p2] = indices[i * 2 + 1][p1];
p1++;
} else {
indices[i][p1 + p2] = indices[i * 2 + 2][p2];
p2++;
}
}
initX(dat[i], indices[i]);
}
}
void set(int y, Index x, const U &val) {
int lower = lower_bound(begin(indices[0]), end(indices[0]), x) - begin(indices[0]);
set(y, lower, val, 0, h, 0);
}
void set(int y, int lower, U const &val, int l, int r, int k) {
if(y + 1 <= l || r <= y) return;
setX(dat[k], lower, val);
if(y <= l && r <= y + 1) return;
set(y, L[k][lower], val, l, (l + r) >> 1, k * 2 + 1);
set(y, R[k][lower], val, (l + r) >> 1, r, k * 2 + 2);
}
U query(int a, int b, Index l, Index r) {
if(a >= b || l >= r) return identity;
int lower = lower_bound(begin(indices[0]), end(indices[0]), l) - begin(indices[0]);
int upper = lower_bound(begin(indices[0]), end(indices[0]), r) - begin(indices[0]);
return query(a, b, lower, upper, 0, h, 0);
}
U query(int a, int b, int lower, int upper, int l, int r, int k) {
if(lower == upper) return identity;
if(b <= l || r <= a) return identity;
if(a <= l && r <= b) return queryX(dat[k], lower, upper);
return mergeY(query(a, b, L[k][lower], L[k][upper], l, (l + r) >> 1, k * 2 + 1),
query(a, b, R[k][lower], R[k][upper], (l + r) >> 1, r, k * 2 + 2));
}
};
/// }}}--- ///
// never forget to init SparseTable by yourself
// FC-SegmentTree Example {{{
using Under = Seg;
using Value = RangeMax<>;
using Data = Value::T;
FractionalCascadingSegmentTree< Under, Data > ecas(
N + 1,
// set x
[](Under &dat, int x, const Data &val) -> void {
// dat.set(x, Value::op(dat.get(x), val));
dat.set(x, val);
},
// init x
[](Under &dat, const vector< ll > &indices) -> void {
dat = Under(indices.size(), 0); // serve initial?
},
// query [l, r) // l < r
[](Under &dat, int l, int r) -> Data { return dat.query(l, r); },
// merge y-direction
[](Data a, Data b) -> Data { return max(a, b); }
// optional
, 0
);
// }}}
// uniq, compress {{{
#include <algorithm>
#include <map>
#include <vector>
template < class T >
void uniq(vector< T > &v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
template < class T >
map< T, int > compress(const vector< T > &v) {
map< T, int > mp;
int i = -1;
for(auto &e : v) mp[e] = ++i;
return mp;
}
// }}}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> fromX >> fromY >> toX >> toY;
cin >> n;
bool revX = 0, revY = 0;
if(fromX > toX) fromX *= -1, toX *= -1, revX = 1;
if(fromY > toY) fromY *= -1, toY *= -1, revY = 1;
using P = pair<int, int>;
vector<P> v;
vector<int> xs;
toX -= fromX, toY -= fromY;
for(int i = 0; i < n; i++) {
cin >> x[i] >> y[i];
if(revX) x[i] *= -1;
if(revY) y[i] *= -1;
x[i] -= fromX;
y[i] -= fromY;
if(0 <= x[i] && x[i] <= toX && 0 <= y[i] && y[i] <= toY) {
xs.emplace_back(x[i]);
v.emplace_back(x[i], y[i]);
}
}
fromX = fromY = 0;
sort((v).begin(), (v).end());
// 座圧
xs.emplace_back(toX);
uniq(xs);
auto mp = compress(xs);
for(auto p : v) ecas.index(mp[p.first], p.second);
ecas.init(1);
for(auto p : v) {
int val = ecas.query(0, mp[p.first], 0, p.second) + 1;
ecas.set(mp[p.first], p.second, val);
}
cout << fixed << setprecision(20);
constexpr double PI = acos(-1);
constexpr double A = 20 - 5 * PI;
constexpr double B = 10 * PI - 20;
int num = ecas.query(0, mp[toX] + 1, 0, toY + 1);
double ans = 0;
if(toX != 0 && toY != 0) {
ans += (double) - num * A;
ans += 100.0 * (toX + toY);
} else {
ans += (double) B * num;
ans += (toX + toY) * 100.0;
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Fountain Walk |
User |
luma |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
10527 Byte |
Status |
WA |
Exec Time |
977 ms |
Memory |
209768 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 |
59 ms |
69888 KB |
sample_02.txt |
AC |
59 ms |
69888 KB |
sample_03.txt |
AC |
59 ms |
69888 KB |
subtask_1_01.txt |
AC |
59 ms |
69888 KB |
subtask_1_02.txt |
AC |
59 ms |
69888 KB |
subtask_1_03.txt |
AC |
59 ms |
69888 KB |
subtask_1_04.txt |
AC |
59 ms |
69888 KB |
subtask_1_05.txt |
AC |
59 ms |
69888 KB |
subtask_1_06.txt |
AC |
59 ms |
69888 KB |
subtask_1_07.txt |
AC |
59 ms |
69888 KB |
subtask_1_08.txt |
AC |
59 ms |
69888 KB |
subtask_1_09.txt |
AC |
72 ms |
70528 KB |
subtask_1_10.txt |
WA |
86 ms |
71040 KB |
subtask_1_11.txt |
WA |
69 ms |
70272 KB |
subtask_1_12.txt |
WA |
701 ms |
209768 KB |
subtask_1_13.txt |
AC |
88 ms |
71168 KB |
subtask_1_14.txt |
WA |
72 ms |
70528 KB |
subtask_1_15.txt |
WA |
69 ms |
70272 KB |
subtask_1_16.txt |
WA |
701 ms |
209768 KB |
subtask_1_17.txt |
AC |
83 ms |
70912 KB |
subtask_1_18.txt |
AC |
81 ms |
70784 KB |
subtask_1_19.txt |
AC |
84 ms |
71552 KB |
subtask_1_20.txt |
AC |
709 ms |
209768 KB |
subtask_1_21.txt |
AC |
709 ms |
209768 KB |
subtask_1_22.txt |
AC |
700 ms |
209768 KB |
subtask_1_23.txt |
AC |
710 ms |
209768 KB |
subtask_1_24.txt |
AC |
59 ms |
69888 KB |
subtask_1_25.txt |
AC |
59 ms |
69888 KB |
subtask_1_26.txt |
AC |
59 ms |
69888 KB |
subtask_1_27.txt |
AC |
59 ms |
69888 KB |
subtask_1_28.txt |
AC |
116 ms |
76288 KB |
subtask_1_29.txt |
AC |
114 ms |
75264 KB |
subtask_1_30.txt |
AC |
977 ms |
209768 KB |
subtask_1_31.txt |
AC |
662 ms |
209768 KB |
subtask_1_32.txt |
AC |
690 ms |
209768 KB |
subtask_1_33.txt |
AC |
681 ms |
209768 KB |
subtask_1_34.txt |
AC |
700 ms |
209768 KB |
subtask_1_35.txt |
AC |
674 ms |
209768 KB |
subtask_1_36.txt |
AC |
959 ms |
209768 KB |
subtask_1_37.txt |
AC |
676 ms |
209768 KB |
subtask_1_38.txt |
AC |
672 ms |
209768 KB |
subtask_1_39.txt |
AC |
677 ms |
209768 KB |
subtask_1_40.txt |
AC |
675 ms |
209768 KB |
subtask_1_41.txt |
AC |
671 ms |
209768 KB |