oj.uz

Submission #233000

# Submission time Handle Problem Language Result Execution time Memory
233000 2020-05-18T22:14:21 Z amoo_safar Svjetlost (COI18_svjetlost) C++14
14 / 100
 158 ms 16632 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);
	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];
	R = RevMatch(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);
	while(L != R){
		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);
	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

*/

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB found '32934.3604540000', expected '32934.3604541195', error '0.0000000000'
2 Correct 7 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 152 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 Runtime error 10 ms 1536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -