Submission #1214369

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214369		thdh__	Aliens (IOI16_aliens)	C++20	0 / 100	1 ms	328 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define fi first
#define se second
#define all(a) a.begin(),a.end()
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define fu(x,a,b) for (auto x=a;x<=b;x++)
#define fd(x,a,b) for (auto x=a;x>=b;x--)

using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

/*
Competitive Programming notes that I need to study & fix my dumbass self:

1. Coding:
- Always be sure to check the memory of arrays (maybe use vectors), for loops, I don't know
- Always try to maximize the memory if possible, even if you are going for subtasks
- Do not exploit #define int long long, it will kill you

2. Stress:
- Don't be cocky and think stressing with your dumbass brute-force solution will give you guaranteed AC. 
- Always try generating big testcases and try if they run

3. Time management:
- Don't overcommit or undercommit, always spend a certain amount of time to think a problem, don't just look at it and say I'm fucked
- Do not spend too much time coding brute-force solutions, they should be easily-codable solutions that don't take up too much time

I hate offline because I am dumb
*/

typedef pair<ll, ll> ii;
const int N = 2e5+5;
const int mod = 1e9+7;
const ll inf = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

struct Line {
    ll m, b;
    ll x; 
    ll cnt; 
};

struct CHT {
    deque<Line> dq;

    static ll divCeil(ll a, ll b) {
        if (a >= 0)   return (a + b - 1) / b;
        else          return  a / b;
    }

    static ll intersect(const Line &l1, const Line &l2) {
        return divCeil(l2.b - l1.b, l1.m - l2.m);
    }
    void addLine(ll m, ll b, ll cnt) {
        Line nw{m, b, 0, cnt};
        while (!dq.empty()) {
            nw.x = intersect(dq.back(), nw);
            if (nw.x <= dq.back().x) dq.pop_back();
            else break;
        }
        if (dq.empty()) {
            nw.x = LLONG_MIN;
        }
        dq.push_back(nw);
    }

    pair<ll,ll> query(ll x) {
        while (dq.size() >= 2 && dq[1].x <= x) {
            dq.pop_front();
        }
        auto &L = dq.front();
        return {L.m * x + L.b, L.cnt};
    }
};

bool cmp(ii x, ii y) 
{
	return x.fi == y.fi ? x.se > y.se : x.fi < y.fi;
}

vector<ll> l,r;

ii calc(ll lb) 
{
	ll n = l.size()-1;
	vector<ii> dp(n+1, {0, 0});
	CHT cht;
	for (ll i = 1; i <= n; i++) 
	{
		// cout<<2 * (l[i]-1)<<" "<<dp[i-1].fi + (l[i]-1) * (l[i]-1) - max(0ll, r[i-1] - (l[i]-1)) * max(0ll, r[i-1] - (l[i]-1))<<endl;
		cht.addLine(2 * (l[i]-1), dp[i-1].fi + (l[i]-1) * (l[i]-1) - max(0ll, r[i-1] - (l[i]-1)) * max(0ll, r[i-1] - (l[i]-1)), dp[i-1].se);
		ii tmp = cht.query(-r[i]);
		// cout<<tmp.fi<<endl;
		dp[i].fi = tmp.fi + r[i] * r[i] + lb;
		dp[i].se = tmp.se + 1;
	}
	// cout<<dp[n].fi - lb<<" "<<dp[n].se<<endl;
	return dp[n];
}

ll take_photos(int n, int m, int k, vector<int> rr, vector<int> cc)  
{
	l.clear(); r.clear();
	vector<ii> a;
	for (ll i = 0; i < n; i++) a.pb({min(rr[i], cc[i]), max(rr[i], cc[i])});
	sort(all(a), cmp);
	// for (auto i : a) cout<<i.fi<<" "<<i.se<<endl;
	ll mx = 0;
	l.pb(-1), r.pb(-1);
	for (ll i = 0; i < n; i++) 
	{
		if (mx >= a[i].se) continue;
		mx = max(mx, a[i].se);
		l.pb(a[i].fi), r.pb(a[i].se);
	}
	// for (int i = 0; i < l.size(); i++) cout<<l[i]<<" "<<r[i]<<endl;
	ll lo = 0, hi = 1LL * m * m;
	while (lo < hi) {
		ll mid = lo + (hi - lo)/2;
		if (calc(mid).second <= k)
		hi = mid;
		else
		lo = mid + 1;
	}
	auto [dp_sum, cnt] = calc(lo);
  	return dp_sum - lo * 1LL * k;
}

void solve()
{
	int n,m,k;
	cin>>n>>m>>k;
	vector<int> rr(n), cc(n);
	for (int i = 0; i < n; i++) cin>>rr[i];
	for (int i = 0; i < n; i++) cin>>cc[i];
	cout<<take_photos(n,m,k,rr,cc);
}

/*
Go through the mistakes you usually make and revise your code, for god's sake...
*/

// signed main()
// {
// 	bruh
// 	//freopen("input.inp","r",stdin);
// 	//freopen("output.inp","w",stdout);
// 	int t = 1;
// 	// cin>>t;
// 	while (t--)
// 	{
// 		solve();
// 		cout<<"\n";
// 	}
// }

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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