oj.uz

Submission #232977

# Submission time Handle Problem Language Result Execution time Memory
232977 2020-05-18T20:23:03 Z amoo_safar Svjetlost (COI18_svjetlost) C++14
14 / 100
 168 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;
}
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){
	Apply(bf[x], -1);
	Apply(x, -1);
	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);
}

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';
	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;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB 11th numbers differ - expected: '34974.5467395685', found: '34816.0652380000', error = '0.0045313383'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB 11th numbers differ - expected: '34974.5467395685', found: '34816.0652380000', error = '0.0045313383'
2 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 38 ms 4352 KB found '31424400.0534069985', expected '31424400.0534067489', error '0.0000000000'
5 Correct 161 ms 16520 KB found '3142086769.6889739037', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 168 ms 16632 KB found '3142076120.8714599609', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 896 KB 68th numbers differ - expected: '1042871452.8534376621', found: '1042655967.3918279409', error = '0.0002066271'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB 11th numbers differ - expected: '34974.5467395685', found: '34816.0652380000', error = '0.0045313383'
2 Halted 0 ms 0 KB -