oj.uz

Submission #552920

# Submission time Handle Problem Language Result Execution time Memory
552920 2022-04-24T10:11:43 Z hoanghq2004 Lightning Conductor (POI11_pio) C++14
27 / 100
 110 ms 9232 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;

const int N = 5e5 + 10;

int n, h[N];

struct Line {
    int a, b, x;
    int operator()(int x) {
        return ceil(sqrt(abs(a - x))) + b;
    }
    int operator[](int x) {
        return ceil(sqrt(abs(a - x))) + b;
    }
    int operator < (const Line& other) const {
        if (x != other.x) return x < other.x;
        if (a != other.a) return a < other.a;
        return b < other.b;
    }
};

int intersect(Line L1, Line L2) {
    int L = max(L1.a, L2.a), R = n + 1;
    while (R - L > 1) {
        int mid = L + R >> 1;
        if (L1[mid] >= L2[mid]) L = mid;
        else R = mid;
    }
    if (L1[L] < L2[L]) return L;
    else return R;
}

int bad(Line L1, Line L2, Line L3) {
    return intersect(L1, L3) <= intersect(L1, L2);
}

int f[N];

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> h[i];
    vector <Line> convex;
    for (int i = 1, cur = 0; i <= n; ++i) {
        if (i > 1) {
            auto iter = --lower_bound(convex.begin(), convex.end(), (Line){(int)1e9, 0, i});
            f[i] = max(f[i], - h[i] + (*iter)(i));
        }
        //
        if (convex.size() && h[i] <= cur) continue;
        Line L = {i, h[i], 0};
        cur = h[i];
        while (convex.size() >= 2 && bad(convex.end()[-2], convex.back(), L)) convex.pop_back();
        L.x = (convex.empty() ? 1 : intersect(convex.back(), L));
        convex.push_back(L);
    }
    convex.clear();
    reverse(h + 1, h + n + 1);
    for (int i = 1, cur = 0; i <= n; ++i) {
        if (i > 1) {
            auto iter = --lower_bound(convex.begin(), convex.end(), (Line){(int)1e9, 0, i});
            f[n - i + 1] = max(f[n - i + 1], - h[i] + (*iter)(i));
        }
        //
        if (convex.size() && h[i] <= cur) continue;
        Line L = {i, h[i], 0};
        cur = h[i];
        while (convex.size() >= 2 && bad(convex.end()[-2], convex.back(), L)) convex.pop_back();
        L.x = (convex.empty() ? 1 : intersect(convex.back(), L));
        convex.push_back(L);
    }
    for (int i = 1; i <= n; ++i) cout << f[i] << '\n';
}

Compilation message

pio.cpp: In function 'int intersect(Line, Line)':
pio.cpp:35:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         int mid = L + R >> 1;
      |                   ~~^~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 828 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1108 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1108 KB Output is correct
2 Correct 11 ms 1108 KB Output is correct
3 Incorrect 17 ms 1356 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 1552 KB Output is correct
2 Correct 18 ms 1484 KB Output is correct
3 Incorrect 22 ms 2004 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 3120 KB Output is correct
2 Correct 46 ms 2960 KB Output is correct
3 Incorrect 46 ms 3668 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 6456 KB Output is correct
2 Correct 73 ms 4380 KB Output is correct
3 Incorrect 79 ms 6592 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 9140 KB Output is correct
2 Correct 103 ms 6196 KB Output is correct
3 Incorrect 101 ms 9232 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 6732 KB Output is correct
2 Correct 104 ms 6140 KB Output is correct
3 Incorrect 98 ms 9144 KB Output isn't correct
4 Halted 0 ms 0 KB -