#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<
T,
null_type,
less<T>,
rb_tree_tag,
tree_order_statistics_node_update>;
// gives the number of keys with value strictly less than x
#define lesscount(x) order_of_key(x)
// gives the iterator to kth element (starting from 0)
#define kthiterator(x) find_by_order(x)
#define clock_starts() clock_t begin = clock()
#define clock_ends() clock_t end = clock()
#define print_running_time() double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC; \
printf("Elapsed Time : %.10f second(s)\n", elapsed_secs)
#define readfile(s) freopen(s, "r", stdin)
#define writefile(s) freopen(s, "w", stdout)
#define debug(s) cout<< #s <<" = "<< s <<endl
#define all(v) (v).begin(), (v).end()
#define KeepUnique(v) (v).erase( unique(all(v)), v.end() )
#define cin_cout_is_cool ios_base::sync_with_stdio(false); cin.tie(NULL)
#define PrintBinary(n) cout << #n << " = " << bitset<64>(n) << endl
#define MEMSET(a,val) memset(a, val, sizeof a)
#define PB push_back
#define endl '\n'
#define cin(n) scanf("%d", &n)
#define popcount(x) __builtin_popcount((x))
#define popcountll(x) __builtin_popcountll((x))
inline int myrand(int l, int r) {
int ret = rand(); ret <<= 15; ret ^= rand();
if(ret < 0) ret = -ret; ret %= (r-l+1); ret += l;
return ret;
}
template <typename F, typename S>
ostream& operator << (ostream& os, const pair< F, S>& p) {
return os<<"(" <<p.first<<", "<<p.second<<")"; }
typedef pair<int, int> ii;
template<typename T> using min_pq =
priority_queue<T, vector<T>, greater<T> >;
template<typename T>T max(T a_,T b_,T c_) { return max(a_,max(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_) { return min(a_,min(b_,c_)); }
template<typename T>T min(T a_,T b_,T c_, T d_) { return min(min(a_, b_),min(c_,d_)); }
template<typename T>T max(T a_,T b_,T c_, T d_) { return max(max(a_, b_),max(c_,d_)); }
//int dx[] = {-1, +0, +1, +0};
//int dy[] = {+0, +1, +0, -1};
template<typename T> inline T ceil(T num, T d)
{ return (T)(num/d) + (num%d>(T)0 ? (T)1 : (T)0); }
#define block_no(idx) (idx/BLOCK_SIZE)
#define block_starting(idx) (block_no(idx)*BLOCK_SIZE)
#define block_ending(idx) (min(n, block_no(idx)*BLOCK_SIZE+BLOCK_SIZE-1))
#define block_rank(idx) (idx%BLOCK_SIZE)
typedef long long ll;
const ll is_query = LLONG_MIN+1LL;
struct Line {
ll m, b;
mutable function<const Line*()> succ;
bool operator<(const Line& rhs) const {
if (rhs.b != is_query) return m < rhs.m;
const Line* s = succ();
if (!s) return 0;
ll x = rhs.m;
return b - s->b < (s->m - m) * x;
}
};
struct HullDynamic : public multiset<Line> {
bool bad(iterator y) {
auto z = next(y);
if (y == begin()) {
if (z == end()) return 0;
return y->m == z->m && y->b <= z->b;
}
auto x = prev(y);
if (z == end()) return y->m == x->m && y->b <= x->b;
return 1.0*(x->b - y->b)*(z->m - y->m) >= 1.0*(y->b - z->b)*(y->m - x->m);
}
void addline(ll m, ll b) {
auto y = insert({ -m, -b });
y->succ = [=] { return next(y) == end() ? 0 : &*next(y); };
if (bad(y)) { erase(y); return; }
while (next(y) != end() && bad(next(y))) erase(next(y));
while (y != begin() && bad(prev(y))) erase(prev(y));
}
ll query(ll x) {
auto l = *lower_bound((Line) { x, is_query });
return -(l.m * x + l.b);
}
};
vector<int> L, R;
vector<ii> All;
int n, m, k;
map<ii, int> same;
vector<vector<ll> > dp;
HullDynamic cht[50010];
inline ll sq(ll x) {
return x * x;
}
long long take_photos(int32_t N, int32_t M, int32_t K, vector<int32_t> RR, vector<int32_t> CC) {
n = N, m = M, k = K;
for(int i=0; i<n; i++) {
int x, y;
tie(x, y) = ii(RR[i], CC[i]);
if(x > y) swap(x, y);
if(same.find(ii(x,y)) == same.end())
same[ii(x,y)], All.push_back(ii(x,y));
}
sort(all(All));
{
vector<int> tick;
tick.assign(All.size(), 1);
typedef tuple<int, int, int> trio;
vector<tuple<int, int, int> > temp;
for(int i=0; i<All.size(); i++) {
ii b = All[i];
temp.push_back(trio(b.first, +1, -i));
temp.push_back(trio(b.second, -1, -i));
}
sort(all(temp));
int c = 0;
for(trio b : temp) {
int x, op, id;
tie(x, op, id) = b;
if(op == -1) {
c--;
if(c) tick[-id] = 0;
}
else c++;
}
for(int i=0; i<All.size(); i++) {
if(tick[i]) {
L.push_back(All[i].first);
R.push_back(All[i].second);
}
}
}
n = L.size();
k = min(n, k);
dp.assign(k+3, {});
dp[1].assign(n+3, 0);
for(int i=0; i<n; i++) {
dp[1][i] = (R[i]-L[0]+1)*(R[i]-L[0]+1);
}
for(int i=2; i<=k; i++) {
dp[i].assign(n+3, 0);
dp[i][0] = (R[0]-L[0]+1)*(R[0]-L[0]+1);
for(int j=1; j<n; j++) {
cht[i].addline(-2*L[j], dp[i-1][j-1]+sq(L[j])+sq(max(0, R[j-1]-L[j]+1)));
dp[i][j] = sq(R[j]+1) + cht[i].query(R[j]+1);
}
dp[i-1].clear();
}
return dp[k][n-1] == 1 ? 4 : dp[k][n-1];
}
Compilation message
aliens.cpp: In function 'long long int take_photos(int32_t, int32_t, int32_t, std::vector<int>, std::vector<int>)':
aliens.cpp:131:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<All.size(); i++) {
^
aliens.cpp:147:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<All.size(); i++) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
3 ms |
2856 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
3 ms |
2856 KB |
Wrong answer: output = 14, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
5292 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
3 ms |
2856 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
3 ms |
2856 KB |
Wrong answer: output = 14, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
3 ms |
2856 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
3 ms |
2856 KB |
Wrong answer: output = 14, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
3 ms |
2856 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
3 ms |
2856 KB |
Wrong answer: output = 14, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 2 |
Correct |
3 ms |
2680 KB |
Correct answer: answer = 4 |
| 3 |
Correct |
3 ms |
2856 KB |
Correct answer: answer = 4 |
| 4 |
Incorrect |
3 ms |
2856 KB |
Wrong answer: output = 14, expected = 12 |
| 5 |
Halted |
0 ms |
0 KB |
- |
