Submission #548188

#	Time	Username	Problem	Language	Result	Execution time	Memory
548188		mosiashvililuka	Aliens (IOI16_aliens)	C++14	4 / 100	1 ms	340 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
const long long ER=694712,N=99999999999999999LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,k,pi,pr[1000009],pas,K,B,X,lef,rig,mid,LEF1,LEF2,RIG1,RIG2,za,z,zz,KK;
long long bofx[1000009];
pair <long long, long long> p[1000009],pp[1000009];
pair <pair <long long, long long>, long long> seg[4000009];
//vector <vector <long long> > dp,dp2;
vector <long long> dp,dp2;
//deque <pair <pair <long long, long long> , long long> > de;
pair <long long, long long> P;
bool fun(pair <pair <long long, long long>, long long> q, pair <pair <long long, long long>, long long> w, long long rr){
	long long qw=q.first.first*rr+q.first.second,we=w.first.first*rr+w.first.second;
	if(qw==we){
		if(q.second<=w.second){
			return 0;
		}else{
			return 1;
		}
	}
	if(qw<we){
		return 1;
	}else{
		return 0;
	}
}
void upd(long long q, long long w, long long rr){
	if(q>w) return;
	pair <pair <long long, long long>, long long> Q;
	Q.first.first=K;Q.first.second=B;Q.second=KK;
	if(seg[rr].second==ER){
		seg[rr]=Q;
		return;
	}
	long long mid=(q+w)/2;
	if(fun(seg[rr],Q,mid)==1){
		swap(seg[rr].first.first,K);swap(seg[rr].first.second,B);swap(seg[rr].second,KK);
	}
	if(fun(seg[rr],Q,q)==1){
		upd(q,mid-1,rr*2);
	}
	if(fun(seg[rr],Q,w)==1){
		upd(mid+1,w,rr*2+1);
	}
}
void read(long long q, long long w, long long rr){
	if(q>w) return;
	long long mid=(q+w)/2;
	if(seg[rr].second!=ER){
	long long qw=seg[rr].first.first*X+seg[rr].first.second;
	if(qw>z||(qw==z&&seg[rr].second<zz)){
		z=qw;zz=seg[rr].second;
	}
	}
	if(X<mid){
		read(q,mid-1,rr*2);
	}
	if(X>mid){
		read(mid+1,w,rr*2+1);
	}
}
pair <long long, long long> DO(long long cost){
	//
	for(i=0; i<=a+1; i++){
		dp[i]=a*a+3+cost*(a+M);
	}
	//cout<<pr[3]<<endl;
	dp[0]=0;dp2[0]=0;
	for(i=1; i<=a; i++){
		if(bofx[i]==0){
			dp[i]=dp[i-1];dp2[i]=dp2[i-1];
			continue;
		}
		for(j=i; j>=1; j--){
			ii=j-1;
			K=(-2LL)*ii;B=dp[pr[ii]]+ii*ii;
			if(pr[ii]>ii) B-=(pr[ii]-ii)*(pr[ii]-ii);
			K=-K;B=-B;KK=dp2[pr[ii]];
			X=i;
			c=i*i-(K*X+B)+cost;
			//cout<<pr[ii]<<" "<<K<<" "<<B<<endl;
			//cout<<i<<" "<<j<<":"<<endl;
			//cout<<dp[i]<<" "<<dp2[i]<<" "<<c<<" "<<KK<<endl;
			if(dp[i]>c||(dp[i]==c&&KK<dp2[i])){
				dp[i]=c;dp2[i]=KK;
			}
		}
	}
	return make_pair(dp[a],dp2[a]);
	//
	pair <pair <long long, long long>, long long> Q;
	Q.first.first=ER;Q.first.second=ER;Q.second=ER;
	for(i=0; i<=a+1; i++){
		dp[i]=a*a+3+cost*(a+M);
	}
	za=1;
	while(za<a) za*=2;
	for(i=0; i<=za*2; i++) seg[i]=Q;
	dp[0]=0;dp2[0]=0;
	//de.clear();
	for(i=1; i<=a; i++){
		ii=i-1;
		K=(-2LL)*ii;B=dp[pr[ii]]+ii*ii;
		if(pr[ii]>ii) B-=(pr[ii]-ii)*(pr[ii]-ii);
		K=-K;B=-B;KK=dp2[pr[ii]];
		//cout<<i<<" "<<pr[ii]<<" "<<bofx[i]<<"    "<<K<<" "<<B<<" "<<KK<<endl;
		/*while(de.size()&&de.back().first.second<=B) de.pop_back();
		while(de.size()>=2){
			zx=(de[de.size()-1].first.second-B)*(K-de[de.size()-2].first.first);
			xc=(de[de.size()-2].first.second-B)*(K-de[de.size()-1].first.first);
			if(zx<xc){
				de.pop_back();
			}else{
				if(zx>xc) break;
				if(de[de.size()-1].second<dp2[pr[ii]]){
					break;
				}else{
					de.pop_back();
				}
			}
		}
		de.push_back({{K,B},dp2[pr[ii]]});*/
		upd(1,za,1);
		X=i;
		/*while(de.size()>=2){
			//if(de[0].first.first*X+de[0].first.second<=de[1].first.first*X+de[1].first.second) de.pop_front(); else break;
			if(de[0].first.first*X+de[0].first.second<de[1].first.first*X+de[1].first.second){
				de.pop_front();
			}else{
				if(de[0].first.first*X+de[0].first.second>de[1].first.first*X+de[1].first.second) break;
				if(de[0].second>=de[1].second){
					de.pop_front();
				}else{
					break;
				}
			}
		}*/
		if(bofx[i]==0){
			dp[i]=dp[i-1];dp2[i]=dp2[i-1];
			continue;
		}
		//K=de[0].first.first;B=de[0].first.second;
		z=-N;zz=N;
		read(1,za,1);
		//cout<<i<<" "<<z<<" "<<zz<<endl;
		//exit(0);
		X=i;
		dp[i]=i*i/*-(K*X+B)*/-z+cost;dp2[i]=zz+1;
	}
	//
	return make_pair(dp[a],dp2[a]);
}
long long take_photos(int Nn, int Mm, int Kk, std::vector<int> Rr, std::vector<int> Cc) {
	M=Nn;a=Mm;k=Kk;
	dp.resize(a+3);dp2.resize(a+3);
	/*for(i=0; i<a+3; i++){
		dp[i].resize(min(k,a)+3);
		dp2[i].resize(min(k,a)+3);
	}*/
	for(i=1; i<=M; i++){
		if(Rr[i-1]>Cc[i-1]) swap(Rr[i-1],Cc[i-1]);
		//pp[i]={Rr[i-1]+1,-Cc[i-1]-1};
		pp[i].first=Rr[i-1]+1;pp[i].second=-Cc[i-1]-1;
	}
	sort(pp+1,pp+M+1);
	for(i=1; i<=M; i++) pp[i].second=-pp[i].second;
	for(i=1; i<=M; i++){
		if(pi!=0&&p[pi].second>=pp[i].second){
			
		}else{
			pi++;p[pi]=pp[i];
		}
	}
	/*cout<<"rewrew "<<pi<<"\n";
	for(i=1; i<=pi; i++) cout<<p[i].first<<" "<<p[i].second<<"\n";*/
	for(i=1; i<=pi; i++){
		pr[p[i].first]=p[i].second;
		bofx[p[i].second]=p[i].first;
	}
	for(i=1; i<=a; i++){
		pr[i]=max(pr[i],pr[i-1]);
	}
	P=DO(0);LEF1=P.first;LEF2=P.second;
	//cout<<"0 0 0      "<<P.first<<" "<<P.second<<"\n\n";
	if(P.second<=k){
		return P.first;
	}
	lef=0;rig=a*a+1;
	while(1){
		if(lef+1>=rig) break;
		mid=(lef+rig)/2;
		P=DO(mid);
		//cout<<lef<<" "<<rig<<" "<<mid<<"      "<<P.first<<" "<<P.second<<endl;
		if(P.second<=k){
			rig=mid;RIG1=P.first;RIG2=P.second;
		}else{
			lef=mid;LEF1=P.first;LEF2=P.second;
		}
	}
	//
	if(RIG2==k){
		pas=RIG1-RIG2*rig;
	}else{
		pas=RIG1-k*rig;
	}
	return pas;
}

• Subtask 1: 4 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40