Submission #545289

#	Time	Username	Problem	Language	Result	Execution time	Memory
545289		pure_mem	Aliens (IOI16_aliens)	C++14	0 / 100	3 ms	340 KiB

aliens

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

#define X first
#define Y second
#define MP make_pair

typedef long long ll;
typedef std::pair<ll, ll> Line;

const ll INF = 1e17;
const int N = 1e5 + 1;

using namespace std;

int n;
vector< Line > a;
Line lines[N];
Line dp[N];

ll divide(ll a, ll b) {
	int delta = 0;
	if(a % b != 0)
		delta = 1;
	if((a > 0 && b > 0) || (a < 0 && b < 0))	
		return a / b + delta;
	return -abs(a) / abs(b);
}

ll intersect(int a, int b) {
	if(lines[a].X == lines[b].X)
		return INF;
	return divide(lines[a].Y - lines[b].Y, lines[b].X - lines[a].X);
}

ll apply(int a, ll x) {
	return lines[a].X * x + lines[a].Y;
}

void insert(deque<int> &cht, int& ptr, int i) {
	while(1) {
		if(cht.empty()) {
			cht.push_back(i);
			break;
		}
		
		int v = cht.end()[-1];
		if(intersect(v, i) == INF) {
			if(lines[v].Y <= lines[i].Y)
				break;
			cht.pop_back();
			if(!cht.empty())
				continue;
		}
		else {
			if(cht.size() > 1) {
				int u = cht.end()[-2];
				if(intersect(v, i) < intersect(u, v)) {
					cht.pop_back();
					continue;
				}
			}
		}
		cht.push_back(i);
		break;
	}
	ptr = min(ptr, (int)cht.size());		
}

int get(const deque< int > &cht, int &ptr, ll x) {
	if(cht.empty()) 
		return -1;
	while(ptr < cht.size()) {
		ll v = apply(cht[ptr - 1], x);
		ll u = apply(cht[ptr], x);
		if(v > u || (v == u && dp[cht[ptr - 1]].Y > dp[cht[ptr]].Y))
			ptr++;
		else
			break;
	}

	return cht[ptr - 1];
}

Line check(ll lambda) {
	static int debug = 0;
	
	for(int i = 0;i <= a.size();i++)
		dp[i] = MP(4e18, 4e18);
	dp[0] = MP(0, 0); 	

	deque< int > larger, smaller;
	int larger_it = 1;
	int smaller_it = 1;

	for(int i = 0;i < a.size();i++) {	
		ll l = a[i].X, r = a[i].Y;
		
		lines[i] = {-2 * r, 2 * r + 1 + r * r + dp[i].X};
		insert(larger, larger_it, i);
		while(!larger.empty()) {
			int v = larger.front();
			if(a[v].Y >= l)
				break;
			lines[v] = {-2 * a[v].X, -2 * a[v].X + 1 + a[v].X * a[v].X + dp[v].X};
			insert(smaller, smaller_it, v);
			larger.pop_front();	
		}
		
		int pos = get(larger, larger_it, l);
		if(pos != -1) {
		//	cerr << i + 1 << " " << pos << " " << dp[pos].Y << "d\n";
			dp[i + 1] = min(dp[i + 1], MP(apply(pos, l) + l * l - 2 * l + lambda, dp[pos].Y + 1));
		}
		pos = get(smaller, smaller_it, r);
		if(pos != -1) {
		//	cerr << i + 1 << " " << pos << "d\n";
			if(debug == 2) {
				cerr << pos << " " << i + 1 << " " << smaller.size() << "\n";
			}
			dp[i + 1] = min(dp[i + 1], MP(apply(pos, r) + r * r + 2 * r + lambda, dp[pos].Y + 1));
		} 
	}

	if(debug == 2) {
		for(int i = 0;i <= a.size();i++) {
			cerr << dp[i].X << " " << dp[i].Y << "z\n";
		}
	}

	return dp[a.size()];
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    {
    	set<int> st;
    	vector< Line > good;

		for(int i = 0;i < n;i++) 
        	a.push_back(MP(min(r[i], c[i]), max(r[i], c[i])));
    	sort(a.begin(), a.end(), 
    		[](pair<int, int> l, pair<int, int> r) {
    			if(l.X != r.X)
    				return l.X < r.X;
    			return l.Y > r.Y;
    		}
    	);                     
    	
    	for(pair<int, int> i: a) {
    		while(!st.empty() && *st.begin() < i.X)
    			st.erase(st.begin());
    		if(st.empty() || *st.rbegin() < i.Y) {
    			st.insert(i.Y);
    			good.push_back(i);	
    			//cerr << i.X << " " << i.Y << "\n";
    		}
    	}
    	a.swap(good);
    }
    k = min(k, (int)a.size());
    ll tl = -INF, tr = INF, res = -INF - 1;
    while(tl <= tr) {
    	ll m = (tl + tr) / 2;
   		Line mid = check(m);
   		//cerr << mid.X << " " << mid.Y << " " << tl << " " << tr << "\n";
   		if(mid.Y > k) {
   			tl = m + 1;
   			res = m;
   		}
   		else {
   			tr = m - 1;
   		}
    } res++;
    //cerr << check(2).Y << "\n";
    Line mid = check(res);
    ll answer = mid.X - k * res;
    
    return answer;
}

Compilation message (stderr)

aliens.cpp: In function 'int get(const std::deque<int>&, int&, ll)':
aliens.cpp:73:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  while(ptr < cht.size()) {
      |        ~~~~^~~~~~~~~~~~
aliens.cpp: In function 'Line check(ll)':
aliens.cpp:88:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |  for(int i = 0;i <= a.size();i++)
      |                ~~^~~~~~~~~~~
aliens.cpp:96:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 0;i < a.size();i++) {
      |                ~~^~~~~~~~~~
aliens.cpp:126:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |   for(int i = 0;i <= a.size();i++) {
      |                 ~~^~~~~~~~~~~

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