QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#386930 | #6746. Merge the Rectangles | k1nsom | TL | 134ms | 42836kb | C++17 | 4.1kb | 2024-04-11 21:39:21 | 2024-04-11 21:39:21 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define N 300005
#define ednl '\n'
#define int long long
int n, m, a[1510][1510] = {0}, b[1510][1510] = {0}, cnt[1510][1510] = {0};
bool vis[1510][1510] = {0};
map<pair<pair<int, int>, pair<int, int>>, int> js;
struct ra
{
int space, sx, sy, tx, ty;
bool operator>(const ra &a) const
{
if (space == a.space)
return sx > a.sx;
return space > a.space;
}
} tmp;
priority_queue<ra, vector<ra>, greater<ra>> q;
set<pair<pair<int, int>, pair<int, int>>> s1, s2;
vector<ra> v;
signed main()
{
cin >> n >> m;
for (int i = 1; i < n; i++)
for (int j = 1; j <= m; j++)
{
char c;
cin >> c;
a[i][j] = c - '0';
}
for (int i = 1; i <= n; i++)
for (int j = 1; j < m; j++)
{
char c;
cin >> c;
b[i][j] = c - '0';
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
if (!vis[i][j])
{
vis[i][j] = 1;
int sx = i, sy = j, tx = i, ty = j;
while (tx <= n && !a[tx][j])
{
tx++;
if (tx > n)
{
tx--;
break;
}
}
while (ty <= m && !b[i][ty])
{
ty++;
if (ty > m)
{
ty--;
break;
}
}
ra tmp = {(ty - sy + 1) * (tx - sx + 1), sx, sy, tx, ty};
q.push(tmp);
v.push_back(tmp);
for (int t = i; t <= tx; t++)
for (int k = j; k <= ty; k++)
vis[t][k] = 1;
s1.insert({{sx, tx}, {sy, ty}}); // s1记录
s2.insert({{sy, ty}, {sx, tx}});
}
int num = 0;
while (!q.empty())
{
ra u = q.top();
q.pop();
s1.erase({{u.sx, u.tx}, {u.sy, u.ty}});
s2.erase({{u.sy, u.ty}, {u.sx, u.tx}});
num++;
if (js[{{u.sx, u.sy}, {u.tx, u.ty}}])
continue;
if (num > 1e6)
{
cout << "NO";
return 0;
}
// cout << u.space << ' ' << u.sx << ' ' << u.sy << ' ' << u.tx << ' ' << u.ty << endl;
if (u.sx == 1 && u.sy == 1 && u.tx == n && u.ty == m)
{
cout << "YES" << endl;
exit(0);
}
auto x = *s1.lower_bound({{u.sx, u.tx}, {0, 0}});
// cout << x.first.first << ' ' << x.first.second << ' ' << x.second.first << ' ' << x.second.second << endl;
if (x.first.first == u.sx && x.first.second == u.tx)
{
int ty = max(u.ty, x.second.second), tx = max(u.tx, x.first.second), sx = min(u.sx, x.first.first), sy = min(u.sy, x.second.first);
// cout << sx << ' ' << sy << ' ' << tx << ' ' << ty << endl;
q.push({(ty - sy + 1) * (tx - sx + 1), sx, sy, tx, ty});
s1.erase(x);
s1.insert({{sx, tx}, {sy, ty}}); // s1记录
js[{{x.first.first, x.second.first}, {x.first.second, x.second.second}}] = 1;
continue;
}
x = *s2.lower_bound({{u.sy, u.ty}, {0, 0}});
// cout << x.first.first << ' ' << x.first.second << ' ' << x.second.first << ' ' << x.second.second << endl;
if (x.first.first == u.sy && x.first.second == u.ty)
{
int ty = max(u.ty, x.first.second), tx = max(u.tx, x.second.second), sx = min(u.sx, x.second.first), sy = min(u.sy, x.first.first);
q.push({(ty - sy + 1) * (tx - sx + 1), sx, sy, tx, ty});
s2.erase(x);
s2.insert({{sy, ty}, {sx, tx}});
js[{{x.first.second, x.second.second}, {x.first.first, x.second.first}}] = 1;
continue;
}
s1.insert({{u.sx, u.tx}, {u.sy, u.ty}});
s2.insert({{u.sy, u.ty}, {u.sx, u.tx}});
}
cout << "NO" << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7776kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 7704kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 134ms
memory: 42836kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...