oj.uz

Submission #127476

# Submission time Handle Problem Language Result Execution time Memory
127476 2019-07-09T12:05:03 Z minhtung0404 Svjetlost (COI18_svjetlost) C++17
100 / 100
 1389 ms 23372 KB 
//https://oj.uz/problem/view/COI18_svjetlost

#include<bits/stdc++.h>
#define int long long
#define double long double
const int N = 1e5 + 5;
const double inf = 1e18;
using namespace std;

struct point{
    int x, y;

    point(int x, int y) : x(x), y(y) {}
    point() {}

    point operator + (point a){
        return point(a.x + x, a.y + y);
    }

    point operator - (point a){
        return point(x - a.x, y - a.y);
    }
} a[N], b[N];

int n, q, p, l[N], r[N], pset[N], Min, Max;
double it[N << 2], lazy[N << 2], sum[N << 2];
bool del[N];

int findset(int i) {return ((pset[i] == i) ? i : pset[i] = findset(pset[i]));}

bool ccw(point a, point b){
    return 1LL * a.x * b.y < 1LL * a.y * b.x;
}

bool cmp(point a, point b){
    int x = ccw(b, a), y = ccw(a, b);
    if (x || y) return x;
    return (1LL * a.x * b.x + 1LL * a.y * b.y) > 0;
}

bool cmp(int i, int j){
    i = findset(i); j = findset(j);
    return cmp(b[i], b[j]);
}

double abs(point a){
    return sqrt(1.0 * a.x * a.x + 1.0 * a.y * a.y);
}

int Find(int pos, int type = 1){
    if (!type){
        if (cmp(pos, Max)){
            if (!cmp(pos, Min)) return Max;
            int r = l[pos], l = Min;
            while (l != r){
                int mid = (l + r + 1) >> 1;
                if (cmp(pos, mid)) l = mid;
                else r = mid-1;
            }
            return l;
        }
        else{
            int l = pos, r = Max;
            while (l != r){
                int mid = (l + r + 1) >> 1;
                if (cmp(pos, mid)) l = mid;
                else r = mid-1;
            }
            return l;
        }
    }
    else{
        if (cmp(Min, pos)){
            if (!cmp(Max, pos)) return Min;
            int l = r[pos], r = Max;
            while (l != r){
                int mid = (l + r) >> 1;
                if (cmp(mid, pos)) r = mid;
                else l = mid+1;
            }
            return l;
        }
        else{
            int l = Min, r = pos;
            while (l != r){
                int mid = (l + r) >> 1;
                if (cmp(mid, pos)) r = mid;
                else l = mid+1;
            }
            return l;
        }
    }
}

void dolazy(int i, int l, int r){
    if (!lazy[i]) return;
    if (l != r){
        lazy[i << 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
    }
    it[i] += lazy[i];
    lazy[i] = 0;
}

void update(int i, int l, int r, int L, int R, double val){
    dolazy(i, l, r);
    if (L > r || l > R) return;
    if (L <= l && r <= R){
        lazy[i] = val;
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, L, R, val); update(i << 1 | 1, mid+1, r, L, R, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void update(int i, int l, int r, int pos, double val){
    dolazy(i, l, r);
    if (pos > r || l > pos) return;
    if (l == r){
        it[i] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, pos, val); update(i << 1 | 1, mid+1, r, pos, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void update(int L, int R, double val){
    if (L > R) update(1, 0, n-1, L, n-1, val), update(1, 0, n-1, 0, R, val);
    else update(1, 0, n-1, L, R, val);
}

void update_sum(int i, int l, int r, int pos, double val){
    if (l > pos || pos > r) return;
    if (l == r){
        sum[i] = val;
        return;
    }
    int mid = (l + r) >> 1;
    update_sum(i << 1, l, mid, pos, val); update_sum(i << 1 | 1, mid+1, r, pos, val);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
}

double get(int i, int l, int r, int L, int R){
    if (L > r || l > R) return 0;
    if (L <= l && r <= R) return sum[i];
    int mid = (l + r) >> 1;
    return get(i << 1, l, mid, L, R) + get(i << 1 | 1, mid+1, r, L, R);
}

double get(int l, int r){
    if (l <= r) return get(1, 0, n-1, l, r);
    return get(1, 0, n-1, l, n-1) + get(1, 0, n-1, 0, r);
}

double wtf(int i, int l, int r, int L, int R){
    dolazy(i, l, r);
    if (L > r || l > R) return -inf;
    if (L <= l && r <= R) return it[i];
    int mid = (l + r) >> 1;
    return max(wtf(i << 1, l, mid, L, R), wtf(i << 1 | 1, mid+1, r, L, R));
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cout << fixed << setprecision(10);
    cin >> n; Min = 0, Max = n-1;
    for (int i = 0; i < n; i++) cin >> a[i].x >> a[i].y;
    for (int i = 0; i < n; i++) b[i] = a[(i+1) % n] - a[i], l[i] = (i+n-1) % n, r[i] = (i+1)%n, pset[i] = i;
    for (int i = 0; i < n; i++) update(Find(i), i, abs(b[i])), update_sum(1, 0, n-1, i, abs(b[i]));
    cout << it[1] << "\n";
    cin >> q;
    while (q--){
        cin >> p; p--;

        update(findset(Find(l[p])), l[p], -abs(b[l[p]]));
        update(findset(Find(p)), p, -abs(b[p]));

        r[l[p]] = r[p]; l[r[p]] = l[p];
        del[p] = true; while (del[Min]) Min++; while (del[Max]) Max--;
        b[l[p]] = b[l[p]] + b[p]; pset[p] = l[p];
        update_sum(1, 0, n-1, p, 0);
        update_sum(1, 0, n-1, l[p], abs(b[l[p]]));

        update(findset(Find(l[p])), l[p], abs(b[l[p]]));
        update(1, 0, n-1, p, -inf);
        update(1, 0, n-1, l[p], get(l[p], findset(Find(l[p], 0))));
        cout << it[1] << "\n";
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 384 KB 93 numbers
5 Correct 4 ms 632 KB 101 numbers
6 Correct 12 ms 760 KB 1201 numbers
7 Correct 15 ms 760 KB 1556 numbers
8 Correct 19 ms 760 KB 1996 numbers
9 Correct 17 ms 760 KB 1960 numbers
10 Correct 17 ms 760 KB 1991 numbers
11 Correct 17 ms 760 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 4 ms 760 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 22 ms 2780 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 41 ms 4968 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Correct 183 ms 17784 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 184 ms 19196 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1016 KB 1001 numbers
2 Correct 152 ms 5592 KB 15001 numbers
3 Correct 427 ms 11768 KB 44445 numbers
4 Correct 359 ms 19672 KB 22223 numbers
5 Correct 883 ms 22520 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB 11 numbers
2 Correct 2 ms 376 KB 41 numbers
3 Correct 2 ms 376 KB 11 numbers
4 Correct 3 ms 384 KB 93 numbers
5 Correct 4 ms 632 KB 101 numbers
6 Correct 12 ms 760 KB 1201 numbers
7 Correct 15 ms 760 KB 1556 numbers
8 Correct 19 ms 760 KB 1996 numbers
9 Correct 17 ms 760 KB 1960 numbers
10 Correct 17 ms 760 KB 1991 numbers
11 Correct 17 ms 760 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 4 ms 760 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 22 ms 2780 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 41 ms 4968 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Correct 183 ms 17784 KB found '3142086769.6889743805', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 184 ms 19196 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 12 ms 1016 KB 1001 numbers
19 Correct 152 ms 5592 KB 15001 numbers
20 Correct 427 ms 11768 KB 44445 numbers
21 Correct 359 ms 19672 KB 22223 numbers
22 Correct 883 ms 22520 KB 88889 numbers
23 Correct 1389 ms 23372 KB 98175 numbers
24 Correct 306 ms 6008 KB 25905 numbers
25 Correct 1065 ms 23212 KB 98169 numbers
26 Correct 958 ms 22692 KB 91845 numbers
27 Correct 1077 ms 23160 KB 98296 numbers
28 Correct 968 ms 21860 KB 85384 numbers
29 Correct 897 ms 21820 KB 85317 numbers
30 Correct 1014 ms 23292 KB 98246 numbers
31 Correct 567 ms 20344 KB 50001 numbers