Submission #1546099


Source Code Expand

Copy
#include<bits/stdc++.h>
 
using namespace std;
 
#define int long long
#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;
 
signed 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.second) - 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
Task C - Fountain Walk
User ei13333
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2847 Byte
Status
Exec Time 455 ms
Memory 28124 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
All 0 / 900 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 2 ms 2304 KB
sample_02.txt 2 ms 2304 KB
sample_03.txt 1 ms 256 KB
subtask_1_01.txt 2 ms 2304 KB
subtask_1_02.txt 2 ms 2304 KB
subtask_1_03.txt 1 ms 256 KB
subtask_1_04.txt 1 ms 256 KB
subtask_1_05.txt 2 ms 2304 KB
subtask_1_06.txt 2 ms 2304 KB
subtask_1_07.txt 2 ms 2304 KB
subtask_1_08.txt 2 ms 2304 KB
subtask_1_09.txt 51 ms 2816 KB
subtask_1_10.txt 106 ms 2560 KB
subtask_1_11.txt 28 ms 896 KB
subtask_1_12.txt 361 ms 26204 KB
subtask_1_13.txt 113 ms 2688 KB
subtask_1_14.txt 53 ms 2560 KB
subtask_1_15.txt 26 ms 768 KB
subtask_1_16.txt 346 ms 19036 KB
subtask_1_17.txt 95 ms 2304 KB
subtask_1_18.txt 73 ms 1792 KB
subtask_1_19.txt 72 ms 1920 KB
subtask_1_20.txt 330 ms 18012 KB
subtask_1_21.txt 361 ms 26204 KB
subtask_1_22.txt 348 ms 18012 KB
subtask_1_23.txt 368 ms 26460 KB
subtask_1_24.txt 2 ms 2304 KB
subtask_1_25.txt 1 ms 256 KB
subtask_1_26.txt 2 ms 2304 KB
subtask_1_27.txt 2 ms 2304 KB
subtask_1_28.txt 124 ms 4224 KB
subtask_1_29.txt 151 ms 4224 KB
subtask_1_30.txt 455 ms 26204 KB
subtask_1_31.txt 280 ms 18780 KB
subtask_1_32.txt 281 ms 18012 KB
subtask_1_33.txt 282 ms 18012 KB
subtask_1_34.txt 288 ms 18140 KB
subtask_1_35.txt 333 ms 26204 KB
subtask_1_36.txt 421 ms 26588 KB
subtask_1_37.txt 349 ms 28124 KB
subtask_1_38.txt 340 ms 26204 KB
subtask_1_39.txt 342 ms 26204 KB
subtask_1_40.txt 352 ms 27868 KB
subtask_1_41.txt 322 ms 26204 KB