oj.uz

Submission #127473

# Submission time Handle Problem Language Result Execution time Memory
127473 2019-07-09T12:01:36 Z minhtung0404 Svjetlost (COI18_svjetlost) C++17
26 / 100
 3000 ms 7756 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){
//        int cur = pos;
//        while (cmp(pos, (cur+1) % n)) cur = (cur + 1) % n;
//        return cur;
        if (cmp(pos, Max)){
            if (!cmp(pos, Min)) return Max;
            int l = Min, r = pos-1;
            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{
//        int cur = pos;
//        while (cmp((cur+n-1) % n, pos)) cur = (cur + n - 1) % n;
//        return cur;
        if (cmp(Min, pos)){
            if (!cmp(Max, pos)) return Min;
        int cur = Max;
        while (cmp((cur+n-1) % n, pos)) cur = (cur + n - 1) % n;
        return cur;
        return cur;
            int l = pos+1, 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 376 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 376 KB 93 numbers
5 Correct 9 ms 632 KB 101 numbers
6 Correct 40 ms 764 KB 1201 numbers
7 Correct 60 ms 760 KB 1556 numbers
8 Correct 94 ms 760 KB 1996 numbers
9 Correct 60 ms 856 KB 1960 numbers
10 Correct 63 ms 760 KB 1991 numbers
11 Correct 53 ms 820 KB 1963 numbers

Subtask #3
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 12 ms 632 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 499 ms 2796 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 1632 ms 4972 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
5 Execution timed out 3091 ms 7756 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1016 KB 1001 numbers
2 Execution timed out 3085 ms 5484 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
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 376 KB 93 numbers
5 Correct 9 ms 632 KB 101 numbers
6 Correct 40 ms 764 KB 1201 numbers
7 Correct 60 ms 760 KB 1556 numbers
8 Correct 94 ms 760 KB 1996 numbers
9 Correct 60 ms 856 KB 1960 numbers
10 Correct 63 ms 760 KB 1991 numbers
11 Correct 53 ms 820 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 12 ms 632 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 499 ms 2796 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Correct 1632 ms 4972 KB found '31424400.0534066260', expected '31424400.0534067489', error '0.0000000000'
16 Execution timed out 3091 ms 7756 KB Time limit exceeded
17 Halted 0 ms 0 KB -