Submission #206592

#	Time	Username	Problem	Language	Result	Execution time	Memory
206592		TAISA_	Aliens (IOI16_aliens)	C++14	60 / 100	2090 ms	360152 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<60;
void chmin(ll &a,ll b){a=min(a,b);}
struct T{
	ll a,b;
};
struct CHT{
	int n;
	vector<T> dat;
	vector<ll> xs;
	CHT(vector<ll>& a){
		n=1;
		while(n<a.size())n<<=1;
		xs=a;
		int c=0;
		while(xs.size()<=n){
			xs.eb(10000000+c);
			c++;
		}
		dat.resize(2*n,T{0,INF});
	}
	inline ll f(T& a,ll x){
		return a.a*x+a.b;
	}
	void upd(T a,int k,int l,int r){
		int m=(l+r)/2;
		ll vl=f(dat[k],xs[l]),vr=f(dat[k],xs[r-1]),vl2=f(a,xs[l]),vr2=f(a,xs[r-1]);
		if(vl<=vl2&&vr<=vr2)return;
		if(vl2<=vl&&vr2<=vr){
			dat[k]=a;
			return;
		}
		if(r-l<=1)return;
		if(vl2<=vl)swap(dat[k],a);
		ll vm=f(dat[k],xs[m]),vm2=f(a,xs[m]);
		if(vm>vm2){
			swap(dat[k],a);
			upd(a,k<<1,l,m);
		}else{
			upd(a,k<<1|1,m,r);
		}
	}
	inline void upd(T a){upd(a,1,0,n);}
	ll get(ll x){
		int k=lower_bound(all(xs),x)-xs.begin();
		k+=n;
		ll res=f(dat[k],x);
		k>>=1;
		while(k>0){
			chmin(res,f(dat[k],x));
			k>>=1;
		}
		return res;
	}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	vector<int> cs(m,-1);
	for(int i=0;i<n;i++){
		if(r[i]>c[i]){
			swap(r[i],c[i]);
		}
		cs[r[i]]=max(cs[r[i]],c[i]);
	}
	vector<ll> a,b,bs;
	int ma=-1;
	for(int i=0;i<m;i++){
		if(cs[i]>ma){
			a.eb(i-1);
			b.eb(cs[i]);
			bs.eb(cs[i]);
			ma=cs[i];
		}
	}
	sort(all(bs));
	bs.erase(unique(all(bs)),bs.end());
	n=a.size();
	vector<vector<ll>> dp(k+1,vector<ll>(n+1,INF));
	dp[0][0]=0;
	for(int i=0;i<k;i++){
		CHT cht(bs);
		for(int j=0;j<n;j++){
			ll t=dp[i][j]+a[j]*a[j];
			if(j>0&&b[j-1]>=a[j]+1){
				t-=(b[j-1]-a[j])*(b[j-1]-a[j]);
			}
			cht.upd(T{-2LL*a[j],t});
			dp[i+1][j+1]=cht.get(b[j])+b[j]*b[j];
			chmin(dp[i+1][j+1],dp[i][j+1]);
		}
	}
    return dp[k][n];
}

Compilation message (stderr)

aliens.cpp: In constructor 'CHT::CHT(std::vector<long long int>&)':
aliens.cpp:19:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(n<a.size())n<<=1;
         ~^~~~~~~~~
aliens.cpp:22:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(xs.size()<=n){
         ~~~~~~~~~^~~

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