oj.uz

Submission #243151

# Submission time Handle Problem Language Result Execution time Memory
243151 2020-06-30T12:42:00 Z VEGAnn Svjetlost (COI18_svjetlost) C++14
69 / 100
 1526 ms 52564 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-9;
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);
    ld ang = arg(complex<long double>(nw_x, nw_y));

    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);
    ld ang = arg(complex<long double>(nw_x, nw_y));

    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 (rt < 0) rt = sz(vc) - 1;

    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 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 5 ms 512 KB 93 numbers
5 Correct 7 ms 896 KB 101 numbers
6 Correct 15 ms 1408 KB 1201 numbers
7 Correct 19 ms 1536 KB 1556 numbers
8 Correct 22 ms 1536 KB 1996 numbers
9 Correct 22 ms 1536 KB 1960 numbers
10 Correct 23 ms 1536 KB 1991 numbers
11 Correct 23 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 9 ms 896 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 31 ms 4220 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 244 ms 29068 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 227 ms 29156 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 1408 KB 1001 numbers
2 Correct 174 ms 14916 KB 15001 numbers
3 Correct 472 ms 30048 KB 44445 numbers
4 Correct 391 ms 30432 KB 22223 numbers
5 Correct 949 ms 51668 KB 88889 numbers

Subtask #5
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 512 KB 93 numbers
5 Correct 7 ms 896 KB 101 numbers
6 Correct 15 ms 1408 KB 1201 numbers
7 Correct 19 ms 1536 KB 1556 numbers
8 Correct 22 ms 1536 KB 1996 numbers
9 Correct 22 ms 1536 KB 1960 numbers
10 Correct 23 ms 1536 KB 1991 numbers
11 Correct 23 ms 1536 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 9 ms 896 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 31 ms 4220 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 244 ms 29068 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 227 ms 29156 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 16 ms 1408 KB 1001 numbers
19 Correct 174 ms 14916 KB 15001 numbers
20 Correct 472 ms 30048 KB 44445 numbers
21 Correct 391 ms 30432 KB 22223 numbers
22 Correct 949 ms 51668 KB 88889 numbers
23 Correct 1526 ms 52564 KB 98175 numbers
24 Correct 342 ms 15528 KB 25905 numbers
25 Correct 1161 ms 52436 KB 98169 numbers
26 Incorrect 1064 ms 51788 KB 40842nd numbers differ - expected: '3728194663.4741077423', found: '3728119835.3530573845', error = '0.0000200709'
27 Halted 0 ms 0 KB -