// Never let them see you bleed...
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
const int maxn = 1e5 + 10, mod = 1e9 + 7;
const ld inf = 1e18;
pll p[maxn];
ll operator * (pll a, pll b){
return a.F * b.S - a.S * b.F;
}
ll operator ^ (pll a, pll b){
return a.F * b.F + a.S * b.S;
}
pll operator + (pll a, pll b){
return {a.F + b.F, a.S + b.S};
}
pll operator - (pll a, pll b){
return {a.F - b.F, a.S - b.S};
}
double lnn(pll a, pll b){
return sqrt((a-b) ^ (a-b));
}
int n;
int nxt[maxn], bef[maxn];
pair<int, ld> iter(int l, int r){
double len = 0;
if(r == l)
r = nxt[r], len+= lnn(p[l], p[r]);
while(l != r && (p[nxt[l]] - p[l]) * (p[nxt[r]] - p[r]) > 0)
len+= lnn(p[r], p[nxt[r]]), r = nxt[r];
return {r, len};
}
ld val[4 * maxn], lz[4 * maxn];
int lzr[4 * maxn], mnr[4 * maxn], mxr[4 * maxn], mnl[4 * maxn], mxl[4 * maxn];
bool emp[4 * maxn];
void shift(int l, int r, int id){
val[id]+= lz[id];
if(lzr[id] != -1){
mnr[id] = mxr[id] = lzr[id];
}
if(r-l > 1){
lz[2*id]+= lz[id];
lz[2*id+1]+= lz[id];
if(lzr[id] != -1)
lzr[2*id] = lzr[2*id+1] = lzr[id];
}
lz[id] = 0;
lzr[id] = -1;
}
void merge(int id){
val[id] = max(val[2*id], val[2*id+1]);
emp[id] = emp[2*id] && emp[2*id+1];
if(emp[2*id])
mnr[id] = mnr[2*id+1], mnl[id] = mnl[2*id+1];
else
mnr[id] = mnr[2*id], mnl[id] = mnl[2*id];
if(emp[2*id+1])
mxr[id] = mxr[2*id], mxl[id] = mxl[2*id];
else
mxr[id] = mxr[2*id+1], mxl[id] = mxl[2*id+1];
}
void off(int pos, int l = 0, int r = n, int id = 1){
shift(l, r, id);
if(r-l == 1){
val[id] = -inf;
emp[id] = 1;
return;
}
int mid = (l+r) >> 1;
if(pos < mid)
off(pos, l, mid, 2*id);
else
off(pos, mid, r, 2*id+1);
merge(id);
}
bool inside(int L, int pos, int R){
return ((pos-L+n)%n) + ((R-pos+n)%n) == ((R-L+n)%n);
}
void addAll(ld x, int l, int r, int id){
val[id]+= x;
// shift(l, r, id);
if(r-l == 1)
return;
int mid = (l+r) >> 1;
addAll(x, l, mid, 2*id);
addAll(x, mid, r, 2*id+1);
}
void recalc(int befp, int pos, int l = 0, int r = n, int id = 1){
if(emp[id])
return;
shift(l, r, id);
bool A = inside(mnl[id], befp, mnr[id]), B = inside(mxl[id], befp, mxr[id]);
if(r-l == 1 && l == befp){
auto x = iter(l, mxr[id]);
val[id]+= x.S - lnn(p[pos], p[bef[pos]]) - lnn(p[pos], p[nxt[pos]]) + lnn(p[bef[pos]], p[nxt[pos]]);
mxr[id] = mnr[id] = x.F;
return;
}
if(r <= befp || befp < l){ // out of seg
if(!A && !B)
return;
if(A && B){
if(mnr[id] == pos && mxr[id] == pos){
auto x = iter(mnl[id], befp), y = iter(mxl[id], befp);
if(x.F == y.F){
lz[id]+= -lnn(p[pos], p[befp]) + x.S;
lzr[id] = x.F;
shift(l, r, id);
return;
}
}
else if(mnr[id] == befp && mxr[id] == befp){
auto x = iter(mnl[id], befp), y = iter(mxl[id], befp);
if(x.F == y.F){
lz[id]+= x.S;
lzr[id] = x.F;
shift(l, r, id);
return;
}
}
else if(mnl[id] != nxt[befp] && inside(mnl[id], nxt[befp], mnr[id]) && inside(mxl[id], nxt[befp], mxr[id])){
assert(lz[id] == 0 && lzr[id] == -1);
addAll(-lnn(p[pos], p[bef[pos]]) - lnn(p[pos], p[nxt[pos]]) + lnn(p[bef[pos]], p[nxt[pos]]), l, r, id);
return;
lz[id]+= -lnn(p[pos], p[bef[pos]]) - lnn(p[pos], p[nxt[pos]]) + lnn(p[bef[pos]], p[nxt[pos]]);
shift(l, r, id);
return;
}
}
}
int mid = (l+r) >> 1;
recalc(befp, pos, l, mid, 2*id);
recalc(befp, pos, mid, r, 2*id+1);
merge(id);
}
void build(int l = 0, int r = n, int id = 1){
static int R = 0;
static ld len = 0;
if(r-l == 1){
auto y = iter(l, R);
len+= y.S;
R = y.F;
mnl[id] = mxl[id] = l;
mnr[id] = mxr[id] = R;
val[id] = len;
len-= lnn(p[l], p[nxt[l]]);
return;
}
int mid = (l+r) >> 1;
build(l, mid, 2*id);
build(mid, r, 2*id+1);
merge(id);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();
memset(lzr, -1, sizeof lzr);
cin >> n;
for(int i = 0; i < n; i++){
cin >> p[i].F >> p[i].S;
nxt[i] = (i+1) % n;
bef[i] = (i+n-1) % n;
}
build();
cout << setprecision(7) << fixed << val[1]+lz[1] << "\n";
int q;
cin >> q;
while(q--){
int pos;
cin >> pos;
--pos;
int L = bef[pos], R = nxt[pos];
bef[R] = L, nxt[L] = R;
off(pos);
recalc(L, pos);
cout << setprecision(7) << fixed << val[1]+lz[1] << "\n";
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1920 KB |
11 numbers |
| 2 |
Correct |
5 ms |
2048 KB |
41 numbers |
| 3 |
Correct |
5 ms |
1920 KB |
11 numbers |
| 4 |
Correct |
7 ms |
1920 KB |
93 numbers |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1920 KB |
11 numbers |
| 2 |
Correct |
5 ms |
2048 KB |
41 numbers |
| 3 |
Correct |
5 ms |
1920 KB |
11 numbers |
| 4 |
Correct |
7 ms |
1920 KB |
93 numbers |
| 5 |
Correct |
7 ms |
2048 KB |
101 numbers |
| 6 |
Correct |
23 ms |
2304 KB |
1201 numbers |
| 7 |
Correct |
32 ms |
2304 KB |
1556 numbers |
| 8 |
Correct |
46 ms |
2296 KB |
1996 numbers |
| 9 |
Incorrect |
36 ms |
2304 KB |
1341st numbers differ - expected: '35149029.3687862679', found: '59352231.8890658990', error = '0.6885880764' |
| 10 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
1920 KB |
found '32934.3604541000', expected '32934.3604541195', error '0.0000000000' |
| 2 |
Correct |
6 ms |
2176 KB |
found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000' |
| 3 |
Correct |
9 ms |
3328 KB |
found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000' |
| 4 |
Correct |
13 ms |
4480 KB |
found '31424400.0534064993', expected '31424400.0534067489', error '0.0000000000' |
| 5 |
Correct |
39 ms |
12280 KB |
found '3142086769.6889934540', expected '3142086769.6889681816', error '0.0000000000' |
| 6 |
Correct |
38 ms |
12280 KB |
found '3142076120.8714604378', expected '3142076120.8714694977', error '0.0000000000' |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
2432 KB |
1001 numbers |
| 2 |
Execution timed out |
3053 ms |
6360 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
1920 KB |
11 numbers |
| 2 |
Correct |
5 ms |
2048 KB |
41 numbers |
| 3 |
Correct |
5 ms |
1920 KB |
11 numbers |
| 4 |
Correct |
7 ms |
1920 KB |
93 numbers |
| 5 |
Correct |
7 ms |
2048 KB |
101 numbers |
| 6 |
Correct |
23 ms |
2304 KB |
1201 numbers |
| 7 |
Correct |
32 ms |
2304 KB |
1556 numbers |
| 8 |
Correct |
46 ms |
2296 KB |
1996 numbers |
| 9 |
Incorrect |
36 ms |
2304 KB |
1341st numbers differ - expected: '35149029.3687862679', found: '59352231.8890658990', error = '0.6885880764' |
| 10 |
Halted |
0 ms |
0 KB |
- |
