Submission #248520

# Submission time Handle Problem Language Result Execution time Memory
248520 2020-07-12T15:18:01 Z vanic Svjetlost (COI18_svjetlost) C++14
14 / 100
52 ms 6520 KB
#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long long ll;
const int maxn=1e5+5, pot=(1<<17);

int n;
pair < int, int > tock[maxn];
pair < int, int > vektor[maxn];

int lij[maxn], des[maxn];

struct tournament{
	double t[pot*2];
	double prop[pot*2];
	void propagate(int x){
		t[x]+=prop[x];
		if(x<pot){
			prop[x*2]+=prop[x];
			prop[x*2+1]+=prop[x];
		}
		prop[x]=0;
	}
	void update(int x, double val){
		t[x]+=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2);
			propagate(x*2+1);
			t[x]=max(t[x*2], t[x*2+1]);
		}
	}
	void update1(int L, int D, int x, int l, int d, double val){
		propagate(x);
		if(L>=l && D<=d){
//			cout << "updateam " << x << endl;
			update(x, val);
			if(x<pot){
				prop[x*2]+=val;
				prop[x*2+1]+=val;
			}
			return;
		}
		if((L+D)/2>=l){
			update1(L, (L+D)/2, x*2, l, d, val);
		}
		if((L+D)/2+1<=d){
			update1((L+D)/2+1, D, x*2+1, l, d, val);
		}
	}
	double query(int L, int D, int x, int l, int d){
		propagate(x);
		if(L>=l && D<=d){
			return t[x];
		}
		double lijeva=0, desna=0;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return max(lijeva, desna);
	}
	void cisti(int L, int D, int x, int l, int d){
		propagate(x);
		if(L>=l && D<=d){
			return;
		}
		if((L+D)/2>=l){
			cisti(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			cisti((L+D)/2+1, D, x*2+1, l, d);
		}
	}
};

struct tournament1{
	double t[pot*2];
	void update(int x, double val){
		t[x]=val;
		for(x/=2; x>0; x/=2){
			t[x]=t[x*2]+t[x*2+1];
		}
	}
	double query(int L, int D, int x, int l, int d){
		if(L>=l && D<=d){
			return t[x];
		}
		double lijeva=0, desna=0;
		if((L+D)/2>=l){
			lijeva=query(L, (L+D)/2, x*2, l, d);
		}
		if((L+D)/2+1<=d){
			desna=query((L+D)/2+1, D, x*2+1, l, d);
		}
		return lijeva+desna;
	}
};

tournament T;
tournament1 T1;

ll ccw(pair < ll, ll > a, pair < ll, ll > b, pair < ll, ll > c){
	return a.first*(b.second-c.second)+b.first*(c.second-a.second)+c.first*(a.second-b.second);
}

double dist(pair < double, double > a, pair < double, double > b){
	return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}

bool cmp(pair < int, int > a, pair < int, int > b){
	return atan2(a.second, a.first)<atan2(b.second, b.first);
}

int binary(int pos){
	int lo=0, hi=n, mid;
	while(lo<hi){
		mid=(lo+hi)/2+1;
		if(ccw({0, 0}, vektor[pos], vektor[(pos+mid)%n])>0){
			lo=mid;
		}
		else{
			hi=mid-1;
		}
	}
	return lo;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	cout << fixed;
	cout << setprecision(10);
	int a, b;
	for(int i=0; i<n; i++){
		cin >> a >> b;
		tock[i]={a, b};
		lij[i]=(i+n-1)%n;
		des[i]=(i+1)%n;
	}
	for(int i=0; i<n; i++){
		if(i!=n-1){
			vektor[i]={tock[i+1].first-tock[i].first, tock[i+1].second-tock[i].second};
			T1.update(i+pot, dist(tock[i], tock[i+1]));
		}
		else{
			vektor[i]={tock[0].first-tock[i].first, tock[0].second-tock[i].second};
			T1.update(i+pot, dist(tock[i], tock[0]));
		}
	}
//	sort(vektor, vektor+n, cmp);
/*	for(int i=0; i<n; i++){
		cout << vektor[i].first << " " << vektor[i].second << '\n';
		cout << atan2(vektor[i].second, vektor[i].first) << '\n';
	}*/
	int pos=1;
	double val=dist({0, 0}, vektor[0]);
	for(int i=0; i<n; i++){
		while(ccw({0, 0}, vektor[i], vektor[pos])>0){
			val+=dist({0, 0}, vektor[pos]);
			pos=(pos+1)%n;
		}
//		cout << val << '\n';
		T.update(pot+i, val);
		val-=dist({0, 0}, vektor[i]);
	}
	cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
	int q;
	cin >> q;
	int x;
	for(int i=0; i<q; i++){
		cin >> a;
		a--;
		x=(binary(a)+a)%n;
		if(ccw({0, 0}, vektor[a], vektor[(x+1)%n])==0){
			x=(x+1)%n;
		}
		x=(x+1)%n;
//		cout << a << " " << x << endl;
		if(x>a){
			T.update1(0, pot-1, 1, x, n-1, -dist({0, 0}, vektor[a]));
			T.update1(0, pot-1, 1, 0, a, -dist({0, 0}, vektor[a]));
		}
		else{
			T.update1(0, pot-1, 1, x, a, -dist({0, 0}, vektor[a]));
		}

/*		T.cisti(0, pot-1, 1, x, x);
		cout << T.t[x+pot] << endl;*/


		x=(binary(lij[a])+lij[a])%n;
		if(ccw({0, 0}, vektor[lij[a]], vektor[(x+1)%n])==0){
			x=(x+1)%n;
		}
		x=(x+1)%n;
//		cout << lij[a] << " " << x << endl;
//		cout << "kraj\n";
		if(x>lij[a]){
			T.update1(0, pot-1, 1, x, n-1, -dist({0, 0}, vektor[lij[a]]));
			T.update1(0, pot-1, 1, 0, lij[a], -dist({0, 0}, vektor[lij[a]]));
		}
		else{
			T.update1(0, pot-1, 1, x, lij[a], -dist({0, 0}, vektor[lij[a]]));
		}
/*
		cout << dist({0, 0}, vektor[lij[a]]) << endl;
		T.cisti(0, pot-1, 1, x, x);
		cout << T.t[x+pot] << endl;
*/
		vektor[lij[a]]={tock[des[a]].first-tock[lij[a]].first, tock[des[a]].second-tock[lij[a]].second};
		T1.update(lij[a]+pot, dist(tock[des[a]], tock[lij[a]]));
		T1.update(a+pot, 0);
		T.cisti(0, pot-1, 1, lij[a], lij[a]);
		T.cisti(0, pot-1, 1, a, a);
		T.update(a+pot, -T.t[a+pot]);
		T.update(a+pot, -1e9);
		T.update(lij[a]+pot, -T.t[lij[a]+pot]);
		lij[des[a]]=lij[a];
		des[lij[a]]=des[a];
		x=(binary(lij[a])+lij[a])%n;
//		cout << lij[a] << " " << x << endl;
//		cout << vektor[lij[a]].first << " " << vektor[lij[a]].second << '\n';
		if(x>lij[a]){
			T.update(lij[a]+pot, T1.query(0, pot-1, 1, lij[a], x));
/*			cout << "tu" << endl;
			cout << T1.query(0, pot-1, 1, lij[a], x) << '\n';*/
		}
		else{
			T.update(lij[a]+pot, T1.query(0, pot-1, 1, lij[a], n-1)+T1.query(0, pot-1, 1, 0, x));
/*			cout << "ovdje" << endl;
			cout << T1.query(0, pot-1, 1, lij[a], n-1)+T1.query(0, pot-1, 1, 0, x) << '\n';*/
		}
		if(ccw({0, 0}, vektor[lij[a]], vektor[(x+1)%n])==0){
			x=(x+1)%n;
		}
		x=(x+1)%n;
/*		cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
		cout << lij[a] << " " << x << endl;

		T.cisti(0, pot-1, 1, x, x);
		cout << T.t[x+pot] << endl;*/

		if(x>lij[a]){
			T.update1(0, pot-1, 1, x, n-1, dist({0, 0}, vektor[lij[a]]));
			if(lij[a]){
				T.update1(0, pot-1, 1, 0, lij[a]-1, dist({0, 0}, vektor[lij[a]]));
			}
		}
		else{
			T.update1(0, pot-1, 1, x, lij[a]-1, dist({0, 0}, vektor[lij[a]]));
		}
		cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
	}
	return 0;
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB 11 numbers
2 Incorrect 1 ms 512 KB 38th numbers differ - expected: '38191.7444325295', found: '39498.9584578257', error = '0.0342276595'
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB 11 numbers
2 Incorrect 1 ms 512 KB 38th numbers differ - expected: '38191.7444325295', found: '39498.9584578257', error = '0.0342276595'
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 544 KB found '32934.3604541195', expected '32934.3604541195', error '0.0000000000'
2 Correct 2 ms 640 KB found '31571636.3365447707', expected '31571636.3365447633', error '0.0000000000'
3 Correct 7 ms 1408 KB found '31442617.6286691166', expected '31442617.6286691241', error '0.0000000000'
4 Correct 11 ms 2048 KB found '31424400.0534065552', expected '31424400.0534067489', error '0.0000000000'
5 Correct 49 ms 6520 KB found '3142086769.6889634132', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 52 ms 6520 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'
# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 768 KB 573rd numbers differ - expected: '1043227215.3493254185', found: '1046037162.4037644863', error = '0.0026935139'
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB 11 numbers
2 Incorrect 1 ms 512 KB 38th numbers differ - expected: '38191.7444325295', found: '39498.9584578257', error = '0.0342276595'
3 Halted 0 ms 0 KB -