Submission #850978

#	Time	Username	Problem	Language	Result	Execution time	Memory
850978		Cyanmond	Svjetlost (COI18_svjetlost)	C++17	100 / 100	1130 ms	27936 KiB

Main

#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 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31