Submission #4316019


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(), [&](P a, P b) {
      if(a.first <= b.first && a.second <= b.second) return true;
      return false;
      });

  // 座圧
  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 10641 Byte
Status WA
Exec Time 1622 ms
Memory 211960 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 900
Status
AC × 3
AC × 34
WA × 13
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 87 ms 71040 KB
subtask_1_11.txt WA 70 ms 70272 KB
subtask_1_12.txt WA 706 ms 209768 KB
subtask_1_13.txt AC 89 ms 71168 KB
subtask_1_14.txt WA 72 ms 70528 KB
subtask_1_15.txt WA 70 ms 70272 KB
subtask_1_16.txt WA 707 ms 209768 KB
subtask_1_17.txt AC 83 ms 70912 KB
subtask_1_18.txt AC 82 ms 70784 KB
subtask_1_19.txt AC 84 ms 71552 KB
subtask_1_20.txt AC 712 ms 209768 KB
subtask_1_21.txt AC 711 ms 209768 KB
subtask_1_22.txt WA 705 ms 209768 KB
subtask_1_23.txt WA 718 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 WA 121 ms 76288 KB
subtask_1_29.txt WA 116 ms 75264 KB
subtask_1_30.txt WA 1622 ms 209768 KB
subtask_1_31.txt AC 643 ms 209768 KB
subtask_1_32.txt AC 697 ms 209768 KB
subtask_1_33.txt AC 681 ms 209768 KB
subtask_1_34.txt AC 660 ms 209768 KB
subtask_1_35.txt WA 667 ms 209768 KB
subtask_1_36.txt WA 1112 ms 211960 KB
subtask_1_37.txt AC 684 ms 209768 KB
subtask_1_38.txt AC 676 ms 209768 KB
subtask_1_39.txt AC 676 ms 209768 KB
subtask_1_40.txt AC 658 ms 209768 KB
subtask_1_41.txt AC 664 ms 209768 KB