QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#369016 | #6746. Merge the Rectangles | ryh7 | TL | 184ms | 466360kb | C++14 | 4.9kb | 2024-03-27 19:28:24 | 2024-03-27 19:28:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ull;
#define MAX_N 1505
string row[MAX_N], col[MAX_N];
vector<pair<int, int>> dpr[MAX_N], dpc[MAX_N];
int n, m;
template<typename T>
class SparseTable {
using VT = vector<T>;
using VVT = vector<VT>;
using func_type = function<T(const T &, const T &)>;
VVT ST;
static T default_func(const T &t1, const T &t2) { return max(t1, t2); }
func_type op;
public:
explicit SparseTable(const vector<T> &v, func_type _func = default_func) {
op = _func;
int len = v.size(), l1 = ceil(log2(len)) + 1;
ST.assign(l1, VT(len, T()));
for (int i = 0; i < len; ++i) {
ST[0][i] = v[i];
}
for (int j = 1; j < l1; ++j) {
int pj = (1 << (j - 1));
for (int i = 0; i + pj < len; ++i) {
ST[j][i] = op(ST[j - 1][i], ST[j - 1][i + (1 << (j - 1))]);
}
}
}
T query(int l, int r) {
int lt = r - l + 1;
int q = __lg(lt);
return op(ST[q][l], ST[q][r - (1 << q) + 1]);
}
};
vector<SparseTable<pair<int, int>>> str, stc;
void dfs(int tl_r, int tl_c, int br_r, int br_c) {
// cout << tl_r << " " << tl_c << " " << br_r << " " << br_c << endl;
// for (int j = tl_c; j < br_c; ++j) {
// if (dpc[j][tl_r] >= br_r) {
// for (int i = tl_r; i <= br_r; ++i) {
// col[i][j] = '2';
// }
// dfs(tl_r, tl_c, br_r, j);
// dfs(tl_r, j + 1, br_r, br_c);
// }
// }
// for (int i = tl_r; i < br_r; ++i) {
// if (dpr[i][tl_c] >= br_c) {
// for (int j = tl_c; j <= br_c; ++j) {
// row[i][j] = '2';
// }
// dfs(tl_r, tl_c, i, br_c);
// dfs(i + 1, tl_c, br_r, br_c);
// }
// }
if (tl_c < br_c) {
auto j = stc[tl_r].query(tl_c, br_c - 1);
// cout << 1 << endl;
// cout << tl_r << " " << tl_c << " " << br_r << " " << br_c << endl;
// cout << j.first << " " << j.second << endl;
if (j.first != -1 && j.first >= br_r) {
for (int i = tl_r; i <= br_r; ++i) {
col[i][j.second] = '2';
}
dfs(tl_r, tl_c, br_r, j.second);
dfs(tl_r, j.second + 1, br_r, br_c);
}
}
if (tl_r < br_r) {
auto i = str[tl_c].query(tl_r, br_r - 1);
// cout << 2 << endl;
// cout << tl_r << " " << tl_c << " " << br_r << " " << br_c << endl;
// cout << i.first << " " << i.second << endl;
if (i.first != -1 && i.first >= br_c) {
for (int j = tl_c; j <= br_c; ++j) {
row[i.second][j] = '2';
}
dfs(tl_r, tl_c, i.second, br_c);
dfs(i.second + 1, tl_c, br_r, br_c);
}
}
}
bool check() {
for (int i = 0; i < n - 1; ++i) {
// cout << row[i] << endl;
for (auto c: row[i]) {
if (c == '1')return false;
}
}
for (int j = 0; j < m - 1; ++j) {
// cout << col[j] << endl;
for (auto c: col[j]) {
if (c == '1')return false;
}
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
dpr[i].resize(n - 1);
}
for (int i = 0; i < n - 1; ++i) {
cin >> row[i];
dpr[m - 1][i] = {(row[i][m - 1] == '1') ? m - 1 : -1, i};
for (int j = m - 2; j >= 0; --j) {
dpr[j][i] = {(row[i][j] == '1') ? (row[i][j + 1] == '1') ? dpr[j + 1][i].first : j : -1, i};
}
}
for (int i = 0; i < m; ++i) {
str.emplace_back(dpr[i]);
}
// for (int i = 0; i < m; ++i) {
// for (int j = 0; j < n - 1; ++j) {
// cout << dpr[i][j].first << ' '<< dpr[i][j].second << ';';
// }
// cout << endl;
// }
for (int i = 0; i < n; ++i) {
cin >> col[i];
dpc[i].resize(m - 1);
}
for (int j = 0; j < m - 1; ++j) {
dpc[n - 1][j] = {(col[n - 1][j] == '1') ? n - 1 : -1, j};
for (int i = n - 2; i >= 0; --i) {
dpc[i][j] = {(col[i][j] == '1') ? (col[i + 1][j] == '1') ? dpc[i + 1][j].first : i : -1, j};
}
}
for (int i = 0; i < n; ++i) {
stc.emplace_back(dpc[i]);
}
// for (int i = 0; i < n; ++i) {
// for (int j = 0; j < m - 1; ++j) {
// cout << dpc[i][j].first << ' '<< dpc[i][j].second << ';';
// }
// cout << endl;
// }
dfs(0, 0, n - 1, m - 1);
if (check()) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
return 0;
}
//3 4
//0000
//0111
//101
//101
//110
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3748kb
input:
3 4 0000 0111 101 101 110
output:
YES
result:
ok answer is YES
Test #2:
score: 0
Accepted
time: 1ms
memory: 3672kb
input:
3 3 110 011 01 11 10
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 184ms
memory: 466360kb
input:
1500 1500 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
YES
result:
ok answer is YES
Test #4:
score: -100
Time Limit Exceeded
input:
1500 1500 11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...