oj.uz

Submission #86947

# Submission time Handle Problem Language Result Execution time Memory
86947 2018-11-28T17:08:18 Z popovicirobert Mobile (BOI12_mobile) C++14
95 / 100
 763 ms 132096 KB 
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
// 217
// 44

using namespace std;

const long double eps = 1e-9;
const long double INF = 1e18;
const int MAXN = (int) 1e6;

struct Point {
    long double x, y;
}pts[MAXN + 1];

inline long double dist(Point a, Point b) {
    return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}

struct Data {
    long double l, r;
    int id;
};

vector <Data> stk;

inline bool eq(long double a, long double b) {
    return fabs(a - b) < eps;
}

long double L;

inline bool ok(long double &l, long double &r, Point b) {
    Point a = pts[stk.back().id];
    if(eq(a.x, b.x)) {
        return 0;
    }
    long double x = 1.0 * (b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y) / (2 * (b.x - a.x));
    if(x > L) {
        return 0;
    }
    x = max(x, (long double) 0.0);
    if(x - stk.back().l > 0) {
        stk.back().r = x;
        l = x;
        r = L;
        return 0;
    }
    l = stk.back().l;
    r = L;
    return 1;
}

int main() {
    //ifstream cin("B.in");
    //ofstream cout("B.out");
    int i, n;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> L;
    int sz = 0;
    for(i = 1; i <= n; i++) {
        long double x, y;
        cin >> x >> y;
        y = fabs(y);
        if(sz > 0 && eq(x, pts[sz].x)) {
            pts[sz].y = min(pts[sz].y, y);
        }
        else {
            pts[++sz] = {x, y};
        }
    }
    n = sz;
    stk.push_back({0, L, 1});
    for(i = 2; i <= n; i++) {
        long double l = INF, r = -INF;
        while(!stk.empty()) {
            if(ok(l, r, pts[i])) {
                stk.pop_back();
            }
            else {
                break;
            }
        }
        if(r - l > 0) {
            stk.push_back({l, r, i});
        }
    }
    long double ans = 0;
    for(auto it : stk) {
        ans = max(ans, dist(pts[it.id], {it.l, 0}));
        ans = max(ans, dist(pts[it.id], {it.r, 0}));
    }
    cout << fixed << setprecision(20) << ans;
    //cin.close();
    //cout.close();
    return 0;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB Output is correct
2 Correct 2 ms 592 KB Output is correct
3 Correct 3 ms 592 KB Output is correct
4 Correct 2 ms 592 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 608 KB Output is correct
2 Correct 4 ms 1024 KB Output is correct
3 Correct 3 ms 1024 KB Output is correct
4 Correct 5 ms 1024 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1024 KB Output is correct
2 Correct 8 ms 1176 KB Output is correct
3 Correct 5 ms 1176 KB Output is correct
4 Correct 6 ms 1176 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1176 KB Output is correct
2 Correct 5 ms 1292 KB Output is correct
3 Correct 5 ms 1292 KB Output is correct
4 Correct 10 ms 1296 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1500 KB Output is correct
2 Correct 5 ms 1524 KB Output is correct
3 Correct 6 ms 1524 KB Output is correct
4 Correct 6 ms 1632 KB Output is correct
5 Correct 4 ms 1632 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 4704 KB Output is correct
2 Correct 52 ms 5108 KB Output is correct
3 Correct 36 ms 5804 KB Output is correct
4 Correct 65 ms 7528 KB Output is correct
5 Correct 27 ms 7528 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 7528 KB Output is correct
2 Correct 43 ms 8228 KB Output is correct
3 Correct 74 ms 10440 KB Output is correct
4 Correct 56 ms 11864 KB Output is correct
5 Correct 66 ms 13592 KB Output is correct

Subtask #9
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 20540 KB Output is correct
2 Correct 57 ms 20540 KB Output is correct
3 Correct 64 ms 20540 KB Output is correct
4 Correct 78 ms 20540 KB Output is correct
5 Correct 53 ms 20540 KB Output is correct

Subtask #10
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 20540 KB Output is correct
2 Correct 68 ms 20732 KB Output is correct
3 Correct 72 ms 21436 KB Output is correct
4 Correct 86 ms 25524 KB Output is correct
5 Correct 65 ms 26212 KB Output is correct

Subtask #11
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 28544 KB Output is correct
2 Correct 69 ms 28544 KB Output is correct
3 Correct 58 ms 28544 KB Output is correct
4 Correct 87 ms 28544 KB Output is correct
5 Correct 63 ms 28544 KB Output is correct

Subtask #12
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 65492 KB Output is correct
2 Correct 338 ms 65492 KB Output is correct
3 Correct 325 ms 65492 KB Output is correct
4 Correct 382 ms 65492 KB Output is correct
5 Correct 318 ms 65492 KB Output is correct

Subtask #13
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 65492 KB Output is correct
2 Correct 391 ms 65492 KB Output is correct
3 Correct 280 ms 65492 KB Output is correct
4 Correct 369 ms 65492 KB Output is correct
5 Correct 339 ms 65492 KB Output is correct

Subtask #14
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 444 ms 93188 KB Output is correct
2 Correct 394 ms 93188 KB Output is correct
3 Correct 381 ms 93188 KB Output is correct
4 Correct 461 ms 93188 KB Output is correct
5 Correct 412 ms 93188 KB Output is correct

Subtask #15
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 406 ms 93188 KB Output is correct
2 Correct 521 ms 93188 KB Output is correct
3 Correct 377 ms 93188 KB Output is correct
4 Correct 452 ms 93188 KB Output is correct
5 Correct 406 ms 93188 KB Output is correct

Subtask #16
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 96468 KB Output is correct
2 Correct 502 ms 96468 KB Output is correct
3 Correct 492 ms 96468 KB Output is correct
4 Correct 552 ms 96468 KB Output is correct
5 Correct 440 ms 96468 KB Output is correct

Subtask #17
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 96468 KB Output is correct
2 Correct 470 ms 96468 KB Output is correct
3 Correct 410 ms 96468 KB Output is correct
4 Correct 560 ms 96468 KB Output is correct
5 Correct 458 ms 96468 KB Output is correct

Subtask #18
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 99488 KB Output is correct
2 Correct 566 ms 99488 KB Output is correct
3 Correct 509 ms 99488 KB Output is correct
4 Correct 635 ms 99488 KB Output is correct
5 Correct 515 ms 99488 KB Output is correct

Subtask #19
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 536 ms 99488 KB Output is correct
2 Correct 535 ms 99488 KB Output is correct
3 Correct 458 ms 99488 KB Output is correct
4 Correct 622 ms 99488 KB Output is correct
5 Correct 529 ms 99488 KB Output is correct

Subtask #20
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 639 ms 117364 KB Output is correct
2 Correct 653 ms 117364 KB Output is correct
3 Correct 648 ms 117364 KB Output is correct
4 Correct 763 ms 117500 KB Output is correct
5 Correct 628 ms 117500 KB Output is correct

Subtask #21
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 687 ms 117500 KB Output is correct
2 Runtime error 685 ms 132096 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
3 Halted 0 ms 0 KB -