| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 484659 | melon940925 | 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 "aliens.h"
#include<bits/stdc++.h>
#define pii pair<ll,ll>
#define x first
#define y second
using namespace std;
typedef long long ll;
pii aliens[500001];
ll dp[500001];
ll Q[500001];
ll candidates[500001];
ll numOfArea[500001];
ll front, rear;
ll N, K;
ll cost(ll a, ll b) {
ll mx = max(0LL, aliens[a].x - aliens[a + 1].y + 1);
return (aliens[b].x + 1 - aliens[a].y) * (aliens[b].x + 1 - aliens[a].y) - mx * mx;
}
ll func(ll i, ll j) {
return dp[i] + cost(i + 1, j);
}
ll cross(ll i, ll j) {
ll l = j + 1, r = N + 1;
while (l < r) {
int m = l + r >> 1;
if (func(i, m) <= func(j, m))l = m + 1;
else r = m;
}
return l - 1;
}
void monotoneQueueOpt(ll m) {
ll front = 0, rear = 1;
Q[0] = 0, candidates[0] = N;
for (ll i = 1; i <= N; ++i) {
while (candidates[front] < i)front++;
dp[i] = func(Q[front], i) + m;
numOfArea[i] = numOfArea[Q[front]] + 1;
while (front + 1 < rear && candidates[rear - 2] >= cross(Q[rear - 1], i))rear--;
candidates[rear - 1] = cross(Q[rear - 1], i), Q[rear] = i, candidates[rear++] = N;
}
}
ll bs(ll l, ll r) {
if (l >= r)return l;
ll m = l + r >> 1;
monotoneQueueOpt(m);
if (numOfArea[N] >= K)return bs(m + 1, r);
else return bs(l, m);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
//preprocess
N = n, K = k;
vector<pii> tmpAliens;
for (int i = 0; i < n; ++i) {
int x = r[i], y = c[i];
if (x < y)swap(x, y);
tmpAliens.push_back({ x,y });
}
sort(tmpAliens.begin(), tmpAliens.end(), [](const pii& a, const pii& b) {
if (a.y == b.y)return a.x > b.x;
return a.y < b.y;
});
pii prv = { -1,-1 };
int idx = 0;
for (auto& i : tmpAliens) {
if (prv.y == i.y || prv.x >= i.x)continue;
aliens[++idx] = prv = i;
}
N = idx;
//preprocess end
ll M = bs(0, 1e14);
monotoneQueueOpt(M);
//cout << "M: " << M << endl;
//cout << "numOfArea: " << numOfArea[N] << endl;
return dp[N] - M * K;
}
int main() {
cout << take_photos(2, 100, 2, { 3,6 }, { 5,7 });
}