This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// In the name of Allah
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 4;
const int maxs = 2e6 + 4;
int n, m, k;
pii a[maxn]; vector<pii> A;
vector<int> ls[maxs];
priority_queue<pair<int, pii>> qu;
ll cal(pll a, pll b) {
ll d = max(0ll, (a.F + a.S) - (b.F - b.S));
return (4 * b.S * b.S - d * d);
}
ll take_photos(int Nx, int Mx, int Kx, vector<int> r, vector<int> c) {
n = Nx; m = Mx; k = Kx;
for (int i = 0; i < n; i++) {
if (c[i] > r[i]) swap(c[i], r[i]);
a[i] = Mp(r[i], c[i]);
ls[a[i].F].pb(i);
}
for (int i = m - 1; i >= 0; i--) {
for (int j : ls[i]) {
qu.push(Mp(-a[j].S, Mp(i, j)));
}
for (int j : ls[i]) {
if (qu.top().S.S == j) {
int x1 = a[j].F, y1 = a[j].S;
A.pb(Mp(x1 + y1 + 1, x1 - y1 + 1));
}
}
}
n = len(A); sort(all(A));
ll res = 0;
for (int i = 0; i < n; i++) {
if (i - 1 >= 0) res += cal(A[i - 1], A[i]);
else res += cal(Mp(0, 0), A[i]);
}
return res / 4;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |