| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 711955 | SA01 | Aliens (IOI16_aliens) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt")
using ll = long long int;
using ull = unsigned long long int;
using vi = vector<ll>;
using ii = pair<ll,ll>;
using vii = vector<ii>;
using ld = long double;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T>
using ordered_set = tree < T, null_type, less<T>,
rb_tree_tag,
tree_order_statistics_node_update >;
#ifdef SA_DEBUG
template <class T>
void print(T a) {cerr << a << endl;}
template <class T, class... V>
void print(T a, V... b) {cerr << a << ", "; print(b...);}
#define dbg(...) cerr << "[" << __LINE__ << "] " << #__VA_ARGS__ << " :: ", print(__VA_ARGS__)
#else
#define dbg(...) 7
#endif
#define eb emplace_back
#define fi first
#define se second
const ll INFL = 1e18;
const int INF = 1e9;
const double PI = acos(-1);
const ll mod = 1e9+7;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T, class V>
ostream& operator << (ostream &s, pair<T, V> a){
s << a.fi << ' ' << a.se; return s;
}
template<class T, class V>
istream& operator >> (istream &s, pair<T, V> &a){
s >> a.fi >> a.se; return s;
}
template<class T>
ostream& operator << (ostream &s, vector<T> a){
for(int i = 0; i < (int)a.size(); i++){
if(i > 0)s << ' ' ;
s << a[i];
} return s;
}
template<class T>
istream& operator >> (istream &s, vector<T> &a){
for(T &x : a)s >> x;
return s;
}
template<class T>
void input(T a[], int l, int r, istream &s = cin){
while(l <= r)s >> a[l++];
}
template<class T>
void output(T a[], int l, int r, bool en = true, ostream &s = cout){
while(l <= r){ s << a[l++];
if(l <= r) s << ' ';
} if(en)s << "\n";
}
const int N = 4e5+3, K = 17, M = 2e5 + 5;
//====================================================================//
void testcase(){
int n, m, k;
cin >> n >> m >> k;
vector<ii> v(n);
for(auto &[l,r] : v){
cin >> l >> r;
if(l > r)swap(l, r);
r = -r;
}
sort(v.begin(), v.end());
vector<ii> V(1, ii(-1, -1));
for(auto [l, r]:v){
r = -r;
if(V.back().se < r){
V.eb(l, r);
}
}
n = V.size();
auto cost = [&](int i, int j){
ll cst = V[j].se - V[i].fi + 1;
cst = cst * cst;
if(i > 0 && V[i - 1].se >= V[i].fi){
ll temp = (V[i - 1].se - V[i].fi + 1);
cst -= temp * temp;
}
return cst;
};
//dbg(V);
auto solve = [&](ll extra){
deque<ii> opt(1, ii(0, 1));
vi dp(n);
vector<int> cnt(n);
auto getVal = [&](int i, int j){
return dp[i] + cost(i + 1, j);
};
auto cmp = [&](int i, int j, int l){
return getVal(i, l) >= getVal(j, l);
};
for(int i = 1; i < n; i++){
dp[i] = getVal(opt[0].fi, i) + extra;
cnt[i] = cnt[opt[0].fi] + 1;
opt[0].se++;
while(opt.size() > 1 && opt[0].se >= opt[1].se)opt.pop_front();
while(!opt.empty() && cmp(opt.back().fi, i, opt.back().se))
opt.pop_back();
if(opt.empty()){
opt.eb(i, i + 1);
continue;
}
int lo = opt.back().se + 1, hi = n - 1;
while(lo < hi){
int mid = (lo + hi + 1) / 2;
if(cmp(opt.back().fi, i, mid))lo = mid;
else hi = mid - 1;
}
if(cmp(opt.back().fi, i, lo))opt.eb(i, lo);
}
return ii(dp[n - 1], cnt[n - 1]);
};
ll lo = 0, hi = 1e9;
while(lo < hi){
ll mid = (lo + hi) >> 1;
if(solve(mid).se > k)lo = mid + 1;
else hi = mid;
}
//dbg(lo, solve(lo));
cout << solve(lo).fi - k * lo << "\n";
}
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL);
int T = 1;
//cin >> T;
for(int qq = 1; qq <= T; ++qq){
//cout << "Case #" << qq << ": ";
testcase();
}
return 0;
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
2 6 2
1 4
4 1
*/