Submission #5307011


Source Code Expand

#include <stdio.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <algorithm>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath>
#include <iomanip>
//#include <unordered_map>
//#include <unordered_set>
//#include <boost/container/static_vector.hpp>
//#include <boost/unordered_set.hpp>
//#include <boost/unordered_map.hpp>
//#include <unistd.h>

//#include <cv.h>
//#include <highgui.h>
#include <stdlib.h>
#include <string>

const int MAX_N = 200050;
const int MAX_L = 100000000;

int N;
int X[MAX_N], Y[MAX_N];

int seq[MAX_N], dp_lis[MAX_N];

int main(int argc, char **argv) {
    int x1, y1, x2, y2;
    std::cin >> x1 >> y1 >> x2 >> y2;
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        std::cin >> X[i] >> Y[i];
    }

    if (x2 < x1) {
        for (int i = 1; i <= N; i++) {
            X[i] = MAX_L - 1 - X[i];
        }
        x1 = MAX_L - 1 - x1;
        x2 = MAX_L - 1 - x2;
    }

    if (y2 < y1) {
        for (int i = 1; i <= N; i++) {
            Y[i] = MAX_L - 1 - Y[i];
        }
        y1 = MAX_L - 1 - y1;
        y2 = MAX_L - 1 - y2;
    }

    std::vector<std::pair<int, int>> vec;

    for (int i = 1; i <= N; i++) {
        if (x1 <= X[i] && X[i] <= x2 && y1 <= Y[i] && Y[i] <= y2) {
            vec.push_back(std::pair<int, int>({X[i], Y[i]}));
        }
    }

    std::sort(vec.begin(), vec.end(),
        [](const std::pair<int, int>& a, const std::pair<int, int> b) { return a.first < b.first; }
    );

    int seq_size = vec.size();

    for (int i = 1; i <= seq_size; i++) {
        seq[i] = vec[i-1].second;
    }

    for (int i = 1; i <= seq_size; i++) {
        dp_lis[i] = MAX_L;
    }
    dp_lis[0] = 0;

    for (int i = 1; i <= seq_size; i++) {
        int lb = 0;
        int ub = seq_size;
        while(lb + 1 < ub) {
            int mid = (lb + ub) / 2;
            if (dp_lis[mid] < seq[i]) {
                lb = mid;
            } else {
                ub = mid;
            }
        }
        dp_lis[ub] = std::min(dp_lis[ub], seq[i]);
    }

    int length = 0;
    for (int i = 1; i <= seq_size; i++) {
        if (dp_lis[i] < MAX_L) {
            length++;
        } else {
            break;
        }
    }

    double PI = acos(-1.0);

    double ret = (x2 - x1 + y2 - y1) * 100.0;

    if (length == std::min(x2 - x1 + 1, y2 - y1 + 1)) {
        ret += (length - 1) * (5.0 * PI - 20.0);
        ret += 10.0 * PI - 20.0;
    } else {
        ret += length * (5.0 * PI - 20.0);
    }

    std::cout << std::setprecision(14) << ret << std::endl;

    return 0;
}

Submission Info

Submission Time
Task C - Fountain Walk
User critter
Language C++14 (GCC 5.4.1)
Score 900
Code Size 2704 Byte
Status AC
Exec Time 197 ms
Memory 5104 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 52 ms 768 KB
subtask_1_10.txt AC 107 ms 1408 KB
subtask_1_11.txt AC 28 ms 512 KB
subtask_1_12.txt AC 176 ms 5104 KB
subtask_1_13.txt AC 114 ms 1536 KB
subtask_1_14.txt AC 53 ms 768 KB
subtask_1_15.txt AC 26 ms 512 KB
subtask_1_16.txt AC 197 ms 5104 KB
subtask_1_17.txt AC 94 ms 1280 KB
subtask_1_18.txt AC 74 ms 1024 KB
subtask_1_19.txt AC 72 ms 1024 KB
subtask_1_20.txt AC 164 ms 5104 KB
subtask_1_21.txt AC 178 ms 5104 KB
subtask_1_22.txt AC 178 ms 5104 KB
subtask_1_23.txt AC 176 ms 5104 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 2048 KB
subtask_1_29.txt AC 146 ms 1920 KB
subtask_1_30.txt AC 185 ms 5104 KB
subtask_1_31.txt AC 133 ms 5104 KB
subtask_1_32.txt AC 136 ms 5104 KB
subtask_1_33.txt AC 135 ms 5104 KB
subtask_1_34.txt AC 131 ms 5104 KB
subtask_1_35.txt AC 165 ms 5104 KB
subtask_1_36.txt AC 166 ms 5104 KB
subtask_1_37.txt AC 165 ms 5104 KB
subtask_1_38.txt AC 165 ms 5104 KB
subtask_1_39.txt AC 165 ms 5104 KB
subtask_1_40.txt AC 163 ms 5104 KB
subtask_1_41.txt AC 163 ms 5104 KB