#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <set>
#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
const int SIZE = 1000;
int t[25000000], lazy[25000000];
void push(int v, int tlx, int trx, int tly, int try_) {
if (v >= 25000000) exit(0);
if (lazy[v] == 0 || tlx == trx) return;
t[4 * v + 0] += lazy[v];
t[4 * v + 1] += lazy[v];
t[4 * v + 2] += lazy[v];
t[4 * v + 3] += lazy[v];
lazy[4 * v + 0] += lazy[v];
lazy[4 * v + 1] += lazy[v];
lazy[4 * v + 2] += lazy[v];
lazy[4 * v + 3] += lazy[v];
lazy[v] = 0;
}
int max(int a, int b, int c, int d) {
return max(max(a, b), max(c, d));
}
void update(int v, int qlx, int qrx, int qly, int qry, int tlx = 0, int trx = SIZE - 1, int tly = 0, int try_ = SIZE - 1) {
push(v, tlx, trx, tly, try_);
if (qlx <= tlx && trx <= qrx && qly <= tly && try_ <= qry) {
t[v] += 1;
lazy[v] += 1;
return;
}
int tmx = (tlx + trx) / 2;
int tmy = (tly + try_) / 2;
if (qlx <= tmx && qly <= tmy) update(4 * v + 0, qlx, qrx, qly, qry, tlx, tmx, tly, tmy);
if (qlx <= tmx && qry >= tmy + 1) update(4 * v + 1, qlx, qrx, qly, qry, tlx, tmx, tmy + 1, try_);
if (qrx >= tmx + 1 && qly <= tmy) update(4 * v + 2, qlx, qrx, qly, qry, tmx + 1, trx, tly, tmy);
if (qrx >= tmx + 1 && qry >= tmy + 1) update(4 * v + 3, qlx, qrx, qly, qry, tmx + 1, trx, tmy + 1, try_);
t[v] = max(t[4 * v + 0], t[4 * v + 1], t[4 * v + 2], t[4 * v + 3]);
}
int query(int v, int qlx, int qrx, int qly, int qry, int tlx = 0, int trx = SIZE - 1, int tly = 0, int try_ = SIZE - 1) {
push(v, tlx, trx, tly, try_);
if (qlx <= tlx && trx <= qrx && qly <= tly && try_ <= qry) {
return t[v];
}
int tmx = (tlx + trx) / 2;
int tmy = (tly + try_) / 2;
int res = 0;
return max(
query(4 * v + 0, qlx, qrx, qly, qry, tlx, tmx, tly, tmy),
query(4 * v + 1, qlx, qrx, qly, qry, tlx, tmx, tmy + 1, try_),
query(4 * v + 2, qlx, qrx, qly, qry, tmx + 1, trx, tly, tmy),
query(4 * v + 3, qlx, qrx, qly, qry, tmx + 1, trx, tmy + 1, try_)
);
}
int rectangle(int R, int C, int H, int W, int Q[3001][3001]) {
vector<pair<int, pii>> ord;
FOR(i, R) {
FOR(j, C) {
ord.push_back({ Q[i][j], {i, j} });
}
}
sort(ord.begin(), ord.end());
for (auto p: ord) {
int x = p.second.first;
int y = p.second.second;
update(1, max(0, x - H + 1), x, max(0, y - W + 1), y);
//cout << query(0, 0, R - 1, 0, C - 1) << endl;
if (query(1, 0, R - H, 0, C - W) == (H * W + 1) / 2) {
return p.first;
}
}
//cout << "ERROR" << endl;
return -1;
}
#ifdef LOCAL_TEST
int grid[3001][3001];
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("quality.in", "r", stdin);
int r, c, h, w;
cin >> r >> c >> h >> w;
FOR(i, r) {
FOR(j, c) {
cin >> grid[i][j];
}
}
cout << rectangle(r, c, h, w, grid) << endl;
}
#endif
Compilation message
quality.cpp: In function 'int query(int, int, int, int, int, int, int, int, int)':
quality.cpp:75:9: warning: unused variable 'res' [-Wunused-variable]
75 | int res = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
