| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 796253 |
2023-07-28T08:23:16 Z |
GEN 이지후(#10112) |
Security Guard (JOI23_guard) |
C++17 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using pi = array<lint, 2>;
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
int k, chk[4];
lint down(vector<pi> a, lint w, lint h) {
sort(all(a));
lint ph = h;
lint ans = 0;
for (int i = 0; i < sz(a); i++) {
if (ph > a[i][1]) {
ans += 1ll * (w - a[i][0]) * (ph - a[i][1]);
ph = a[i][1];
}
}
return ans;
}
void solve0() {
int n;
lint w, h;
cin >> n >> w >> h;
vector<pi> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
cout << down(a, w, h) << "\n";
}
struct point {
lint first;
lint second;
};
struct cht {
vector<point> v;
int p = 0;
void clear() {
v.clear();
p = 0;
}
bool parksanghoon(point a, point b, point c) { return (__int128)(a.second - b.second) * (c.first - b.first) > (__int128)(b.second - c.second) * (b.first - a.first); }
void addLine(lint x, lint y) {
while (v.size() >= p + 2 && parksanghoon(v[v.size() - 2], v.back(), (point){x, y})) {
v.pop_back();
}
v.push_back({x, y});
}
lint query(int x) {
if (sz(v) == 0)
return -lint(2e18);
auto f = [&](int p) { return v[p].first * x + v[p].second; };
while (p + 1 < sz(v) && f(p) < f(p + 1))
p++;
return v[p].first * x + v[p].second;
}
} cht0, cht1;
lint solve_monotone(vector<pi> a, lint w, lint h) {
a.push_back({w, 0});
a.push_back({0, h});
sort(all(a));
vector<pi> dp(sz(a) - 1);
dp[0][0] = (w - a[1][0]) * (h - a[1][1]);
dp[0][1] = a[1][0] * a[1][1];
vector<lint> s0(sz(a)), s1(sz(a));
for (int i = 1; i < sz(a) - 1; i++) {
s0[i] = s0[i - 1] + (a[i - 1][1] - a[i][1]) * (w - a[i][0]);
s1[i] = s1[i - 1] + (a[i][0] - a[i - 1][0]) * a[i][1];
}
cht0.clear();
cht1.clear();
for (int i = 1; i < sz(a) - 1; i++) {
int j = i - 1;
cht0.addLine(a[j][0], dp[j][0] - s0[j + 1]);
cht1.addLine(-a[j][1], dp[j][1] - s1[j + 1]);
dp[i][0] = cht1.query(a[i + 1][0] - w) - a[i + 1][1] * (w - a[i + 1][0]) + s1[i];
dp[i][1] = cht0.query(-a[i + 1][1]) + s0[i] + a[i + 1][0] * a[i + 1][1];
}
return max(dp.back()[0], dp.back()[1]);
}
void solve1() {
int n;
lint w, h;
cin >> n >> w >> h;
vector<pi> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
a.push_back({w, 0});
a.push_back({0, h});
sort(all(a));
vector<int> chk(sz(a));
vector<int> pmin(sz(a)), smax(sz(a));
for (int i = 0; i < sz(a); i++)
pmin[i] = smax[i] = a[i][1];
for (int i = 1; i < sz(a); i++)
pmin[i] = min(pmin[i], pmin[i - 1]);
for (int i = sz(a) - 2; i >= 0; i--)
smax[i] = max(smax[i], smax[i + 1]);
for (int i = 1; i + 1 < sz(a); i++) {
if (pmin[i - 1] > a[i][1] && smax[i + 1] < a[i][1])
chk[i] = 1;
}
lint ans = 1ll * w * h;
for (int i = 1; i + 1 < sz(a); i++) {
if (chk[i] == 0)
continue;
int j = i;
while (chk[j])
j++;
// [i, j)
int bx = a[i - 1][0], ex = a[j][0];
int by = smax[j], ey = pmin[i - 1];
vector<pi> t;
for (int k = i; k < j; k++) {
t.push_back({a[k][0] - bx, a[k][1] - by});
}
ans -= 1ll * (ex - bx) * (ey - by) - solve_monotone(t, ex - bx, ey - by);
i = j - 1;
}
for (int i = 0; i + 1 < sz(a); i++) {
if (!chk[i] && !chk[i + 1] && pmin[i] > smax[i + 1]) {
ans -= 1ll * (pmin[i] - smax[i + 1]) * (a[i + 1][0] - a[i][0]);
}
}
cout << ans << "\n";
}
void solve2() {
int n;
lint w, h;
cin >> n >> w >> h;
vector<pi> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
if (n >= 6) {
cout << 1ll * w * h << "\n";
return;
}
vector<lint> crdx = {0, w};
vector<lint> crdy = {0, h};
auto comp = [&](vector<lint> &v, lint p) { return lower_bound(all(v), p) - v.begin(); };
for (auto &[x, y] : a) {
crdx.push_back(x);
crdy.push_back(y);
}
sort(all(crdx));
sort(all(crdy));
crdx.resize(unique(all(crdx)) - crdx.begin());
crdy.resize(unique(all(crdy)) - crdy.begin());
w = comp(crdx, w);
h = comp(crdy, h);
for (auto &[x, y] : a) {
x = comp(crdx, x);
y = comp(crdy, y);
}
lint dx[10][10];
lint dap = 0;
for (int i = 0; i < (1 << (2 * n)); i++) {
memset(dx, 0, sizeof(dx));
for (int j = 0; j < n; j++) {
int dir = ((i >> (2 * j)) & 3);
if (dir == 0) {
dx[a[j][0]][a[j][1]]++;
dx[a[j][0]][h]--;
dx[w][a[j][1]]--;
dx[w][h]++;
}
if (dir == 1) {
dx[0][a[j][1]]++;
dx[0][h]--;
dx[a[j][0]][a[j][1]]--;
dx[a[j][0]][h]++;
}
if (dir == 2) {
dx[0][0]++;
dx[0][a[j][1]]--;
dx[a[j][0]][0]--;
dx[a[j][0]][a[j][1]]++;
}
if (dir == 3) {
dx[a[j][0]][0]++;
dx[a[j][0]][a[j][1]]--;
dx[w][0]--;
dx[w][a[j][1]]++;
}
}
lint ans = 0;
for (int i = 0; i <= w; i++) {
for (int j = 0; j <= h; j++) {
if (i)
dx[i][j] += dx[i - 1][j];
if (j)
dx[i][j] += dx[i][j - 1];
if (i && j)
dx[i][j] -= dx[i - 1][j - 1];
if (dx[i][j])
ans += (crdx[i + 1] - crdx[i]) * (crdy[j + 1] - crdy[j]);
}
}
dap = max(dap, ans);
}
cout << dap << "\n";
}
void solve3() {
int n;
lint w, h;
cin >> n >> w >> h;
vector<pi> a(n);
for (auto &[x, y] : a) {
cin >> x >> y;
}
lint dap = down(a, w, h);
{
auto b = a;
for (auto &[x, y] : b)
x = w - x;
dap = max(dap, down(b, w, h));
}
a.push_back({w, h});
a.push_back({0, h});
sort(all(a));
vector<vector<int>> nl(20, vector<int>(sz(a)));
vector<vector<int>> nr(20, vector<int>(sz(a)));
vector<int> surpl(sz(a), 1e9), surpr(sz(a), 1e9);
vector<lint> sumL(sz(a)), sumR(sz(a));
for (int i = 0; i < sz(a);) {
int j = i;
while (j < sz(a) && a[i][0] == a[j][0])
j++;
if (j - i >= 2) {
surpl[j - 1] = a[i + 1][1];
surpr[i] = a[i + 1][1];
}
i = j;
}
{
vector<int> stk;
for (int i = 0; i < sz(a);) {
int j = i;
while (j < sz(a) && a[i][0] == a[j][0])
j++;
while (sz(stk) && a[stk.back()][1] >= a[i][1]) {
surpl[i] = min(surpl[i], (int)a[stk.back()][1]);
stk.pop_back();
}
if (sz(stk)) {
nl[0][i] = stk.back();
sumL[i] = sumL[stk.back()] + (a[i][0] - a[stk.back()][0]) * (h - a[i][1]);
} else {
nl[0][i] = i;
sumL[i] = a[i][0] * (h - a[i][1]);
}
stk.push_back(i);
i = j;
}
}
{
vector<int> stk;
for (int i = sz(a) - 1; i >= 0;) {
int j = i;
while (j >= 0 && a[i][0] == a[j][0])
j--;
while (sz(stk) && a[stk.back()][1] >= a[j + 1][1]) {
surpr[j + 1] = min(surpr[j + 1], (int)a[stk.back()][1]);
stk.pop_back();
}
if (sz(stk)) {
nr[0][j + 1] = stk.back();
sumR[j + 1] = sumR[stk.back()] + (a[stk.back()][0] - a[j + 1][0]) * (h - a[j + 1][1]);
} else {
nr[0][j + 1] = j + 1;
sumR[j + 1] = (w - a[j + 1][0]) * (h - a[j + 1][1]);
}
stk.push_back(j + 1);
i = j;
}
}
for (int i = 1; i < sz(a); i++)
surpl[i] = min(surpl[i], surpl[i - 1]);
for (int i = sz(a) - 2; i >= 0; i--)
surpr[i] = min(surpr[i], surpr[i + 1]);
for (int i = 0; i < sz(a) - 1; i++) {
if (a[i][0] != a[i + 1][0]) {
lint border = min(surpl[i], surpr[i + 1]);
int zl = i, zr = i + 1;
while (zl > 0 && a[zl - 1][0] == a[i][0])
zl--;
while (a[zl][1] >= border && nl[0][zl] != zl)
zl = nl[0][zl];
while (a[zr][1] >= border && nr[0][zr] != zr)
zr = nr[0][zr];
lint ans = (a[zl][1] >= border ? 0 : (sumL[zl] - (h - border) * a[zl][0])) + (a[zr][1] >= border ? 0 : (sumR[zr] - (h - border) * (w - a[zr][0]))) + (h - border) * w;
dap = max(dap, ans);
}
}
cout << dap << "\n";
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> k;
for (int i = 0; i < k; i++) {
int v;
cin >> v;
chk[v - 1] = 1;
}
if (k == 1 && chk[0]) {
int tc;
cin >> tc;
while (tc--) {
solve0();
}
return 0;
}
if (k == 2 && chk[0] && chk[2]) {
int tc;
cin >> tc;
while (tc--) {
solve1();
}
return 0;
}
if (k == 2 && chk[0] && chk[1]) {
int tc;
cin >> tc;
while (tc--) {
solve3();
}
return 0;
}
if (k == 4) {
int tc;
cin >> tc;
while (tc--) {
solve2();
}
return 0;
}
assert(0);
}
Compilation message
guard.cpp: In member function 'void cht::addLine(lint, lint)':
guard.cpp:47:19: warning: comparison of integer expressions of different signedness: 'std::vector<point>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
47 | while (v.size() >= p + 2 && parksanghoon(v[v.size() - 2], v.back(), (point){x, y})) {
| ~~~~~~~~~^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
