oj.uz

Submission #127471

# Submission time Handle Problem Language Result Execution time Memory
127471 2019-07-09T12:00:54 Z minhtung0404 Svjetlost (COI18_svjetlost) C++17
26 / 100
 3000 ms 4232 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 = pos;
        while (cmp((cur+n-1) % n, pos)) cur = (cur + n - 1) % n;
        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 13 ms 504 KB 101 numbers
6 Correct 70 ms 632 KB 1201 numbers
7 Correct 108 ms 764 KB 1556 numbers
8 Correct 170 ms 760 KB 1996 numbers
9 Correct 211 ms 888 KB 1960 numbers
10 Correct 154 ms 1016 KB 1991 numbers
11 Correct 158 ms 792 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 20 ms 632 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 973 ms 2656 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Execution timed out 3039 ms 4232 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 888 KB 1001 numbers
2 Execution timed out 3035 ms 3876 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 13 ms 504 KB 101 numbers
6 Correct 70 ms 632 KB 1201 numbers
7 Correct 108 ms 764 KB 1556 numbers
8 Correct 170 ms 760 KB 1996 numbers
9 Correct 211 ms 888 KB 1960 numbers
10 Correct 154 ms 1016 KB 1991 numbers
11 Correct 158 ms 792 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 20 ms 632 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 973 ms 2656 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Execution timed out 3039 ms 4232 KB Time limit exceeded
16 Halted 0 ms 0 KB -