Submission #545380

#	Time	Username	Problem	Language	Result	Execution time	Memory
545380		pure_mem	Aliens (IOI16_aliens)	C++14	100 / 100	266 ms	12556 KiB

aliens

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

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

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];

ld intersect(int a, int b) {
	if(lines[a].X == lines[b].X)
		return INF;
	return (lines[a].Y - lines[b].Y) * 1.0 / (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()) {
		if(intersect(cht[ptr - 1], cht[ptr]) <= x)
			ptr++;
		else
			break;
	}
	return cht[ptr - 1];
}

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

	deque< int > larger;
	int larger_it = 1;

	for(int i = 0;i < a.size();i++) {	
		ll l = a[i].X, r = a[i].Y;
		lines[i] = {-2 * (l - 1), (l - 1) * (l - 1) + dp[i].X};
		if(i && a[i - 1].Y >= a[i].X) {
			lines[i].Y -= (a[i - 1].Y - a[i].X + 1) * (a[i - 1].Y - a[i].X + 1);
		}

		insert(larger, larger_it, i);
		int pos = get(larger, larger_it, r);
		
		assert(pos != -1);
		dp[i + 1] = {apply(pos, r) + r * r + lambda, dp[pos].Y + 1};
	}

	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]) + 1, max(r[i], c[i]) + 1));
    	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);	
    		}
    	}
    	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;
   		}
    } 

    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:65:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |  while(ptr < cht.size()) {
      |        ~~~~^~~~~~~~~~~~
aliens.cpp: In function 'Line check(ll)':
aliens.cpp:75: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]
   75 |  for(int i = 0;i <= a.size();i++)
      |                ~~^~~~~~~~~~~
aliens.cpp:82: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]
   82 |  for(int i = 0;i < a.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