//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){
if (cmp(pos, Max)){
if (!cmp(pos, Min)) return Max;
int l = Min, r = l[pos];
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 = r[pos], 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";
}
}
Compilation message
svjetlost.cpp: In function 'long long int Find(long long int, long long int)':
svjetlost.cpp:54:35: error: invalid types 'long long int[long long int]' for array subscript
int l = Min, r = l[pos];
^
