oj.uz

답안 #233013

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
233013 2020-05-18T22:42:48 Z amoo_safar Svjetlost (COI18_svjetlost) C++14
26 / 100
 18 ms 640 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 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, 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;
	assert(n <= 2000);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 6 ms 512 KB 101 numbers
6 Correct 11 ms 640 KB 1201 numbers
7 Correct 14 ms 640 KB 1556 numbers
8 Correct 18 ms 640 KB 1996 numbers
9 Correct 17 ms 640 KB 1960 numbers
10 Correct 17 ms 640 KB 1991 numbers
11 Correct 17 ms 640 KB 1963 numbers

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 ms 512 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
3 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 5 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 6 ms 512 KB 101 numbers
6 Correct 11 ms 640 KB 1201 numbers
7 Correct 14 ms 640 KB 1556 numbers
8 Correct 18 ms 640 KB 1996 numbers
9 Correct 17 ms 640 KB 1960 numbers
10 Correct 17 ms 640 KB 1991 numbers
11 Correct 17 ms 640 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
13 Correct 5 ms 512 KB found '31571636.3365450017', expected '31571636.3365447633', error '0.0000000000'
14 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -