Submission #240787

#	Time	Username	Problem	Language	Result	Execution time	Memory
240787		ne4eHbKa	Svjetlost (COI18_svjetlost)	C++17	100 / 100	2406 ms	136632 KiB

Main

//{ <defines>
#include <bits/stdc++.h>
using namespace std;

//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,-O3")

#define fr(i, n) for(int i = 0; i < n; ++i)
#define fo(n) fr(i, n)

#define re return
#define ef else if
#define ifn(x) if(!(x))
#define _  << ' ' <<

#define ft first
#define sd second
#define ve vector
#define pb push_back
#define eb emplace_back

#define sz(x) int((x).size())
#define bnd(x) x.begin(), x.end()
#define clr(x, y) memset((x), (y), sizeof (x))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef ve<int> vi;

inline ll time() {re chrono :: system_clock().now().time_since_epoch().count();}
mt19937 rnd(time());
mt19937_64 RND(time());

template<typename t> inline void umin(t &a, t b) {a = min(a, b);}
template<typename t> inline void umax(t &a, t b) {a = max(a, b);}

int md = 998244353;

inline int m_add(int&a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_sum(int a, int b) {a += b; if(a < 0) a += md; if(a >= md) a -= md; re a;}
inline int m_mul(int&a, int b) {re a = 1ll * a * b % md;}
inline int m_prod(int a, int b) {re 1ll * a * b % md;}

int m_bpow(ll A, ll b) {
    int a = A % md;
    ll ans = 1;
    for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
        (ans *= ans) %= md;
        if(p & b)
            (ans *= a) %= md;
    }
    re ans;
}

const ld pi = arg(complex<ld>(-1, 0));
const ld pi2 = pi + pi;
const int oo = 2e9;
const ll OO = 4e18;
//} </defines>
const int N = 1e5 + 5;

int n, q, m;
int x[N], y[N], v[N], pr[N], nx[N];

const ld eps = 1e-12;

struct cmp {
    bool operator() (const ld &a, const ld &b) const {
        if(abs(a - b) < eps) return false;
        return a < b;
    }
};

map<ld, int, cmp> sh;

ld inv(ld a) {
    a += pi;
    if(a >= pi2) a -= pi2;
    return a;
}

ld angle(int i, int j) {
    ld a = arg(complex<ld> (x[i] - x[j], y[i] - y[j]));
    if(a < 0) a += pi2;
    return a;
}

bool cw(int a, int b, int c) {
    return 1ll * (x[b] - x[a]) * (y[c] - y[a]) <
           1ll * (y[b] - y[a]) * (x[c] - x[a]);
}

struct tree {
    tree *l{0}, *r{0};
    ld v{0}, p{0};
    tree(int tl = 0, int tr = m) {
        if(tl < tr) {
            int tm = tl + tr >> 1;
            l = new tree(tl, tm);
            r = new tree(tm + 1, tr);
        }
    }
    void push() {
        v += p;
        if(l) {
            l->p += p;
            r->p += p;
        }
        p = 0;
    }
    void upd(ld s, int ql, int qr, int tl = 0, int tr = m) {
        if(ql > qr) re push();
        if(ql == tl && qr == tr) {p += s; re push();}
        push();
        int tm = tl + tr >> 1;
        l->upd(s, ql, min(tm, qr), tl, tm);
        r->upd(s, max(tm + 1, ql), qr, tm + 1, tr);
        v = max(l->v, r->v);
    }
    void add(ld v, ld fi) {
        ld se = inv(fi);
        int l = sh[fi] + 1;
        int r = sh[se] - 1;
        if(l > r) {
            upd(v, 0, r);
            upd(v, l, m);
        } else {
            upd(v, l, r);
        }
    }
};

ld sq(ld x) {re x * x;}
ld dist(int i, int j) { return sqrt(sq(x[i] - x[j]) + sq(y[i] - y[j])); }

void solve() {
    cin >> n; for(int i = 0; i < n; ++i) cin >> x[i] >> y[i];
    cin >> q; for(int i = 0; i < q; ++i) cin >> v[i], --v[i];

    if(!cw(0, 1, 2)) {
        reverse(x, x + n);
        reverse(y, y + n);
        for(int i = 0; i < q; ++i) v[i] = n - 1 - v[i];
    }

    for(int i = 0; i < n; ++i) pr[i] = (i + n - 1) % n, nx[i] = (i + 1) % n;

    for(int i = 0; i < n; ++i) {
        ld a = angle(i, nx[i]);
        sh[a], sh[inv(a)];
    }

    for(int i = 0; i < q; ++i) {
        int j = v[i];
        int fi = pr[j];
        int se = nx[j];
        pr[se] = fi;
        nx[fi] = se;
        ld a = angle(fi, se);
        sh[a], sh[inv(a)];
    }

    sh[0], sh[pi2];

    m = 1; for(auto t : sh) sh[t.ft] = (m += 2) - 2;

    for(int i = 0; i < n; ++i) pr[i] = (i + n - 1) % n, nx[i] = (i + 1) % n;

    tree t {};

    for(int i = 0; i < n; ++i) t.add(dist(i, nx[i]), angle(i, nx[i]));

    cout << t.v << '\n';

    for(int i = 0; i < q; ++i) {
        int j = v[i];
        int fi = pr[j];
        int se = nx[j];
        pr[se] = fi;
        nx[fi] = se;
        t.add(-dist(fi,  j), angle(fi,  j));
        t.add(-dist(j,  se), angle(j,  se));
        t.add(+dist(fi, se), angle(fi, se));
        cout << t.v << '\n';
    }
}

int main() {
    cout.precision(10); cout << fixed;
    cerr.precision(6); cerr << fixed;
#ifdef _LOCAL
    freopen("in.txt", "r", stdin);
    int tests; cin >> tests;
    for(int test = 1; test <= tests; ++test) {
		cerr << "case #" << test << endl;
        solve();
        cerr << endl;
    }
#else
//    freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
    ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    solve();
#endif
    return 0;
}

Compilation message (stderr)

svjetlost.cpp: In function 'int m_bpow(ll, ll)':
svjetlost.cpp:50:26: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
     for(ll p = 1ll << 63 - __builtin_clzll(b); p; p >>= 1) {
                       ~~~^~~~~~~~~~~~~~~~~~~~
svjetlost.cpp: In constructor 'tree::tree(int, int)':
svjetlost.cpp:101:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
             int tm = tl + tr >> 1;
                      ~~~^~~~
svjetlost.cpp: In member function 'void tree::upd(ld, int, int, int, int)':
svjetlost.cpp:118:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int tm = tl + tr >> 1;
                  ~~~^~~~

• Subtask 1: 12 / 12
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31