oj.uz

Submission #850978

# Submission time Handle Problem Language Result Execution time Memory
850978 2023-09-18T04:39:08 Z Cyanmond Svjetlost (COI18_svjetlost) C++17
100 / 100
 1130 ms 27936 KB 
#include <bits/stdc++.h>

using namespace std;

#define rep(i, l, r) for (int i = (l); i < (r); ++i)
#define per(i, l, r) for (int i = (r - 1); i >= l; --i)
#define ALL(x) (x).begin(), (x).end()

using i64 = long long;

struct LazySegTree {
    int n, siz, lg;
    vector<long double> data, lazy;

    void update(int i) {
        data[i] = max(data[2 * i], data[2 * i + 1]);
    }

    void fall(int i, long double v) {
        data[i] += v;
        if (i < siz) lazy[i] += v;
    }

    void push(int i) {
        fall(2 * i, lazy[i]);
        fall(2 * i + 1, lazy[i]);
        lazy[i] = 0;
    }

    LazySegTree(int n_) : n(n_) {
        lg = 0;
        while ((1 << lg) < n) ++lg;
        siz = 1 << lg;
        data.assign(2 * siz, 0);
        lazy.assign(siz, 0);
    }

    void apply(int l, int r, long double v) {
        l += siz, r += siz;

        for (int i = lg; i >= 1; --i) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        int l2 = l, r2 = r;
        while (l < r) {
            if (l & 1) fall(l++, v);
            if (r & 1) fall(--r, v);
            l /= 2;
            r /= 2;
        }
        l = l2, r = r2;

        for (int i = 1; i <= lg; ++i) {
            if (((l >> i) << i) != l) update(l >> i);
            if (((r >> i) << i) != r) update((r - 1) >> i);
        }
    }

    long double fold(int l, int r) {
        l += siz, r += siz;

        for (int i = lg; i >= 1; --i) {
            if (((l >> i) << i) != l) push(l >> i);
            if (((r >> i) << i) != r) push((r - 1) >> i);
        }

        long double ret = 0;
        while (l < r) {
            if (l & 1) ret = max(ret, data[l++]);
            if (r & 1) ret = max(ret, data[--r]);
            l /= 2;
            r /= 2;
        }

        return ret;
    }
};

void main_() {
    int N;
    cin >> N;
    vector<pair<i64, i64>> P(N);
    for (auto &[a, b] : P) {
        cin >> a >> b;
    }

    auto calcRegion = [](const pair<i64, i64> &p) {
        assert(p.first != 0 or p.second != 0);
        if (p.first > 0 and p.second >= 0) return 1;
        else if (p.first <= 0 and p.second > 0) return 2;
        else if (p.first < 0 and p.second <= 0) return 3;
        else return 4;
    };

    auto rotate = [](pair<i64, i64> &p) {
        pair<i64, i64> q = {p.second, -p.first};
        p = q;
    };
    
    auto comp = [&](pair<i64, i64> a, pair<i64, i64> b) {
        int rga = calcRegion(a), rgb = calcRegion(b);
        if (rga != rgb) return rga < rgb;
        while (not(a.first > 0 and a.second >= 0)) {
            rotate(a);
            rotate(b);
        }
        return a.second * b.first < a.first * b.second;
    };

    set<int> s;
    rep(i, 0, N) s.insert(i);
    vector<pair<i64, i64>> lines;
    rep(i, 0, N) lines.push_back({P[i].first - P[(i + N - 1) % N].first, P[i].second - P[(i + N - 1) % N].second});

    int Q;
    cin >> Q;
    vector<int> S(Q);
    for (auto &e : S) {
        cin >> e;
        --e;
        s.erase(s.find(e));
        auto itr1 = s.lower_bound(e);
        auto itrR = itr1;
        if (itrR == s.end()) itrR = s.begin();
        auto itrL = itr1;
        if (itrL == s.begin()) itrL = --s.end();
        else --itrL;

        const auto a = *itrL, b = *itrR;
        lines.push_back({P[b].first - P[a].first, P[b].second - P[a].second});
    }

    sort(ALL(lines), comp);
    const int M = (int)lines.size();
    LazySegTree seg(M);

    auto dist = [&](const pair<i64, i64> &p) {
        return sqrtl(p.first * p.first + p.second * p.second);
    };

    auto add = [&](int i, long double v) {
        auto line = lines[i];
        line.first *= -1;
        line.second *= -1;
        const int p = (int)(upper_bound(ALL(lines), line, comp) - lines.begin());
        if (p < i) {
            seg.apply(p, i + 1, v);
        } else {
            seg.apply(p, M, v);
            seg.apply(0, i + 1, v);
        }
    };

    auto calcAns = [&]() {
        return seg.fold(0, M);
    };

    rep(i, 0, N) {
        auto line = make_pair(P[i].first - P[(i + N - 1) % N].first, P[i].second - P[(i + N - 1) % N].second);
        const int p = (int)(lower_bound(ALL(lines), line, comp) - lines.begin());
        add(p, dist(line));
    }

    cout << fixed << setprecision(10);
    cout << calcAns() << endl;

    rep(i, 0, N) s.insert(i);
    rep(i, 0, Q) {
        auto itr = s.erase(s.find(S[i]));
        auto itrL = itr;
        if (itrL == s.begin()) itrL = --s.end();
        else --itrL;
        auto itrR = itr;
        if (itrR == s.end()) itrR = s.begin();

        pair<int, int> line1 = {P[S[i]].first - P[*itrL].first, P[S[i]].second - P[*itrL].second};
        const int p1 = (int)(lower_bound(ALL(lines), line1, comp) - lines.begin());
        pair<int, int> line2 = {P[*itrR].first - P[S[i]].first, P[*itrR].second - P[S[i]].second};
        const int p2 = (int)(lower_bound(ALL(lines), line2, comp) - lines.begin());
        pair<int, int> line3 = {P[*itrR].first - P[*itrL].first, P[*itrR].second - P[*itrL].second};
        const int p3 = (int)(lower_bound(ALL(lines), line3, comp) - lines.begin());

        add(p1, -dist(line1));
        add(p2, -dist(line2));
        add(p3, dist(line3));

        cout << calcAns() << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    main_();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB 11 numbers
2 Correct 1 ms 348 KB 41 numbers
3 Correct 1 ms 348 KB 11 numbers
4 Correct 1 ms 456 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB 11 numbers
2 Correct 1 ms 348 KB 41 numbers
3 Correct 1 ms 348 KB 11 numbers
4 Correct 1 ms 456 KB 93 numbers
5 Correct 2 ms 604 KB 101 numbers
6 Correct 9 ms 860 KB 1201 numbers
7 Correct 13 ms 856 KB 1556 numbers
8 Correct 15 ms 1112 KB 1996 numbers
9 Correct 14 ms 860 KB 1960 numbers
10 Correct 14 ms 804 KB 1991 numbers
11 Correct 14 ms 860 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 604 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 18 ms 2428 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 36 ms 4204 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 147 ms 15252 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 159 ms 15352 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 856 KB 1001 numbers
2 Correct 150 ms 6684 KB 15001 numbers
3 Correct 394 ms 13784 KB 44445 numbers
4 Correct 315 ms 15840 KB 22223 numbers
5 Correct 820 ms 27644 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB 11 numbers
2 Correct 1 ms 348 KB 41 numbers
3 Correct 1 ms 348 KB 11 numbers
4 Correct 1 ms 456 KB 93 numbers
5 Correct 2 ms 604 KB 101 numbers
6 Correct 9 ms 860 KB 1201 numbers
7 Correct 13 ms 856 KB 1556 numbers
8 Correct 15 ms 1112 KB 1996 numbers
9 Correct 14 ms 860 KB 1960 numbers
10 Correct 14 ms 804 KB 1991 numbers
11 Correct 14 ms 860 KB 1963 numbers
12 Correct 1 ms 348 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 2 ms 604 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 18 ms 2428 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 36 ms 4204 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 147 ms 15252 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 159 ms 15352 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 9 ms 856 KB 1001 numbers
19 Correct 150 ms 6684 KB 15001 numbers
20 Correct 394 ms 13784 KB 44445 numbers
21 Correct 315 ms 15840 KB 22223 numbers
22 Correct 820 ms 27644 KB 88889 numbers
23 Correct 1130 ms 27936 KB 98175 numbers
24 Correct 254 ms 7184 KB 25905 numbers
25 Correct 937 ms 27320 KB 98169 numbers
26 Correct 867 ms 26436 KB 91845 numbers
27 Correct 947 ms 27200 KB 98296 numbers
28 Correct 834 ms 26484 KB 85384 numbers
29 Correct 822 ms 25164 KB 85317 numbers
30 Correct 923 ms 27900 KB 98246 numbers
31 Correct 508 ms 17028 KB 50001 numbers