oj.uz

Submission #233011

# Submission time Handle Problem Language Result Execution time Memory
233011 2020-05-18T22:35:56 Z amoo_safar Svjetlost (COI18_svjetlost) C++14
26 / 100
 3000 ms 16700 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];
}
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, int 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, -1e9, 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 256 KB 93 numbers

Subtask #2
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 256 KB 93 numbers
5 Correct 6 ms 512 KB 101 numbers
6 Correct 14 ms 640 KB 1201 numbers
7 Correct 17 ms 768 KB 1556 numbers
8 Correct 21 ms 768 KB 1996 numbers
9 Correct 20 ms 768 KB 1960 numbers
10 Incorrect 22 ms 768 KB 1988th numbers differ - expected: '3497170293.5628347397', found: '4825322758.1817188263', error = '0.3797791795'
11 Halted 0 ms 0 KB -

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 2432 KB found '31442617.6286690012', expected '31442617.6286691241', error '0.0000000000'
4 Correct 40 ms 4352 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 153 ms 16632 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 158 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 896 KB 1001 numbers
2 Correct 639 ms 4960 KB 15001 numbers
3 Correct 2705 ms 10360 KB 44445 numbers
4 Execution timed out 3076 ms 16700 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
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 256 KB 93 numbers
5 Correct 6 ms 512 KB 101 numbers
6 Correct 14 ms 640 KB 1201 numbers
7 Correct 17 ms 768 KB 1556 numbers
8 Correct 21 ms 768 KB 1996 numbers
9 Correct 20 ms 768 KB 1960 numbers
10 Incorrect 22 ms 768 KB 1988th numbers differ - expected: '3497170293.5628347397', found: '4825322758.1817188263', error = '0.3797791795'
11 Halted 0 ms 0 KB -