oj.uz

Submission #243167

# Submission time Handle Problem Language Result Execution time Memory
243167 2020-06-30T13:09:05 Z VEGAnn Svjetlost (COI18_svjetlost) C++14
100 / 100
 1444 ms 52540 KB 
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define PB push_back
using namespace std;
typedef long double ld;
const int N = 400100;
const ld E = 1e-10;
const ld pi = 3.1415926535897;
vector<ld> vc;
int n, pr[N], nt[N], x[N], y[N], nm[N], q;
ld st[4 * N], psh[4 * N];

ld sqr(ld xx) { return xx * xx;}

ld dist(ld x1, ld y1, ld x2, ld y2){
    return sqrt(sqr(x1 - x2) + sqr(y1 - y2));
}

void add(int i, int j){
    ld nw_x = x[j] - x[i];
    ld nw_y = y[j] - y[i];

    ld ang = atan2(nw_y, nw_x);

    if (ang < 0) ang += pi + pi;

    vc.PB(ang);

    ang += pi;

    if (ang >= pi + pi)
        ang -= pi + pi;

    vc.PB(ang);
}

void push(int v){
    if (psh[v] != 0){
        st[v] += psh[v];

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[v + v + 1] += psh[v];
        }

        psh[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, ld val){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r) {
        psh[v] += val;
        push(v);
        return;
    }

    int md = (tl + tr) >> 1;

    update(v + v, tl, md, l, min(r, md), val);
    update(v + v + 1, md + 1, tr, max(md + 1, l), r, val);

    st[v] = max(st[v + v], st[v + v + 1]);
}

void add_seg(int i, int j, ld val){
    ld nw_x = x[j] - x[i];
    ld nw_y = y[j] - y[i];

    ld ang = atan2(nw_y, nw_x);

    if (ang < 0) ang += pi + pi;

    int lf = lower_bound(all(vc), ang - E) - vc.begin();

    ang += pi;

    if (ang >= pi + pi)
        ang -= pi + pi;

    int rt = lower_bound(all(vc), ang - E) - vc.begin() - 1;

    if (vc[rt] + E > ang) {
        rt--;
        if (rt < 0)
            rt = sz(vc) - 1;
    }

    if (rt < 0) rt = sz(vc) - 1;

//    cerr << lf << " " << rt << '\n';

    if (lf <= rt){
        update(1, 0, sz(vc) - 1, lf, rt, val);
    } else {
        update(1, 0, sz(vc) - 1, lf, sz(vc) - 1, val);
        update(1, 0, sz(vc) - 1, 0, rt, val);
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

#ifdef _LOCAL
    freopen("in.txt","r",stdin);
#endif // _LOCAL

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        pr[i] = (i - 1 + n) % n;
        nt[i] = (i + 1) % n;
    }

    for (int i = 0; i < n; i++)
        add(i, nt[i]);

    cin >> q;

    for (int i = 0; i < q; i++){
        cin >> nm[i]; nm[i]--;

        int id = nm[i];

        pr[nt[id]] = pr[id];
        nt[pr[id]] = nt[id];

        add(pr[id], nt[id]);
    }

    sort(all(vc));

    int cnt = 1;

    for (int i = 1; i < sz(vc); i++)
        if (abs(vc[i] - vc[i - 1]) > E)
            vc[cnt++] = vc[i];

    vc.resize(cnt);

    for (int i = 0; i < n; i++){
        pr[i] = (i - 1 + n) % n;
        nt[i] = (i + 1) % n;
        add_seg(i, nt[i], dist(x[i], y[i], x[nt[i]], y[nt[i]]));
    }
    cout << fixed << setprecision(10) << st[1] << '\n';

    for (int i = 0; i < q; i++){
        int id = nm[i];

        add_seg(pr[id], id, -dist(x[pr[id]], y[pr[id]], x[id], y[id]));
        add_seg(id, nt[id], -dist(x[id], y[id], x[nt[id]], y[nt[id]]));

        pr[nt[id]] = pr[id];
        nt[pr[id]] = nt[id];

        add_seg(pr[id], nt[id], dist(x[pr[id]], y[pr[id]], x[nt[id]], y[nt[id]]));

        cout << fixed << setprecision(10) << st[1] << '\n';
    }

    return 0;
}

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 5 ms 384 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 5 ms 384 KB 93 numbers
5 Correct 7 ms 896 KB 101 numbers
6 Correct 15 ms 1408 KB 1201 numbers
7 Correct 20 ms 1536 KB 1556 numbers
8 Correct 24 ms 1536 KB 1996 numbers
9 Correct 21 ms 1536 KB 1960 numbers
10 Correct 21 ms 1536 KB 1991 numbers
11 Correct 22 ms 1536 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 7 ms 896 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 30 ms 4092 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 56 ms 7664 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 230 ms 29152 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 234 ms 29276 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 1500 KB 1001 numbers
2 Correct 172 ms 14800 KB 15001 numbers
3 Correct 479 ms 30176 KB 44445 numbers
4 Correct 459 ms 30372 KB 22223 numbers
5 Correct 932 ms 51820 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 5 ms 384 KB 93 numbers
5 Correct 7 ms 896 KB 101 numbers
6 Correct 15 ms 1408 KB 1201 numbers
7 Correct 20 ms 1536 KB 1556 numbers
8 Correct 24 ms 1536 KB 1996 numbers
9 Correct 21 ms 1536 KB 1960 numbers
10 Correct 21 ms 1536 KB 1991 numbers
11 Correct 22 ms 1536 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 7 ms 896 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 30 ms 4092 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 56 ms 7664 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 230 ms 29152 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 234 ms 29276 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 16 ms 1500 KB 1001 numbers
19 Correct 172 ms 14800 KB 15001 numbers
20 Correct 479 ms 30176 KB 44445 numbers
21 Correct 459 ms 30372 KB 22223 numbers
22 Correct 932 ms 51820 KB 88889 numbers
23 Correct 1444 ms 52508 KB 98175 numbers
24 Correct 378 ms 15672 KB 25905 numbers
25 Correct 1147 ms 52284 KB 98169 numbers
26 Correct 1043 ms 51692 KB 91845 numbers
27 Correct 1141 ms 52540 KB 98296 numbers
28 Correct 1069 ms 51172 KB 85384 numbers
29 Correct 1010 ms 50932 KB 85317 numbers
30 Correct 1114 ms 52312 KB 98246 numbers
31 Correct 582 ms 31772 KB 50001 numbers