oj.uz

Submission #233016

# Submission time Handle Problem Language Result Execution time Memory
233016 2020-05-18T22:54:51 Z amoo_safar Svjetlost (COI18_svjetlost) C++14
100 / 100
 2491 ms 19704 KB 
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 1000000007LL;
const int N = 1e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ld seg[N << 2];
ld lz[N << 2];

void Add(int id, int l, int r, ld x, int L, int R){
	if((r <= L) || (R <= l)) return ;
	if((l <= L) && (R <= r)){
		lz[id] += x;
		seg[id] += x;
		return ;
	}
	int mid = (L + R) >> 1;
	Add(id << 1, l, r, x, L, mid);
	Add(id << 1 | 1, l, r, x, mid, R);
	seg[id] = max(seg[id << 1], seg[id << 1 | 1]) + lz[id];
}

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};
}
ll operator * (pll a, pll b){
	return a.F * b.S - a.S * b.F;
}

typedef pair<pll, ll> nd;

struct CMP {
	bool operator() (nd A, nd B) const {
		pll a = A.F, b = B.F;
		if(a == b) return A.S < B.S;
		int fa = a < pll(0, 0);
		int fb = b < pll(0, 0);
		if(fa != fb) return fa > fb;
		return a*b > 0;
	}
};

multiset<nd, CMP> ms;

ll n;
ll nx[N], bf[N];
pll p[N];

int Match(int x){
	pll e = p[x] - p[nx[x]];
	auto it = ms.lower_bound({e, -1});
	if(it == ms.begin()) it = --ms.end();
	else it --;
	return it -> S;
}
int RevMatch(int x){
	//int res = bf[bf[x]];
	//while((p[bf[x]] - p[x]) * (p[res] - p[nx[res]]) < 0) res = bf[res];
	//return nx[res];
	int wh = Match(bf[x]);
	if(((p[x]-p[bf[x]]) * (p[wh] - p[nx[wh]])) == 0) wh = nx[wh];
	return wh;
}

ld Len(pll x){ return sqrt(x.F*x.F + x.S*x.S); }


void Add(int l, int r, ld ln){
	if(l <= r){
		Add(1, l, r + 1, ln, 0, n);
	} else {
		Add(1, l, n, ln, 0, n);
		Add(1, 0, r + 1, ln, 0, n);
	}
}
void Apply(int x, ld z){
	Add(nx[x], Match(x), z*Len(p[nx[x]] - p[x]));
}
void Rem(int x){
	int L, R;
	Apply(bf[x], -1);
	Apply(x, -1);
	L = RevMatch(x);
	R = RevMatch(nx[x]);
	
	ms.erase(ms.find({p[nx[x]] - p[x], nx[x]}));
	ms.erase(ms.find({p[x] - p[bf[x]], x}));
	bf[nx[x]] = bf[x];
	nx[bf[x]] = nx[x];

	ms.insert({p[nx[x]] - p[bf[x]], nx[x]});
	Apply(bf[x], 1);
	Add(1, x, x + 1, -1e15, 0, n);
	ld sm = 0;
	//assert(L == R);
	//cerr << L << ' ' << R << '\n';
	while(L != R){
		/*debug(L);
		debug(((p[nx[L]] - p[L]) * (p[nx[x]] - p[bf[x]])));
		debug((p[nx[L]] - p[L]).F);
		debug((p[nx[L]] - p[L]).S);
		debug((p[nx[x]] - p[bf[x]]).F);
		debug((p[nx[x]] - p[bf[x]]).S);
		*/
		if( ((p[nx[L]] - p[L]) * (p[nx[x]] - p[bf[x]])) > 0) sm += Len(p[L] - p[nx[L]]);
		L = nx[L];
	}
	//assert(sm == 0);
	//assert(sm < 1);
	//cerr << sm << '\n';
	Add(1, nx[x], nx[x] + 1, sm, 0, n);
}

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 0; i < n; i++)
		cin >> p[i]. F >> p[i].S;
	for(int i = 0; i < n; i++) nx[i] = (i + 1) % n;
	for(int i = 0; i < n; i++) bf[nx[i]] = i;

	for(int i = 0; i < n; i++)
		ms.insert({ p[i] - p[bf[i]], i });
	for(int i = 0; i < n; i++) Apply(i, 1);
	cout << fixed << setprecision(6) << seg[1] << '\n';
	//for(int i = 0; i < n; i++) cerr << i << ' ' << RevMatch(i) << ' ' << Match(i) << '\n';
	
	ll Q;
	cin >> Q;
	int rm;
	for(int i = 0; i < Q; i++){
		cin >> rm;
		rm --;
		Rem(rm);
		cout << fixed << setprecision(6) << seg[1] << '\n';
	}
	return 0;
}
/*
3
0 0
1 0
0 1
0

4
0 0
2 0
2 2
0 2
1
1

*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 4 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 4 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 6 ms 512 KB 101 numbers
6 Correct 12 ms 640 KB 1201 numbers
7 Correct 15 ms 768 KB 1556 numbers
8 Correct 16 ms 768 KB 1996 numbers
9 Correct 15 ms 768 KB 1960 numbers
10 Correct 16 ms 768 KB 1991 numbers
11 Correct 15 ms 768 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 6 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Correct 21 ms 2560 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 37 ms 4344 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 156 ms 16504 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 156 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 896 KB 1001 numbers
2 Correct 122 ms 4984 KB 15001 numbers
3 Correct 348 ms 10116 KB 44445 numbers
4 Correct 294 ms 16696 KB 22223 numbers
5 Correct 686 ms 19064 KB 88889 numbers

Subtask #5
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 4 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 6 ms 512 KB 101 numbers
6 Correct 12 ms 640 KB 1201 numbers
7 Correct 15 ms 768 KB 1556 numbers
8 Correct 16 ms 768 KB 1996 numbers
9 Correct 15 ms 768 KB 1960 numbers
10 Correct 16 ms 768 KB 1991 numbers
11 Correct 15 ms 768 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 6 ms 640 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Correct 21 ms 2560 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
15 Correct 37 ms 4344 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
16 Correct 156 ms 16504 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 156 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 12 ms 896 KB 1001 numbers
19 Correct 122 ms 4984 KB 15001 numbers
20 Correct 348 ms 10116 KB 44445 numbers
21 Correct 294 ms 16696 KB 22223 numbers
22 Correct 686 ms 19064 KB 88889 numbers
23 Correct 981 ms 19688 KB 98175 numbers
24 Correct 216 ms 5368 KB 25905 numbers
25 Correct 1251 ms 19576 KB 98169 numbers
26 Correct 2491 ms 18880 KB 91845 numbers
27 Correct 1525 ms 19704 KB 98296 numbers
28 Correct 717 ms 18168 KB 85384 numbers
29 Correct 800 ms 18208 KB 85317 numbers
30 Correct 1524 ms 19704 KB 98246 numbers
31 Correct 452 ms 17016 KB 50001 numbers