Submission #69381

#	Time	Username	Problem	Language	Result	Execution time	Memory
69381		Navick	Aliens (IOI16_aliens)	C++17	4 / 100	4 ms	724 KiB

aliens

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

#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pld pair<pair<ld, ll>, int>

using namespace std;

typedef long long ll;
typedef long long ld;

const int maxN = 1e5 + 10, maxK = 510;
const ll oo = 2e15;

ld dp[maxN];
ll f[maxN];
int n, l[maxN], r[maxN], par[maxN], ted[maxN];

vector <pii> que;
pld lines[maxN];

bool cmp(pii a1, pii a2)
{
	if(a1.F != a2.F) return a1.F < a2.F;
	return a1.S > a2.S;
}

ld barkhord(pld A, pld B)
{
	return (ld)(B.F.F - A.F.F + A.F.S - B.F.S - 1) / (ld)(A.F.S - B.F.S);
}

ll check(ld c, bool g = 0)
{
	int sz = 0, ptr = 0;
	ted[0] = 0, par[0] = -1;

	for (int i=1; i<=n; i++)
	{
		ll x = 0;
		if(i - 1 > 0) x = f[i - 2];
		pld t = {{dp[i - 1] + (ll)l[i - 1] * l[i - 1] - x, -2LL * l[i - 1]}, i - 1};
		while(sz >= 2 && barkhord(lines[sz - 2], lines[sz - 1]) >= barkhord(lines[sz - 1], t)) sz --;
		lines[sz ++] = t;

		ptr = min(ptr, sz - 1);
		while(ptr + 1 < sz && barkhord(lines[ptr], lines[ptr + 1]) <= r[i - 1]) ptr++;
		
		//cout << i << " ))))) " << " << " << r[i - 1] << lines[ptr].F.F << ',' << lines[ptr].F.S << endl;

		dp[i] = (ld)r[i - 1] * r[i - 1] + lines[ptr].F.F + lines[ptr].F.S * r[i - 1] + c;

		int _par = lines[ptr].S;
		par[i] = _par;
		ted[i] = 1 + ted[_par];

	 	//if(g) cout << i << ',' << dp[i] << " : " << par[i] << ',' << ted[i] << endl;
	}

	if(g)
	{
		ll res = 0;

		int curr = n;
		while(curr > 0)
		{
			//cout << curr << ' ';
			int p = par[curr];
			res += 1LL * (r[curr - 1] - l[p]) * (r[curr - 1] - l[p]);
			if(p) res -= f[p - 1];
			curr = p;
		}
		//cout << endl;

		//cout << ted[n] << endl;

		return res;

	}
	//cout << c << " ----> " << ted[n] << endl;

	return ted[n];

}

long long take_photos(int NN, int m, int k, std::vector<int> R, std::vector<int> c) {
    
	n = NN;

	if(n > maxN) return cout << 1/0 << endl, -1;

	for (int i=0; i<n; i++)
	{
		if(R[i] <= c[i])
			c[i] ++;
		else R[i] ++;
		que.pb({min(R[i], c[i]), max(R[i], c[i])});
	}

	sort(que.begin(), que.end(), cmp);

	int mx = -1, cnt = 0;

	for (int i=0; i<n; i++)
	{
		if(mx >= que[i].S) continue ;
		else 
		{
			l[cnt] = que[i].F, r[cnt] = que[i].S;
			mx = max(mx, que[i].S);
			cnt ++;
		}
	}

	n = cnt;

	//for (int i=0; i<n; i++) cout << l[i] << ',' << r[i] << endl; cout << endl;

	ll lo = 0, hi = 2e12;
	
	for (int i=0; i<n-1; i++)
		if(r[i] > l[i + 1]) f[i] = 1LL * (r[i] - l[i + 1]) * (r[i] - l[i + 1]);
	
	while(hi - lo > 1)
	{
		ll mid = (lo + hi)/2;
		if(check(mid) >= k) lo = mid;
		else hi = mid;
	}

	/*
	for (int i=0; i<300; i++)
	{
		ld mid = (lo + hi)/2;
		if(check(mid) >= k) lo = mid;
		else hi = mid;
	}*/

	//check(0, 1);
	
	//cout << lo << endl;

	return check(lo, 1);
}

Compilation message (stderr)

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:93:31: warning: division by zero [-Wdiv-by-zero]
  if(n > maxN) return cout << 1/0 << endl, -1;
                              ~^~

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