oj.uz

답안 #243163

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243163 2020-06-30T13:02:57 Z VEGAnn Svjetlost (COI18_svjetlost) C++14
40 / 100
 972 ms 51588 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-6;
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]);
    }

    vc.PB(0);
    vc.PB(pi + pi);

    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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 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 18 ms 1536 KB 1201 numbers
7 Correct 19 ms 1536 KB 1556 numbers
8 Correct 22 ms 1536 KB 1996 numbers
9 Correct 21 ms 1536 KB 1960 numbers
10 Correct 21 ms 1536 KB 1991 numbers
11 Correct 21 ms 1536 KB 1963 numbers

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 8 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 57 ms 7664 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 235 ms 29204 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 228 ms 29152 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 16 ms 1408 KB 1001 numbers
2 Correct 189 ms 14900 KB 15001 numbers
3 Correct 473 ms 30216 KB 44445 numbers
4 Correct 397 ms 30528 KB 22223 numbers
5 Incorrect 972 ms 51588 KB 2217th numbers differ - expected: '1800653174.7576336861', found: '1800630958.3355422020', error = '0.0000123380'

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 512 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 18 ms 1536 KB 1201 numbers
7 Correct 19 ms 1536 KB 1556 numbers
8 Correct 22 ms 1536 KB 1996 numbers
9 Correct 21 ms 1536 KB 1960 numbers
10 Correct 21 ms 1536 KB 1991 numbers
11 Correct 21 ms 1536 KB 1963 numbers
12 Correct 5 ms 512 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 8 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 57 ms 7664 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 235 ms 29204 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 228 ms 29152 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 16 ms 1408 KB 1001 numbers
19 Correct 189 ms 14900 KB 15001 numbers
20 Correct 473 ms 30216 KB 44445 numbers
21 Correct 397 ms 30528 KB 22223 numbers
22 Incorrect 972 ms 51588 KB 2217th numbers differ - expected: '1800653174.7576336861', found: '1800630958.3355422020', error = '0.0000123380'