Submission #165896

#	Time	Username	Problem	Language	Result	Execution time	Memory
165896		Segtree	Aliens (IOI16_aliens)	C++14	60 / 100	228 ms	14824 KiB

aliens

#include<iostream>
#include<algorithm>
#include<vector>
#include"aliens.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 50010
vector<ll> l,r;
ll Tei(int i){
    ll tei=l[i]*l[i];
    tei-=max(0LL,r[i]-l[i])*max(0LL,r[i]-l[i]);
    return tei;
}

namespace cht{
    struct line{
	ll a,b;
	line(ll a,ll b){
	    this->a=a,this->b=b;
	}
	ll f(ll x){
	    return a*x+b;
	}
    };
    long double crox(line a,line b){
	return (long double)(b.b-a.b)/(long double)(a.a-b.a);
    }
    ll p;
    vector<line> v;
    void add(ll a,ll b){
	if(b>=1e17)return;
	line c=line(a,b);
	while(v.size()>=2){
	    if(crox(v[v.size()-2],v[v.size()-1])>crox(v[v.size()-1],c)){
		v.pop_back();
		chmin(p,(ll)v.size()-1);
	    }
	    else break;
	}
	v.push_back(c);
    }
    ll qry(ll x){
	if(v.size()==0)return 1e17;
	while(p+1<v.size()){
	    if(crox(v[p],v[p+1])<(long double)x)p++;
	    else break;
	}
	return v[p].f(x);
	/*ll ans=1e17;
	for(auto t:v)chmin(ans,t.f(x));
	return ans;*/
    }
    void init(){
	v.clear();
	p=0;
    }
};

ll dp[N],cop[N];
ll take_photos(int n,int m,int K,vector<int> R,vector<int> C){
    vector<P> v;
    for(int i=0;i<n;i++){
	if(R[i]>C[i])swap(R[i],C[i]);
	v.push_back(make_pair((ll)R[i],(ll)-C[i]));
    }
    sort(v.begin(),v.end());
    ll rnd=-1;
    r.push_back(-1);
    for(auto p:v){
	ll x=p.first,y=-p.second+1;
	if(y<=rnd)continue;
	rnd=y;
	l.push_back(x);
	r.push_back(y);
    } 
    n=l.size();
    if(n==1)return (r[1]-l[0])*(r[1]-l[0]);
    for(int i=0;i<=n;i++)dp[i]=1e17;
    dp[0]=Tei(0);
    
    ll ans=1e17;
    for(int k=1;k<=K;k++){
	cht::init();
	for(int i=0;i<=n;i++)cop[i]=1e17;
	for(int i=1;i<=n;i++){
	    cht::add(-2*l[i-1],dp[i-1]);
	    chmin(cop[i],cht::qry(r[i])+r[i]*r[i]);
	    /*for(int j=0;j<i;j++){
		chmin(dp[i][k],dp[j][k-1]-2*r[i]*l[j]+r[i]*r[i]);
	    }*/
	    if(i==n)chmin(ans,cop[i]);
	    cop[i]+=Tei(i);
	    //cout<<i<<" "<<k<<" "<<dp[i][k]<<endl;
	}
	for(int i=0;i<=n;i++)dp[i]=cop[i];
    }
    return ans;
}

Compilation message (stderr)

aliens.cpp: In function 'll cht::qry(ll)':
aliens.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(p+1<v.size()){
        ~~~^~~~~~~~~

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