QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#294337 | #7120. Soccer | Goldenglow1427 | Compile Error | / | / | C++14 | 6.5kb | 2023-12-30 12:34:13 | 2024-04-28 08:28:56 |
Judging History
你现在查看的是最新测评结果
- [2024-04-28 08:28:56]
- 管理员手动重测本题所有提交记录
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-12-30 12:34:13]
- 评测
- 测评结果:Compile Error
- 用时:0ms
- 内存:0kb
- [2023-12-30 12:34:13]
- 提交
answer
/*
ID: Victor Chen [mail_vi1]
PROG: Soccer Stadium
LANG: C++
*/
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;
typedef long long ll;
const int Maxn = 2e3;
map<ll, int> hash_mp;
struct Rect
{
int l, r;
int u, d;
int hshid;
Rect(){}
Rect(int x1, int y1, int x2, int y2)
{
u = x1; d = x2;
l = y1; r = y2;
}
ll get_hash()
{
return ((((ll)(l*Maxn)+r)*Maxn)+u)*Maxn+d;
}
}rec[Maxn+10][Maxn+10];
int cnt_r;
Rect ord[Maxn*Maxn];
int n, cnt, dp[Maxn*Maxn+10];
int mp[Maxn+10][Maxn+10];
// Comparator for rectangeles.
bool cmp(Rect x, Rect y)
{
return (x.d-x.u) < (y.d-y.u);
}
// Finding the 2-D prefix sum and thus find out the range sum.
int pre[Maxn+10][Maxn+10];
int find_area(int x1, int y1, int x2, int y2)
{
return pre[x2][y2] - pre[x1-1][y2] - pre[x2][y1-1] + pre[x1-1][y1-1];
}
// Finding out the rectangle for given line (with optimizations).
Rect find_rect(int tp, int ed, int k)
{
Rect ret = Rect(tp, k, ed, k);
int l = 1, r = k;
while(l <= r)
{
int mid = (l+r)/2;
if(find_area(tp, mid, ed, k) == 0)
{
ret.l = mid;
r = mid-1;
}
else
l = mid+1;
}
l = k, r = n;
while(l <= r)
{
int mid = (l+r)/2;
if(find_area(tp, k, ed, mid) == 0)
{
ret.r = mid;
l = mid+1;
}
else
r = mid-1;
}
return ret;
}
ll mx_pre[Maxn+10][Maxn+10];
ll mx_nxt[Maxn+10][Maxn+10];
int mx_dpid[Maxn+10][Maxn+10];
// Finding out the upper rectangle for given line.
Rect find_upper_rect(int bg, int ed, int k)
{
Rect ret = Rect(k, bg, k, ed);
int l = 1, r = k;
while(l <= r)
{
int mid = (l+r)/2;
if(find_area(mid, bg, k, ed) == 0)
{
ret.u = mid;
r = mid-1;
}
else
l = mid+1;
}
return ret;
}
// Get the area of a certain rectangle.
int get_area(Rect x)
{
return (x.d-x.u+1) * (x.r-x.l+1);
}
// Get the crossing area of two rectangles.
int get_cross_area(Rect x, Rect y)
{
return (min(x.d,y.d)-max(x.u,y.u)+1) * (min(x.r,y.r)-max(x.l,y.l)+1);
}
// Locating the next and the previous different tile.
int prv[Maxn+10][Maxn+10], nxt[Maxn+10][Maxn+10];
// Finding out the largest possible stadium in a certain map.
int biggest_stadium(int N, vector<vector<int>> F)
{
int ans = 0;
n = N;
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
{
mp[i][j] = F[i-1][j-1];
pre[i][j] = pre[i-1][j] + pre[i][j-1] - pre[i-1][j-1] + mp[i][j];
}
// Finding the next different tile.
for(int i=1; i<=n; i++)
{
int lst0 = n+1, lst1 = n+1;
for(int j=n; j>=1; j--)
if(mp[i][j] == 0)
{
nxt[i][j] = lst1;
lst0 = j;
}
else
{
nxt[i][j] = lst0;
lst1 = j;
}
}
// Finding the previous different tile.
for(int i=1; i<=n; i++)
{
int pre0 = 0, pre1 = 0;
for(int j=1; j<=n; j++)
if(mp[i][j] == 0)
{
prv[i][j] = pre1;
pre0 = j;
}
else
{
prv[i][j] = pre0;
pre1 = j;
}
}
// The columns.
for(int i=1; i<=n; i++)
{
int tp = 0;
for(int j=1; j<=n; j++)
if(mp[j][i] == 1)
tp = j;
else
{
if(i <= mx_nxt[tp+1][j])
{
rec[i][j] = Rect(tp+1, mx_pre[tp+1][j], j, mx_nxt[tp+1][j]);
rec[i][j].hshid = mx_dpid[tp+1][j];
}
else
{
rec[i][j] = find_rect(tp+1, j, i);
mx_pre[tp+1][j] = rec[i][j].l;
mx_nxt[tp+1][j] = rec[i][j].r;
mx_dpid[tp+1][j] = ++cnt;
rec[i][j].hshid = cnt;
hash_mp[rec[i][j].get_hash()] = cnt;
ord[++cnt_r] = rec[i][j];
}
}
}
sort(ord+1, ord+cnt_r+1, cmp);
for(int i=1; i<=cnt_r; i++)
{
// printf("%d %d %d %d\n", ord[i].l, ord[i].r, ord[i].u, ord[i].d);
dp[ord[i].hshid] = max(dp[ord[i].hshid], get_area(ord[i]));
if(ord[i].u != 1)
{
int bg = ord[i].l;
if(mp[ord[i].u-1][bg] == 1)
bg = nxt[ord[i].u-1][bg];
int ed = nxt[ord[i].u-1][bg] - 1;
if(ed >= ord[i].r) ed = ord[i].r;
// ord[i].print();
// printf("%d %d\n", bg, ed);
while(bg <= ord[i].r)
{
Rect nw = find_upper_rect(bg, ed, ord[i].d);
// nw.getHash();
nw.hshid = hash_mp[nw.get_hash()];
dp[nw.hshid] = max(dp[nw.hshid], dp[ord[i].hshid] + get_area(nw) - get_cross_area(nw, ord[i]));
bg = nxt[ord[i].u-1][ed+1];
ed = nxt[ord[i].u-1][bg] - 1;
if(ed >= ord[i].r) ed = ord[i].r;
if(bg == 0) break;
// printf("%d %d\n", bg, ed);
}
}
if(ord[i].d != n)
{
for(int j=ord[i].l; j<=ord[i].r; j++)
if(mp[ord[i].d+1][j] == 0)
dp[rec[j][ord[i].d+1].hshid] = max(dp[rec[j][ord[i].d+1].hshid], dp[ord[i].hshid] + get_area(rec[j][ord[i].d+1]) - get_cross_area(rec[j][ord[i].d+1], ord[i]));
}
ans = max(ans, dp[ord[i].hshid]);
}
// for(int i=1; i<=cnt_r; i++)
// printf("%d %d %d %d %d\n", ord[i].l, ord[i].r, ord[i].u, ord[i].d, dp[ord[i].hshid]);
return ans;
}
// int N;
// vector<int> ept;
// vector<vector<int>> F;
// int main()
// {
// freopen("starcase-large-06.in", "r", stdin);
// // freopen("read.in", "r", stdin);
// scanf("%d", &N);
// for(int i=0; i<N; i++)
// {
// F.push_back(ept);
// for(int j=0; j<N; j++)
// {
// int x;
// scanf("%d", &x);
// F[i].push_back(x);
// }
// }
// printf("%d\n", biggest_stadium(N, F));
// return 0;
// }
詳細信息
answer.code:132:28: error: ‘vector’ has not been declared 132 | int biggest_stadium(int N, vector<vector<int>> F) | ^~~~~~ answer.code:132:34: error: expected ‘,’ or ‘...’ before ‘<’ token 132 | int biggest_stadium(int N, vector<vector<int>> F) | ^ answer.code: In function ‘int biggest_stadium(int, int)’: answer.code:140:24: error: ‘F’ was not declared in this scope 140 | mp[i][j] = F[i-1][j-1]; | ^