oj.uz

Submission #43880

# Submission time Handle Problem Language Result Execution time Memory
43880 2018-03-27T01:15:28 Z ngkan146 Svjetlost (COI18_svjetlost) C++11
100 / 100
 1282 ms 42496 KB 
#include <bits/stdc++.h>
using namespace std;
int dsup[100005];
int dsu_p(int x){
    return dsup[x] == x ? x : dsup[x] = dsu_p(dsup[x]);
}
void dsu_union(int x,int y){
    x = dsu_p(x);
    y = dsu_p(y);
    dsup[y] = x;
}
struct point{
    int x, y;
    point(int x=0,int y=0): x(x), y(y) {}
    point operator - (const point& v){
        return {x - v.x, y - v.y};
    }
};
double dist(point a,point b){
    return sqrt(1.0 * (a.x - b.x) * (a.x - b.x) + 1.0 * (a.y - b.y) * (a.y - b.y));
}
int ccw(point a,point b){
    long long val = 1ll * a.x * b.y - 1ll * a.y * b.x;
    if (val > 0)
        return 1;
    if (val == 0)
        return 0;
    return -1;
}
struct segTreeMAX{
    double node[400005];
    double lazy[400005];
    void doLazy(int id,int l,int r){
        node[id] += lazy[id];
        if (l != r){
            lazy[2*id] += lazy[id];
            lazy[2*id+1] += lazy[id];
        }
        lazy[id] = 0;
    }
    void upd(int id,int l,int r,int u,int v,double val){
        doLazy(id, l, r);
        if (r < u || v < l)
            return;
        if (u <= l && r <= v){
            lazy[id] += val;
            doLazy(id,l,r);
            return;
        }
        upd(2*id, l, (l+r)/2, u, v, val);
        upd(2*id+1, (l+r)/2+1, r, u, v ,val);
        node[id] = max(node[2*id], node[2*id+1]);
    }
    double get(int id,int l,int r,int u,int v){
        doLazy(id,l,r);
        if (r < u || v < l)
            return -1;
        if (u <= l && r <= v)
            return node[id];
        return max(get(2*id, l, (l+r)/2, u, v), get(2*id+1, (l+r)/2+1, r, u, v));
    }
    void updQuery(int l,int r,int n,double val){
        if (l <= r)
            upd(1, 1, n, l, r, val);
        else
            upd(1, 1, n, 1, r, val),
            upd(1, 1, n, l, n, val);
    }
}   seg;
struct segTreeSum{
    double node[400005];
    void upd(int id,int l,int r,int pos,double val){
        if (r < pos || pos < l)
            return;
        if (l == r){
            node[id] += val;
            return;
        }
        upd(2*id, l, (l+r)/2, pos, val);
        upd(2*id+1, (l+r)/2+1, r, pos ,val);
        node[id] = node[2*id] + node[2*id+1];
    }
    double get(int id,int l,int r,int u,int v){
        if (r < u || v < l)
            return 0;
        if (u <= l && r <= v)
            return node[id];
        return get(2*id, l, (l+r)/2, u, v) + get(2*id+1, (l+r)/2+1, r, u, v);
    }
    double getQuery(int l,int r,int n){
        if (l <= r)
            return get(1, 1, n, l, r);
        else
            return get(1, 1, n, 1, r) + get(1, 1, n, l, n);
    }
}   segConsecutive;
int n, q;
int prv[100005], nxt[100005], antipodal[100005], antipodalMAX[100005];
point a[100005];
void re(int x){
    // check
    int l = (nxt[x] - x + n) % n, r=n;
    while(l+1<r){
        int mid = (l+r)/2;
        int val = (x+mid+n-1) % n + 1;
        val = dsu_p(val);
        if (ccw(a[nxt[x]] - a[x], a[nxt[val]] - a[val]) > 0)
            l = mid;
        else
            r = mid;
    }
    antipodal[x]  = nxt[dsu_p((x+l+n-1)%n+1)];

    r = n;
    while(l+1<r){
        int mid = (l+r)/2;
        int val = (x+mid+n-1) % n + 1;
        val = dsu_p(val);
        if (ccw(a[nxt[x]] - a[x], a[nxt[val]] - a[val]) >= 0)
            l = mid;
        else
            r = mid;
    }
    antipodalMAX[x] = nxt[dsu_p((x+l+n-1)%n+1)];
}
int main(){
    for(int i=1;i<=100000;i++)
        dsup[i] = i;
    iostream::sync_with_stdio(0);
    cout << fixed << setprecision(9);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i].x >> a[i].y;
        prv[i] = i-1;
        nxt[i] = i+1;
    }   prv[1] = n; nxt[n] = 1;

    double curval = dist(a[1], a[2]);

    a[0] = a[1];    // temp
    antipodal[0] = 2;// temp
    antipodalMAX[0]=2;//temp

    for(int i=1;i<=n;i++){
        curval -= dist(a[i-1], a[i]);
        antipodal[i] = antipodal[i-1];
        antipodalMAX[i] = antipodalMAX[i-1];

        while(ccw(a[nxt[i]] - a[i], a[nxt[antipodal[i]]] - a[antipodal[i]]) > 0)
            curval += dist(a[antipodal[i]], a[nxt[antipodal[i]]]),
            antipodal[i] = nxt[antipodal[i]];
        while(ccw(a[nxt[i]] - a[i], a[nxt[antipodalMAX[i]]] - a[antipodalMAX[i]]) >= 0)
            antipodalMAX[i] = nxt[antipodalMAX[i]];

        seg.upd(1,1,n,i,i,curval);
        segConsecutive.upd(1,1,n,i, dist(a[i], a[nxt[i]]));
    }
    for(int i=1;i<=n;i++)   re(i);
    cout << seg.get(1,1,n,1,n) << '\n';

    cin >> q;
    while(q--){
        int pos;
        cin >> pos;

        re(pos);
        re(prv[pos]);

        // upd
        seg.updQuery(antipodalMAX[pos], prv[pos], n, -dist(a[nxt[pos]], a[pos]));
        seg.updQuery(antipodalMAX[prv[pos]], prv[pos], n, - dist(a[pos], a[prv[pos]]));

        segConsecutive.upd(1,1,n,prv[pos], -dist(a[prv[pos]], a[pos]));
        segConsecutive.upd(1,1,n,pos,  - dist(a[pos], a[nxt[pos]]));

        // erase
        seg.upd(1, 1, n, pos, pos, -1e18);
        nxt[prv[pos]] = nxt[pos];
        prv[nxt[pos]] = prv[pos];
        dsu_union(prv[pos], pos);

        // fix pos val
        pos = prv[pos];
        re(pos);
        segConsecutive.upd(1,1,n,pos, dist(a[pos], a[nxt[pos]]));
        seg.updQuery(antipodalMAX[pos], pos, n, dist(a[pos], a[nxt[pos]]));

        double curval = segConsecutive.getQuery(pos,prv[antipodal[pos]],n);
        seg.upd(1,1,n,pos,pos, curval - seg.get(1,1,n,pos,pos));

        cout << seg.get(1,1,n,1,n) << '\n';
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB 11 numbers
2 Correct 3 ms 1680 KB 41 numbers
3 Correct 3 ms 1680 KB 11 numbers
4 Correct 3 ms 1692 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB 11 numbers
2 Correct 3 ms 1680 KB 41 numbers
3 Correct 3 ms 1680 KB 11 numbers
4 Correct 3 ms 1692 KB 93 numbers
5 Correct 4 ms 1712 KB 101 numbers
6 Correct 12 ms 1896 KB 1201 numbers
7 Correct 16 ms 2044 KB 1556 numbers
8 Correct 25 ms 2176 KB 1996 numbers
9 Correct 25 ms 2208 KB 1960 numbers
10 Correct 18 ms 2276 KB 1991 numbers
11 Correct 21 ms 2288 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2288 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
2 Correct 4 ms 2312 KB found '31571636.3365447707', expected '31571636.3365447633', error '0.0000000000'
3 Correct 14 ms 3400 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 24 ms 4680 KB found '31424400.0534065552', expected '31424400.0534067489', error '0.0000000000'
5 Correct 103 ms 12320 KB found '3142086769.6889634132', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 105 ms 13876 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 13876 KB 1001 numbers
2 Correct 138 ms 13876 KB 15001 numbers
3 Correct 382 ms 13876 KB 44445 numbers
4 Correct 281 ms 18168 KB 22223 numbers
5 Correct 789 ms 22612 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1528 KB 11 numbers
2 Correct 3 ms 1680 KB 41 numbers
3 Correct 3 ms 1680 KB 11 numbers
4 Correct 3 ms 1692 KB 93 numbers
5 Correct 4 ms 1712 KB 101 numbers
6 Correct 12 ms 1896 KB 1201 numbers
7 Correct 16 ms 2044 KB 1556 numbers
8 Correct 25 ms 2176 KB 1996 numbers
9 Correct 25 ms 2208 KB 1960 numbers
10 Correct 18 ms 2276 KB 1991 numbers
11 Correct 21 ms 2288 KB 1963 numbers
12 Correct 3 ms 2288 KB found '32934.3604541190', expected '32934.3604541195', error '0.0000000000'
13 Correct 4 ms 2312 KB found '31571636.3365447707', expected '31571636.3365447633', error '0.0000000000'
14 Correct 14 ms 3400 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 24 ms 4680 KB found '31424400.0534065552', expected '31424400.0534067489', error '0.0000000000'
16 Correct 103 ms 12320 KB found '3142086769.6889634132', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 105 ms 13876 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 14 ms 13876 KB 1001 numbers
19 Correct 138 ms 13876 KB 15001 numbers
20 Correct 382 ms 13876 KB 44445 numbers
21 Correct 281 ms 18168 KB 22223 numbers
22 Correct 789 ms 22612 KB 88889 numbers
23 Correct 1282 ms 25556 KB 98175 numbers
24 Correct 259 ms 25556 KB 25905 numbers
25 Correct 962 ms 28980 KB 98169 numbers
26 Correct 857 ms 31136 KB 91845 numbers
27 Correct 926 ms 34196 KB 98296 numbers
28 Correct 854 ms 36084 KB 85384 numbers
29 Correct 898 ms 38476 KB 85317 numbers
30 Correct 918 ms 41832 KB 98246 numbers
31 Correct 480 ms 42496 KB 50001 numbers