Submission #173268

#	Time	Username	Problem	Language	Result	Execution time	Memory
173268		dndhk	Aliens (IOI16_aliens)	C++14	25 / 100	2056 ms	49988 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

#define all(v) (v).begin(), (v).end()
#define sortv(v) sort(all(v))
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define pb push_back
#define FI first
#define SE second
#define lb lower_bound
#define ub upper_bound
#define mp make_pair
#define test 0
#define TEST if(test)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;

const int MOD = 1000000007; // 998244353
const int INF = 2e9;
const ll INFLL = 1e15;
const int MAX_N = 50000;

int N, M, K;
vector<pii> vt;
vector<ll> C;
ll dp[2][MAX_N+1];
bool sf(pii a, pii b){
	if(a.first==b.first){
		return a.second>b.second;
	}
	return a.first<b.first;
}

struct Lichao{
	struct NODE{
		int l, r;
		ll a, b;
	};
	ll SZ;
	vector<NODE> seg;
	void add(){
		seg.pb({-1, -1, 0, INFLL});
	}
	void Init(int x){
		SZ = (ll)x;
		add();
		init(0, 0LL, SZ);
	}
	void Reset(){
		for(int i=0; i<seg.size(); i++){
			seg[i].a = 0LL; seg[i].b = INFLL;
		}
	}
	void init(int idx, ll s, ll e){
		if(s==e)	return;
		seg[idx].l = seg.size(); add();
		seg[idx].r = seg.size(); add();
		init(seg[idx].l ,s, (s+e)/2); init(seg[idx].r, (s+e)/2+1, e);
	}
	void Update(ll a, ll b){
		update(0, 0LL, SZ, a, b);
	}
	void update(int idx, ll s, ll e, ll x, ll y){
		if(s*x+y<=seg[idx].a*s+seg[idx].b && e*x+y<=seg[idx].a*e+seg[idx].b){
			seg[idx].a = x;
			seg[idx].b = y;
			return;
		}else if(s*x+y>=seg[idx].a*s+seg[idx].b && e*x+y>=seg[idx].a*e+seg[idx].b){
			return;
		}
		update(seg[idx].l, s, (s+e)/2, x, y);
		update(seg[idx].r, (s+e)/2+1, e, x, y);
	}
	ll Calc(ll x){
		return calc(0, 0LL, SZ, x);
	}
	ll calc(int idx, ll s, ll e, ll k){
		if(s==e){
			return seg[idx].a * k + seg[idx].b;
		}
		if(k<=(s+e)/2){
			return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].l, s, (s+e)/2, k));
		}else{
			return min(seg[idx].a * k + seg[idx].b, calc(seg[idx].r, (s+e)/2+1, e, k));
		}
	}
}Seg;

void solve(){
	dp[1][0] = 0LL;
	Seg.Reset();
	for(int i=0; i<vt.size(); i++){
		Seg.Update(-2LL * vt[i].first, dp[0][i] - C[i] + (ll)vt[i].first * (ll)vt[i].first);
		dp[1][i+1] = (ll)vt[i].second * (ll)vt[i].second + Seg.Calc((ll)vt[i].second);
	}
}

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
	N = n; M = m; K = k;
	for(int i=0; i<N; i++){
		vt.pb({min(r[i], c[i]), max(r[i], c[i]) + 1});
	}
	sort(vt.begin(), vt.end(), sf);
	int mx = -1;
	for(int i=0 ;i<N; i++){
		if(mx>=vt[i].second){
			vt[i].second = INF;
			vt[i].first = INF;
		}else mx = max(mx, vt[i].second);
	}
	sort(vt.begin(), vt.end());
	while(!vt.empty() && vt.back().first==INF && vt.back().second==INF)	vt.pop_back();
	for(int i=0; i<=vt.size(); i++){
		dp[0][i] = dp[1][i] = INFLL;
	}
	C.pb(0LL);
	for(int i=1; i<vt.size(); i++){
		C.pb(max(0LL, (ll)(vt[i-1].second - vt[i].first)) * max(0LL, (ll)(vt[i-1].second - vt[i].first)));
	}
	dp[0][0] = dp[1][0] = 0LL;
	Seg.Init(M);
	while(K--){
		solve();
		for(int i=0; i<=vt.size(); i++){
			//TEST cout<<dp[1][i]<<" ";
			dp[0][i] = dp[1][i];
			dp[1][i] = INFLL;
		}
		//TEST cout<<endl;
	}
	return dp[0][vt.size()];
}

Compilation message (stderr)

aliens.cpp: In member function 'void Lichao::Reset()':
aliens.cpp:55:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<seg.size(); i++){
                ~^~~~~~~~~~~
aliens.cpp: In function 'void solve()':
aliens.cpp:97:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<vt.size(); i++){
               ~^~~~~~~~~~
aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:118:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<=vt.size(); i++){
               ~^~~~~~~~~~~
aliens.cpp:122:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vt.size(); i++){
               ~^~~~~~~~~~
aliens.cpp:129:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0; i<=vt.size(); i++){
                ~^~~~~~~~~~~

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