#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long ll;
vector<ll> A, B, ids; int tam = 0, pos = 0;
bool inutil(int novo, int atual, int velho)
{
return ((B[velho] - B[novo])*(A[atual] - A[velho]) <= (B[velho] - B[atual])*(A[novo] - A[velho]));
}
void update(ll newA, ll newB, ll newId)
{
A.push_back(newA); B.push_back(newB); ids.push_back(newId);
++tam;
while (tam > 2 && inutil(tam-1, tam-2, tam-3)) {A.erase(A.end()-2); B.erase(B.end()-2); ids.erase(ids.end()-2); --tam;}
}
pair<ll, ll> query(ll x)
{
if (pos >= tam) pos = tam-1;
while (pos < tam-1 && (A[pos]*x + B[pos]) >= (A[pos+1]*x + B[pos+1])) ++pos;
return make_pair(A[pos]*x + B[pos], ids[pos]);
}
ll take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c)
{
vector<pair<ll, ll>> v(N);
for (int i = 0; i < N; i++)
{
int Y = r[i], X = c[i];
if (X > Y) swap(X, Y);
v[i] = make_pair(X, Y);
}
sort(v.begin(), v.end(), [&](const pair<int, int> &a, const pair<int, int> &b) {return (a.first == b.first ? a.second < b.second : a.first > b.first);});
vector<pair<ll, ll>> pareto;
for (auto [X, Y] : v)
{
while (!pareto.empty() && pareto.back().second <= Y) pareto.pop_back();
pareto.emplace_back(X, Y);
}
v = pareto;
reverse(v.begin(), v.end()); //So pra ficar ordenado por X
N = v.size(); v.insert(v.begin(), make_pair(-1, -1));
vector<ll> sIni(N+1), inter(N+1);
for (int i = 1; i < N; i++) inter[i] = (v[i+1].first > v[i].second ? 0 : (v[i].second - v[i+1].first + 1)*(v[i].second - v[i+1].first + 1));
for (int i = 1; i <= N; i++) sIni[i] = (v[i].second - v[i].first + 1)*(v[i].second - v[i].first + 1) + sIni[i-1] - inter[i-1];
//Ate aqui estou so reduzindo o problema
auto C = [&](int l, int r) {return ((v[r].second - v[l].first + 1LL) * (v[r].second - v[l].first + 1LL)) - (sIni[r] - sIni[l-1] + inter[l-1]);};
K = min(K, N);
ll ini = 0, fim = M*M;
vector<ll> dp(N+1), dp2(N+1);
while (ini < fim)
{
ll multa = (ini + fim + 1) >> 1LL;
fill(dp.begin(), dp.end(), 0x3f3f3f3f3f3f3f3f); dp[0] = 0;
fill(dp2.begin(), dp2.end(), 0);
A.clear(); B.clear(); ids.clear(); tam = pos = 0;
for (int i = 1; i <= N; i++)
{
update(-2*v[i].first, (v[i].first*v[i].first) - 2*v[i].first + sIni[i-1] - inter[i-1] + dp[i-1], i-1);
dp[i] = multa + ((v[i].second + 1)*(v[i].second + 1)) - sIni[i] + query(v[i].second).first;
dp2[i] = dp2[query(v[i].second).second] + 1;
}
// cerr << "multa: " << multa << ", dp2[N]: " << dp2[N] << '\n';
if (dp2[N] >= K) ini = multa;
else fim = multa-1LL;
}
// cerr << "ini: " << ini << '\n';
// cerr << "dp[N]: " << dp[N] << '\n';
dp[N] -= (dp2[N] * ini);
ll resp = dp[N] - ((dp2[N] - K) * ini);
return resp + sIni[N];
}
Compilation message
aliens.cpp: In function 'll take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:50:10: warning: variable 'C' set but not used [-Wunused-but-set-variable]
50 | auto C = [&](int l, int r) {return ((v[r].second - v[l].first + 1LL) * (v[r].second - v[l].first + 1LL)) - (sIni[r] - sIni[l-1] + inter[l-1]);};
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 21, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 1 |
2 |
Correct |
1 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 1 |
4 |
Incorrect |
1 ms |
348 KB |
Wrong answer: output = 14, expected = 5 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 21, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 21, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 21, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Correct answer: answer = 4 |
2 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
3 |
Correct |
0 ms |
344 KB |
Correct answer: answer = 4 |
4 |
Incorrect |
0 ms |
348 KB |
Wrong answer: output = 21, expected = 12 |
5 |
Halted |
0 ms |
0 KB |
- |