# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
965609 | weakweakweak | Garden (JOI23_garden) | C++17 | 1152 ms | 790144 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.
//希望我沒假解...
/*
把題目轉換一下,就變成我有兩個直線,type a就是在兩個直線各加一個點,tybe b就是我可以選哪個直線要加一個點。最後求兩個直線中的相鄰的點對最大的,用d扣掉再+1後就是我要選的範圍。乘起來的最小值就是答案。
我可以枚舉x這條直線上要拿哪個區間,先枚舉左界,然後右界往外長的時候,發現如果[左界, 右界]覆蓋掉所有y值為h的type b,然後不存在y值為h的type a,那我就可以從y這條線上把h丟掉。(dsu 把h - 1、h、h+1 merge起來,但如果h - 1, h + 1我還沒覆蓋到,那就不merge)
維護y這條直線我用有兩種優化的dsu;然後維護h第一次被完全覆蓋掉的位置可用前綴和判斷、用linked list儲存
總時間複雜度就是O(d^2 反阿克曼(2d)) ~= O(d^2)
*/
#include <bits/stdc++.h>
using namespace std;
int n, m, d, cntax[10010] = {0}, cntbx[10010] = {0}, cntb[10010][5010] = {0}, www[5010] = {0}; //www[i]代表i這個y值目前存在哪個x的linked_list裡面,0代表沒存
int ans = INT_MAX;
bool abcovery[10010] = {0};
bool acovery[10010] = {0};
struct linked_list {
int pre[5010], nxt[5010], used[5010] = {0};
void init () {
pre[0] = nxt[0] = 0;
for (int i = 1; i <= d; i++) pre[i] = nxt[i] = -1, used[i] = 0;
}
void add (int x) {
int edd = pre[0];
nxt[x] = nxt[edd], pre[nxt[edd]] = x;
pre[x] = edd, nxt[edd] = x;
used[x] = 1;
}
void del (int x) {
nxt[pre[x]] = nxt[x], pre[nxt[x]] = pre[x];
# | 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... |