Submission #1085921

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085921		DennisYbruh	Aliens (IOI16_aliens)	C++17	12 / 100	1 ms	444 KiB

aliens

/*
Click here to see my github page:
https://tinyurl.com/4jmutjr2

^^^^^^^^^^^^^^^^^^^^^^^^^^^^

yo wut da derek shakk doin'
⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣤⣴⣤⣤⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⣰⣾⣿⣿⣿⣿⣿⣿⣿⣿⣆⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢠⡿⠋⠉⠉⠛⠛⠛⠋⠉⠙⢿⡆⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⣼⠇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⣧⠀⠀⠀⠀⠀⠀
⡰⠉⠉⠁⠉⡙⠹⢠⢾⣛⠛⢶⢀⡶⠛⣛⠳⡄⡏⢋⠉⠉⠉⠉⢢
⢹⠶⠶⠶⣾⠡⣾⠈⠸⡿⠷⠀⠀⠀⢾⣿⠇⠁⡶⡌⢷⠶⠶⠶⡏
⢸⠀⠀⠀⠆⠀⢻⡀⠀⠀⡀⠀⠀⠀⢀⢀⡀⠀⡟⠀⠸⡀⠀⠀⡇
⢸⠀⠀⢸⠀⠀⠈⡇⣠⠒⠓⠤⣀⠤⠘⠀⡘⢰⠃⠀⠀⡇⠀⠀⡇
⢸⠀⠀⡎⠀⠀⠀⢻⠀⠙⣶⣶⣒⣶⣶⠋⢀⡏⠀⠀⠀⢸⠀⠀⡇
⢸⠀⠀⡇⠀⠀⠀⠘⣧⡀⠈⠿⣿⡿⠁⢀⢮⠃⠀⠀⠀⢸⠀⠀⡇
⢸⠀⠀⡇⠀⠀⠀⠀⢰⠑⠄⣀⠀⢀⡠⠊⡌⠀⠀⠀⠀⢸⠀⠀⡇
⢸⠀⠀⠘⢄⠀⠀⠀⠀⠆⠀⠀⠀⠀⠀⠰⠀⠀⠀⠀⡠⠃⠀⠀⡇
⠈⠦⣀⣔⠂⠋⠒⠲⠶⠾⠤⠤⠤⠤⠤⠷⠶⠖⠒⠉⠒⢢⣀⠴⠃
⠀⠀⠀⠅⠉⠉⠉⠉⠉⠒⠒⠒⠒⠒⠒⠊⠉⠉⠉⠉⠉⠨⡀⠀⠀
⠀⠀⠀⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⠁⠀⠀
⠀⠀⠀⠳⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡜⠀⠀⠀
⠀⠀⠀⠀⠱⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⠎⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠈⠢⢄⣀⡀⢀⠀⡀⢀⠀⣀⣀⡠⠔⠁⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠀⡌⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢀⡇⠀⠀⠀⠀⠀⠀⠀⠀⠀⠸⡀⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⡇⠀⠀⠀⠀⠀⠀
⠀⠀⠀⠀⠀⠀⠸⠤⠠⠀⢀⣀⣀⣀⠀⠀⠤⠤⠖⠀⠀⠀

WWWWWWWWWWWWWWWWWWWWWWWWWWWW'S
IN DA CHAT

WE DA SKIBIDI SIGMAS FROM O'BLOCK
*/ 

#include <bits/stdc++.h>
 
using namespace std;
using namespace std::chrono;
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...) 
#endif

int setbit(int x) {return __builtin_popcount(x);}
int setbit(long long x) {return __builtin_popcountll(x);}
int highbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int highbit(long long x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(long long x) {return (x==0?-1:__builtin_ctzll(x));}
#define ll long long
#define int ll
#define inf (int)1e9 + 5
#define inf_long_long 9223372036854775807/4
#define endl "\n"
#define mod 1000000007
#define fastinput ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define umap unordered_map
#define pii pair<int,int>
#define ppiii pair<pii, int>
#define pipii pair<int, pii>
#define sz(x) ((int) x.size())
#define forn(i,a,b) for(int i=a;i<=b;i++)
#define for0(i,a,b) for(int i=a;i>=b;i--)
#define all(x) x.begin(), x.end()
typedef tuple<int,int,int> tiii;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
vector<int> factorials;
vector<int> invf;
int bpm(int a, int b) {if (b==0) {return 1;} int ret = bpm(a, b/2); ret = (1LL * ret * ret) % mod; if (b%2==1) {ret = (1LL * ret * a) % mod;} return ret;}
int gcd(int a, int b) {if (a==0) {return b;} if (b==0) {return a;}return gcd(b%a, a);}
int lcm(int a, int b) {return a/gcd(a,b)*b;}
int inv(int a) {return bpm(a, mod-2);}
void calcfacmod(int n) {factorials.resize(n+1);factorials[0] = 1;for (int i = 1; i <= n; i++) {factorials[i] = factorials[i-1]*i;factorials[i]%=mod;}}
mt19937_64 rngg(chrono::steady_clock::now().time_since_epoch().count());
int RNG() {return rngg()%inf_long_long;}
void calcfac(int n) {calcfacmod(n);}

template<typename T>
void modpos(T &a) {T amt = (-a)/mod;amt++; amt = max(T(0), amt); a += amt*mod; a%=mod;}

int chs(int a, int b) {if (a<b || b < 0) {return 0;}if (b==a || b==0) {return 1;}return (((factorials[a]*invf[b])%mod)*invf[a-b])%mod;}
void calcinvfac(int n) {invf.resize(n);for (int i = 0; i < n; i++) {invf[i] = inv(factorials[i]);}}
// int paths(int a, int b) {return choose(a+b, a);}
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// using namespace std;
// template<typename T> 
// using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; // remove #define int ll before use


vector<pii> rg;
vector<int> ovlp;
int n, k;
vector<int> dp;

#define double long double

double df = 1e-12;
int cst = -1;

int xv(int x) {
	return rg[x + 1].first;
}

int yv(int x) {
	return dp[x] + xv(x) * xv(x) - ovlp[x] + cst;
}

double slope(int a, int b) {
	return (1.0 * yv(a) - yv(b)) / (1.0 * xv(a) - xv(b));
}


int calc() {
	dp.clear();
	dp.resize(n + 1, 0);
	vector<int> usd(n + 1, 0);
	int l = 0;
	int r = 0;
	vector<int> cht(1, 0);
	for (int i = 1; i <= n; i++) {
		while (l < r && 2.0 * rg[i].second >= slope(cht[l + 1], cht[l]) + df) {
			l ++;
		}
		int bst = cht[l];
		dp[i] = dp[bst] + (rg[i].second - xv(bst)) * (rg[i].second - xv(bst)) - ovlp[bst] + cst;
		usd[i] = usd[bst] + 1;
		while (l < r && slope(i, cht[r]) <= slope(cht[r], cht[r - 1]) + df) {
			cht.pop_back();
			r--;
		}
		cht.pb(i);
		r++;
	}
	return usd[n];
}

ll take_photos(signed N, signed M, signed K, vector<signed> L, vector<signed> R) {
	n = N;
	k = K;
	rg.resize(n);
	ovlp.resize(n, 0);
	for (int i = 0; i < n; i++) {
		// cin >> rg[i].first >> rg[i].second;
		// if (rg[i].second < rg[i].first) {
		// 	swap(rg[i].first, rg[i].second);
		// }
		// rg[i].second *= -1;
		rg[i] = {L[i], R[i]};
		if (rg[i].second < rg[i].first) {
			swap(rg[i].first, rg[i].second);
		}
		rg[i].second *= -1;
	}
	sort(all(rg));
	for (auto &[a, b] : rg) {
		b*=-1;
	}
	vector<pii> tmp(1, {-1, -1});
	int lstr = -inf;
	for (auto [l, r] : rg) {
		if (r > lstr) {
			tmp.pb({l, r});
			lstr = r;
		}
	}
	swap(rg, tmp);
	n = sz(rg) - 1;
	for (int i = 1; i < n; i++) {
		if (rg[i].second > rg[i + 1].first) {
			ovlp[i] = (rg[i].second - rg[i + 1].first + 1) * (rg[i].second - rg[i + 1].first + 1);
		}
	}
	for (int i = 1; i <= n; i++) {
		rg[i].second++;
	}
	// debug(rg);
	int l = 0;
	int r = (int)1e18;
	int as = -1;
	while (l <= r) {
		int md = (l + r) / 2;
		cst = md;
		if (calc() > k) {
			l = md + 1;
		} else {
			as = md;
			r = md - 1;
		}
	}
	cst = as;
	calc();
	// cout << dp[n] - k * as << endl;
	return dp[n] - k * as;
}

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