Submission #248769

#	Time	Username	Problem	Language	Result	Execution time	Memory
248769		vanic	Svjetlost (COI18_svjetlost)	C++14	14 / 100	57 ms	12408 KiB

Main

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


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


struct tournament2{
	pair < int, int > t[pot*2];
	pair < int, int > prop[pot*2];
	pair < int, int > prazno={1e9+1, 1e9+1};
	tournament2(){
		for(int i=0; i<pot*2; i++){
			prop[i]=prazno;
		}
	}
	void propagate(int x){
		if(prop[x]!=prazno){
			t[x]=prop[x];
			if(x<pot){
				prop[x*2]=prop[x];
				prop[x*2+1]=prop[x];
			}
			prop[x]=prazno;
		}
	}
	void update(int x, pair < int, int > val){
		t[x]=val;
		for(x/=2; x>0; x/=2){
			propagate(x*2+1);
			t[x]=t[x*2+1];
		}
	}
	void update1(int L, int D, int x, int l, int d, pair < int, int > val){
		propagate(x);
		if(L>=l && D<=d){
			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);
		}
	}
	int query(int L, int D, int x, int l, int d, pair < int, int > val){
		propagate(x);
		int y;
		if(L>=l && D<=d){
			if(ccw({0, 0}, val, t[x])>0){
				return -1;
			}
			if(val==t[x]){
				return -1;
			}
			if(x>=pot){
				return x-pot;
			}
			if(ccw({0, 0}, val, t[x*2])>0 || t[x*2]==val){
				return query((L+D)/2+1, D, x*2+1, l, d, val);
			}
			else{
				return query(L, (L+D)/2, x*2, l, d, val);
			}
		}
		if((L+D)/2>=l){
			y=query(L, (L+D)/2, x*2, l, d, val);
			if(y!=-1){
				return y;
			}
		}
		if((L+D)/2+1<=d){
			return query((L+D)/2+1, D, x*2+1, l, d, val);
		}
		return -1;
	}
	
};

tournament T;
tournament1 T1;
tournament2 T2;


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]));
		}
		T2.update(i+pot, vektor[i]);
	}
	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;
		x=T2.query(0, pot-1, 1, a, n-1, vektor[a]);
		if(x==-1){
			x=T2.query(0, pot-1, 1, 0, a-1, vektor[a]);
		}
		if(ccw({0, 0}, vektor[a], vektor[x])==0){
			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=T2.query(0, pot-1, 1, lij[a], n-1, vektor[lij[a]]);
		if(x==-1){
			x=T2.query(0, pot-1, 1, 0, lij[a]-1, vektor[lij[a]]);
		}
//		x=(binary(lij[a])+lij[a])%n;
		if(ccw({0, 0}, vektor[lij[a]], vektor[x])==0){
			x=(x+1)%n;
		}
//		cout << lij[a] << " " << x << endl;
/*		cout << vektor[lij[a]].first << " " << vektor[lij[a]].second << '\n';
		cout << vektor[x].first << " " << vektor[x].second << '\n';*/
//		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};
		if(lij[a]<a){
			T2.update1(0, pot-1, 1, lij[a], a, vektor[lij[a]]);
		}
		else{
			T2.update1(0, pot-1, 1, lij[a], n-1, vektor[lij[a]]);
			T2.update1(0, pot-1, 1, 0, a, vektor[lij[a]]);
		}
		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=T2.query(0, pot-1, 1, lij[a], n-1, vektor[lij[a]]);
//		cout << lij[a] << " " << x << endl;
		if(x==-1){
			x=T2.query(0, pot-1, 1, 0, lij[a]-1, vektor[lij[a]]);
		}
		x=(x+n-1)%n;
//		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;
}

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