Contest Duration: ~ (local time) (150 minutes) Back to Home

Submission #1546153

Source Code Expand

Copy
```#include<bits/stdc++.h>

using namespace std;

#define double long double
template< typename T >
struct SegmentTree
{
const T INF;

vector< T > seg;
int sz;

SegmentTree(int n) : INF(-1e30)
{
sz = 1;
while(sz < n) sz <<= 1;
seg.assign(2 * sz - 1, -1e30);
}

T merge(T a, T b)
{
return (max(a, b));
}

void set(int k, int x)
{
seg[k + sz - 1] = x;
}

void build()
{
for(int k = sz - 2; k >= 0; k--) {
seg[k] = merge(seg[2 * k + 1], seg[2 * k + 2]);
}
}

T rmq(int a, int b, int k, int l, int r)
{
if(a >= r || b <= l) return (INF);
if(a <= l && r <= b) return (seg[k]);
return (merge(rmq(a, b, 2 * k + 1, l, (l + r) >> 1),
rmq(a, b, 2 * k + 2, (l + r) >> 1, r)));
}

T rmq(int a, int b)
{
return (rmq(a, b, 0, 0, sz));
}

void update(int k, T x)
{
k += sz - 1;
seg[k] = x;
while(k > 0) {
k = (k - 1) >> 1;
seg[k] = merge(seg[2 * k + 1], seg[2 * k + 2]);
}
}
};

typedef pair< int, int > Pi;

int main()
{
double cost = 20 * acos(-1) / 4.0;

int a, b, c, d, N;
int X[200000], Y[200000];

cin >> a >> b >> c >> d;
cin >> N;
for(int i = 0; i < N; i++) cin >> X[i] >> Y[i];

vector< Pi > xx;
vector< int > yy;

auto p = minmax(a, c), q = minmax(b, d);

bool flip = false;
//if(a > c && b < d) flip = true;
if(a < c && b > d) flip = true;

for(int i = 0; i < N; i++) {
if(p.first <= X[i] && X[i] <= p.second) {
if(q.first <= Y[i] && Y[i] <= q.second) {
xx.emplace_back(X[i], i);
if(flip) Y[i] *= -1;
yy.push_back(Y[i]);
yy.push_back(Y[i] + 1);
}
}
}
yy.push_back(q.second);
sort(begin(xx), end(xx));
sort(begin(yy), end(yy));
yy.erase(unique(begin(yy), end(yy)), end(yy));

SegmentTree< double > seg(yy.size());
seg.update(0, 0.0);

for(int i = 0; i < xx.size(); i++) {
int idx = xx[i].second;
Y[idx] = lower_bound(begin(yy), end(yy), Y[idx]) - begin(yy);
auto ss = seg.rmq(Y[idx], Y[idx] + 1);
double st = ss - (cost * 2 - 20.0);
seg.update(Y[idx] + 1, max(seg.rmq(Y[idx] + 1, Y[idx] + 2), seg.rmq(0, Y[idx] + 1) + 20.0 - cost));
seg.update(Y[idx], max(st, seg.rmq(0, Y[idx]) + 20.0 - cost));
}

double rest = 0.0;
rest += (p.second - p.first) * 100.0;
rest += (q.second - q.first) * 100.0;

if(flip) {
auto ps = lower_bound(begin(yy), end(yy), -q.first) - begin(yy);
cout << fixed << setprecision(15) << rest - seg.rmq(0, ps + 1) << endl;
} else {
auto ps = lower_bound(begin(yy), end(yy), q.second) - begin(yy);
cout << fixed << setprecision(15) << rest - seg.rmq(0, ps + 1) << endl;
}
}```

#### Submission Info

Submission Time 2017-08-27 00:06:49+0900 C - Fountain Walk ei13333 C++14 (GCC 5.4.1) 0 2822 Byte WA 440 ms 21476 KB

#### Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB