oj.uz

답안 #243159

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
243159 2020-06-30T12:59:05 Z VEGAnn Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 55052 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);

    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 384 KB 11 numbers
2 Correct 6 ms 384 KB 41 numbers
3 Correct 6 ms 384 KB 11 numbers
4 Correct 8 ms 512 KB 93 numbers

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 6 ms 384 KB 41 numbers
3 Correct 6 ms 384 KB 11 numbers
4 Correct 8 ms 512 KB 93 numbers
5 Correct 17 ms 896 KB 101 numbers
6 Correct 56 ms 1528 KB 1201 numbers
7 Correct 68 ms 1536 KB 1556 numbers
8 Correct 86 ms 1656 KB 1996 numbers
9 Correct 90 ms 1656 KB 1960 numbers
10 Correct 92 ms 1656 KB 1991 numbers
11 Correct 86 ms 1536 KB 1963 numbers

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 512 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 18 ms 896 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 124 ms 4380 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 221 ms 7872 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 865 ms 30432 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 888 ms 30324 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 1528 KB 1001 numbers
2 Correct 748 ms 15720 KB 15001 numbers
3 Correct 1950 ms 32608 KB 44445 numbers
4 Correct 1599 ms 32504 KB 22223 numbers
5 Execution timed out 3063 ms 55052 KB Time limit exceeded

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 6 ms 384 KB 41 numbers
3 Correct 6 ms 384 KB 11 numbers
4 Correct 8 ms 512 KB 93 numbers
5 Correct 17 ms 896 KB 101 numbers
6 Correct 56 ms 1528 KB 1201 numbers
7 Correct 68 ms 1536 KB 1556 numbers
8 Correct 86 ms 1656 KB 1996 numbers
9 Correct 90 ms 1656 KB 1960 numbers
10 Correct 92 ms 1656 KB 1991 numbers
11 Correct 86 ms 1536 KB 1963 numbers
12 Correct 6 ms 512 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 18 ms 896 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 124 ms 4380 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 221 ms 7872 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 865 ms 30432 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 888 ms 30324 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 59 ms 1528 KB 1001 numbers
19 Correct 748 ms 15720 KB 15001 numbers
20 Correct 1950 ms 32608 KB 44445 numbers
21 Correct 1599 ms 32504 KB 22223 numbers
22 Execution timed out 3063 ms 55052 KB Time limit exceeded