Submission #127429

#	Time	Username	Problem	Language	Result	Execution time	Memory
127429		minhtung0404	Svjetlost (COI18_svjetlost)	C++17	43 / 100	594 ms	13152 KiB

Main

//https://oj.uz/problem/view/COI18_svjetlost

#include<bits/stdc++.h>
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 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{
        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, 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))));
//        for (int i = 0; i < n; i++) cout << wtf(1, 0, n-1, i, i) << " "; cout << "\n";
        cout << it[1] << "\n";
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 29 / 29
• Subtask 5: 0 / 31