oj.uz

Submission #127470

# Submission time Handle Problem Language Result Execution time Memory
127470 2019-07-09T12:00:34 Z minhtung0404 Svjetlost (COI18_svjetlost) C++17
26 / 100
 3000 ms 4212 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)){
        int cur = pos;
        while (cmp((cur+n-1) % n, pos)) cur = (cur + n - 1) % n;
        return cur;
            if (!cmp(Max, pos)) return Min;
            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 508 KB 101 numbers
6 Correct 72 ms 888 KB 1201 numbers
7 Correct 110 ms 920 KB 1556 numbers
8 Correct 171 ms 892 KB 1996 numbers
9 Correct 222 ms 764 KB 1960 numbers
10 Correct 163 ms 804 KB 1991 numbers
11 Correct 180 ms 908 KB 1963 numbers

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 19 ms 632 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 969 ms 2552 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Execution timed out 3047 ms 4212 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 936 KB 1001 numbers
2 Execution timed out 3038 ms 3780 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 508 KB 101 numbers
6 Correct 72 ms 888 KB 1201 numbers
7 Correct 110 ms 920 KB 1556 numbers
8 Correct 171 ms 892 KB 1996 numbers
9 Correct 222 ms 764 KB 1960 numbers
10 Correct 163 ms 804 KB 1991 numbers
11 Correct 180 ms 908 KB 1963 numbers
12 Correct 2 ms 380 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 19 ms 632 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 969 ms 2552 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Execution timed out 3047 ms 4212 KB Time limit exceeded
16 Halted 0 ms 0 KB -