oj.uz

Submission #240787

# Submission time Handle Problem Language Result Execution time Memory
240787 2020-06-21T07:47:30 Z ne4eHbKa Svjetlost (COI18_svjetlost) C++17
100 / 100
 2406 ms 136632 KB 
//{ <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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 6 ms 512 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 6 ms 512 KB 93 numbers
5 Correct 9 ms 1152 KB 101 numbers
6 Correct 18 ms 2176 KB 1201 numbers
7 Correct 21 ms 2560 KB 1556 numbers
8 Correct 26 ms 3200 KB 1996 numbers
9 Correct 25 ms 3072 KB 1960 numbers
10 Correct 25 ms 3200 KB 1991 numbers
11 Correct 25 ms 3072 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 9 ms 1408 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 43 ms 8316 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 87 ms 14840 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 352 ms 59512 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 355 ms 59640 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 2816 KB 1001 numbers
2 Correct 233 ms 27640 KB 15001 numbers
3 Correct 661 ms 66168 KB 44445 numbers
4 Correct 596 ms 72476 KB 22223 numbers
5 Correct 1323 ms 127096 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 5 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 6 ms 512 KB 93 numbers
5 Correct 9 ms 1152 KB 101 numbers
6 Correct 18 ms 2176 KB 1201 numbers
7 Correct 21 ms 2560 KB 1556 numbers
8 Correct 26 ms 3200 KB 1996 numbers
9 Correct 25 ms 3072 KB 1960 numbers
10 Correct 25 ms 3200 KB 1991 numbers
11 Correct 25 ms 3072 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 9 ms 1408 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 43 ms 8316 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 87 ms 14840 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 352 ms 59512 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 355 ms 59640 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 22 ms 2816 KB 1001 numbers
19 Correct 233 ms 27640 KB 15001 numbers
20 Correct 661 ms 66168 KB 44445 numbers
21 Correct 596 ms 72476 KB 22223 numbers
22 Correct 1323 ms 127096 KB 88889 numbers
23 Correct 2406 ms 136384 KB 98175 numbers
24 Correct 526 ms 36088 KB 25905 numbers
25 Correct 1627 ms 136316 KB 98169 numbers
26 Correct 1508 ms 127608 KB 91845 numbers
27 Correct 1674 ms 136632 KB 98296 numbers
28 Correct 1772 ms 118608 KB 85384 numbers
29 Correct 1376 ms 118524 KB 85317 numbers
30 Correct 1549 ms 136380 KB 98246 numbers
31 Correct 866 ms 90616 KB 50001 numbers