Submission #248512

#	Time	Username	Problem	Language	Result	Execution time	Memory
248512		vanic	Svjetlost (COI18_svjetlost)	C++14	14 / 100	49 ms	8348 KiB

Main

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <string.h>
#include <array>
#include <bitset>
#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(6);
	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]]));
//		cout << dist(tock[des[a]], tock[lij[a]]) << endl;
		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(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 << dist({0, 0}, vektor[lij[a]]) << endl;
		}
		cout << T.query(0, pot-1, 1, 0, n-1) << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31