Submission #173410

#	Time	Username	Problem	Language	Result	Execution time	Memory
173410		dndhk	Aliens (IOI16_aliens)	C++14	100 / 100	180 ms	9716 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 = 1e12;
const int MAX_N = 100000;

int N, M, K;
vector<pii> vt;
vector<ll> C;
ll dp[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;*/

struct S{
	ll a, b;
	int idx;
};

vector<S> st;
int idx = 0;

void add(ll a, ll b, int i){
	while(st.size()>=2){
		S prv = st.back(); st.pop_back();
		if((b-prv.b) * (prv.a - st.back().a) >= (a-prv.a) * (prv.b - st.back().b)){
			if(idx==st.size())	idx--;
			continue;
		}else{
			st.pb(prv);
			break;
		}
	}
	st.pb({a, b, i});
}
int cnt[MAX_N+1];

ll calc(ll x, int i){
	while(idx+1<st.size()){
		if(st[idx+1].a * x + st[idx+1].b < st[idx].a * x + st[idx].b) idx++;
		else	break;
	}
	cnt[i] = cnt[st[idx].idx]+1;
	return st[idx].a * x + st[idx].b;
}

int solve(ll x){
	//TEST cout<<x<<endl;
	st.clear();
	idx = 0;
	for(int i=0; i<vt.size(); i++){
		//TEST cout<<dp[i]<<" ";
		add(-4LL * (ll)vt[i].first, dp[i] - 2LL * C[i] + 2LL * (ll)vt[i].first * (ll)vt[i].first, i);
		dp[i+1] = 2LL * (ll)vt[i].second * (ll)vt[i].second + calc((ll)vt[i].second, i+1) + x;
	}//TEST cout<<dp[vt.size()]<<endl<<cnt[vt.size()]<<endl<<dp[vt.size()] - (ll)cnt[vt.size()] * x<<endl<<endl;
	return cnt[vt.size()];
}

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();
	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)));
	}
	ll s = 0, e = (ll)M*(ll)M, mid;
	while(s<e){
		mid = (s+e)/2LL;
		int t = solve(2LL*mid+1LL);
		if(t<=K){
			e = mid;
		}else{
			s = mid+1LL;
		}
	}
	solve(2LL*s);
	return (dp[vt.size()] - 2LL * s * (ll)K)/2LL;
}

Compilation message (stderr)

aliens.cpp: In function 'void add(ll, ll, int)':
aliens.cpp:106:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if(idx==st.size()) idx--;
       ~~~^~~~~~~~~~~
aliens.cpp: In function 'll calc(ll, int)':
aliens.cpp:118:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx+1<st.size()){
        ~~~~~^~~~~~~~~~
aliens.cpp: In function 'int solve(ll)':
aliens.cpp:130: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:154:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vt.size(); i++){
               ~^~~~~~~~~~

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