Submission #550620

#	Time	Username	Problem	Language	Result	Execution time	Memory
550620		mosiashvililuka	Aliens (IOI16_aliens)	C++14	12 / 100	3 ms	436 KiB

aliens

#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,K,pi,pr[1000009],pas,dp[1000009],dp2[1000009],lef,rig,mid,A,B,C,X,za,z,zz;
long long bofx[1000009];
pair <long long, long long> p[1000009],pp[1000009];
pair <pair <long long, long long>, long long> seg[4000009];
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) return 0;
	if(qw>we) return 1;
	if(q.second>w.second) return 1;
	return 0;
}
void upd(long long q, long long w, long long rr){
	if(q>w) return;
	if(seg[rr].second==-1){
		seg[rr]={{A,B},C};
		return;
	}
	long long mid=(q+w)/2;
	if(fun(seg[rr],{{A,B},C},mid)){
		swap(seg[rr].first.first,A);swap(seg[rr].first.second,B);swap(seg[rr].second,C);
	}
	if(fun(seg[rr],{{A,B},C},q)){
		upd(q,mid-1,rr*2);
	}else{
		if(fun(seg[rr],{{A,B},C},w)){
			upd(mid+1,w,rr*2+1);
		}
	}
}
void read(long long q, long long w, long long rr){
	if(q>w) return;
	if(seg[rr].second==-1){
		return;
	}
	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;
	}
	long long mid=(q+w)/2;
	if(X<mid){
		read(q,mid-1,rr*2);
	}
	if(X>mid){
		read(mid+1,w,rr*2+1);
	}
}
pair <long long, long long> fun(){
	for(i=0; i<=a+1; i++){
		dp[i]=a*a+mid*(a+2)+3;dp2[i]=0;
	}
	za=1;
	while(za<a) za*=2;
	for(i=0; i<=za*2+2; i++){
		seg[i]={{-1,-1},-1};
	}
	dp[0]=0;dp2[0]=0;
	for(i=1; i<=a; i++){
		ii=i-1;
		if(pr[ii]>ii){
			A=-2*ii;B=ii*ii+dp[pr[ii]]-(pr[ii]-ii)*(pr[ii]-ii);C=dp2[pr[ii]];
			upd(1,za,1);
		}else{
			A=-2*ii;B=ii*ii+dp[pr[ii]];C=dp2[pr[ii]];
			upd(1,za,1);
		}
		if(bofx[i]==0){
			dp[i]=dp[i-1];dp2[i]=dp2[i-1];
			continue;
		}
		dp[i]=i*i+mid;dp2[i]=1;
		X=i;z=zz=999999999999999999LL;
		read(1,za,1);
		z+=i*i+mid;zz++;
		if(dp[i]>z||(dp[i]==z&&dp2[i]>zz)){
			dp[i]=z;dp2[i]=zz;
		}
	}
	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;pas=a*a+4;
	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};
	}
	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]);
	}
	/*
	for(i=0; i<=a+1; i++){
		for(j=0; j<=K+1; j++){
			dp[i][j]=a*a+3;
		}
	}
	dp[0][0]=0;
    for(i=1; i<=a; i++){
    	for(j=1; j<=min(i,K); j++){
    		if(bofx[i]==0){
    			dp[i][j]=dp[i-1][j];
    			continue;
			}
    		dp[i][j]=i*i;
    		for(ii=0; ii<i; ii++){
    			//zx=i*i+i*(-2*ii)+(dp[pr[ii]][j-1]-pr[ii]*pr[ii]+2*pr[ii]*ii);
    			if(pr[ii]>ii){
    				zx=(i-ii)*(i-ii)+dp[pr[ii]][j-1]-(pr[ii]-ii)*(pr[ii]-ii);
				}else{
					zx=(i-ii)*(i-ii)+dp[pr[ii]][j-1];
				}
    			dp[i][j]=min(dp[i][j],zx);
			}
		}
	}
	pas=dp[a][1];
	for(j=1; j<=K; j++){
		pas=min(pas,dp[a][j]);
	}
	*/
	pair <long long, long long> P;
	mid=0;
	P=fun();
	//exit(0);
	if(P.second<=K){
		return P.first;
	}
	//K=min(K,P.second);
	lef=0;rig=a*a+4;
	long long EF=0,KL;
	while(1){
		if(lef+1>=rig) break;
		mid=(lef+rig)/2;
		P=fun();
		if(P.second<=K){
			pas=min(pas,P.first-mid*P.second);
			rig=mid;KL=P.first-mid*K;EF=P.second;
		}else{
			lef=mid;
		}
	}
	if(EF<K){
		return KL;
	}
	return pas;
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:146:17: warning: 'KL' may be used uninitialized in this function [-Wmaybe-uninitialized]
  146 |  long long EF=0,KL;
      |                 ^~

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