Submission #6365696


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define fi first
#define se second
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define DCIN(...)                                                              \
    double __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    {                                                                          \
        FOREACH(x, v) { cout << x << " "; }                                    \
        cout << "\n";                                                          \
    }
template <typename T = string> inline void eputs(T s) {
    cout << s << "\n";
    exit(0);
}
template <typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val) {
    std::fill((T *)array, (T *)(array + N), val);
}
template <typename T> using PQG = priority_queue<T, vector<T>, greater<T>>;
template <typename T> using PQ = priority_queue<T>;

typedef long long ll;
typedef unsigned long long ul;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;

const int INF = 1e9;
const int MOD = 1e9 + 7;
const double PI = atan(1.0) * 4.0;
// const int MOD = 998244353;
const ll LINF = 9e18;
const ll dx[] = {1, 0, -1, 0};
const ll dy[] = {0, 1, 0, -1};

void cinfast() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

const ll sup = 1e8;

struct LIS {
    vector<int> &v;
    vector<int> dp, id, ret, info;
    // info 1:unused 2:使っても良い 3:必ず使う
    int n, lis;
    LIS(vector<int> &_v) : v(_v) {
        n = v.size();
        dp.resize(n, INT_MAX / 2);
        id.resize(n, 0);
        REP(i, n) {
            // 狭義単調増加列
            // id[i] = lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
            // 広義単調増加列
            id[i] = upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin();
            dp[id[i]] = v[i];
        }
        int nl = *max_element(id.begin(), id.end());
        lis = nl;
        ret.resize(nl + 1, 0);
        REPR(i, n - 1) if(id[i] == nl) ret[nl] = v[i], nl--;

        info.resize(n);
        vector<int> ma(n + 1), cnt(n);
        ma[lis] = INT_MAX / 2;
        REPR(i, n - 1) {
            // 狭義単調増加列
            // if (ma[id[i] + 1] <= v[i]) info[i] = 1;
            // 広義単調増加列
            if(ma[id[i] + 1] < v[i])
                info[i] = 1;

            else
                cnt[id[i]]++, ma[id[i]] = max(ma[id[i]], v[i]);
        }

        REPR(i, n - 1) if(info[i] == 0 && cnt[id[i]] == 1) info[i] = 3;
        REP(i, n) if(info[i] == 0) info[i] = 2;
        lis--;
    }
};

signed main() {
    // cinfast();
    CINT(x1, y1, x2, y2, N);
    vector<int> X(N), Y(N);
    REP(i, N) cin >> X[i] >> Y[i];
    if(x1 > x2) {
        x1 = sup - x1;
        x2 = sup - x2;
        REP(i, N) X[i] = sup - X[i];
    }
    if(y1 > y2) {
        y1 = sup - y1;
        y2 = sup - y2;
        REP(i, N) Y[i] = sup - Y[i];
    }
    vector<pair<int, int>> v;
    REP(i, N)
    if(y1 <= Y[i] && Y[i] <= y2 && x1 <= X[i] && X[i] <= x2)
        v.push_back({X[i], Y[i]});
    sort(v.begin(), v.end());
    vector<int> vv;
    vv.push_back(-1);
    FOREACH(p, v) vv.push_back(p.second);
    vv.push_back(INT_MAX / 2 - 1);
    LIS lis(vv);
    double ans = 100.0 * (x2 - x1 + y2 - y1);
    ans += (5.0 * PI - 20.0) * lis.lis;
    if(lis.lis == min(x2 - x1, y2 - y1) + 1) ans += 5.0 * PI;
    printf("%.15f\n", ans);
}

Submission Info

Submission Time
Task C - Fountain Walk
User arktan763
Language C++14 (GCC 5.4.1)
Score 900
Code Size 4951 Byte
Status AC
Exec Time 181 ms
Memory 18796 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 900 / 900
Status
AC × 3
AC × 47
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 1 ms 256 KB
sample_02.txt AC 1 ms 256 KB
sample_03.txt AC 1 ms 256 KB
subtask_1_01.txt AC 1 ms 256 KB
subtask_1_02.txt AC 1 ms 256 KB
subtask_1_03.txt AC 1 ms 256 KB
subtask_1_04.txt AC 1 ms 256 KB
subtask_1_05.txt AC 1 ms 256 KB
subtask_1_06.txt AC 1 ms 256 KB
subtask_1_07.txt AC 1 ms 256 KB
subtask_1_08.txt AC 1 ms 256 KB
subtask_1_09.txt AC 51 ms 1280 KB
subtask_1_10.txt AC 107 ms 2560 KB
subtask_1_11.txt AC 28 ms 768 KB
subtask_1_12.txt AC 181 ms 18028 KB
subtask_1_13.txt AC 114 ms 2688 KB
subtask_1_14.txt AC 57 ms 1408 KB
subtask_1_15.txt AC 26 ms 768 KB
subtask_1_16.txt AC 180 ms 18796 KB
subtask_1_17.txt AC 94 ms 2304 KB
subtask_1_18.txt AC 74 ms 1792 KB
subtask_1_19.txt AC 72 ms 1920 KB
subtask_1_20.txt AC 168 ms 17900 KB
subtask_1_21.txt AC 180 ms 18540 KB
subtask_1_22.txt AC 180 ms 17900 KB
subtask_1_23.txt AC 180 ms 17900 KB
subtask_1_24.txt AC 1 ms 256 KB
subtask_1_25.txt AC 1 ms 256 KB
subtask_1_26.txt AC 1 ms 256 KB
subtask_1_27.txt AC 1 ms 256 KB
subtask_1_28.txt AC 119 ms 3840 KB
subtask_1_29.txt AC 149 ms 3712 KB
subtask_1_30.txt AC 179 ms 16620 KB
subtask_1_31.txt AC 133 ms 16620 KB
subtask_1_32.txt AC 142 ms 18412 KB
subtask_1_33.txt AC 139 ms 17132 KB
subtask_1_34.txt AC 134 ms 17004 KB
subtask_1_35.txt AC 167 ms 16876 KB
subtask_1_36.txt AC 168 ms 17132 KB
subtask_1_37.txt AC 172 ms 17516 KB
subtask_1_38.txt AC 168 ms 17132 KB
subtask_1_39.txt AC 168 ms 16876 KB
subtask_1_40.txt AC 167 ms 17900 KB
subtask_1_41.txt AC 166 ms 17132 KB