oj.uz

Submission #127466

# Submission time Handle Problem Language Result Execution time Memory
127466 2019-07-09T11:57:32 Z minhtung0404 Svjetlost (COI18_svjetlost) C++17
26 / 100
 3000 ms 4192 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 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 22 ms 504 KB 101 numbers
6 Correct 130 ms 888 KB 1201 numbers
7 Correct 202 ms 876 KB 1556 numbers
8 Correct 319 ms 860 KB 1996 numbers
9 Correct 278 ms 900 KB 1960 numbers
10 Correct 308 ms 888 KB 1991 numbers
11 Correct 266 ms 892 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 38 ms 808 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
3 Correct 1969 ms 2640 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Execution timed out 3051 ms 4192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 888 KB 1001 numbers
2 Execution timed out 3042 ms 3788 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 22 ms 504 KB 101 numbers
6 Correct 130 ms 888 KB 1201 numbers
7 Correct 202 ms 876 KB 1556 numbers
8 Correct 319 ms 860 KB 1996 numbers
9 Correct 278 ms 900 KB 1960 numbers
10 Correct 308 ms 888 KB 1991 numbers
11 Correct 266 ms 892 KB 1963 numbers
12 Correct 2 ms 376 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
13 Correct 38 ms 808 KB found '31571636.3365447670', expected '31571636.3365447633', error '0.0000000000'
14 Correct 1969 ms 2640 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
15 Execution timed out 3051 ms 4192 KB Time limit exceeded
16 Halted 0 ms 0 KB -