QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #817700 | #2604. Spiral Matrix | 通顶雪道 (Qiuyang Mang, Youran Sun, Qingshuo Guo)# | WA | 96ms | 19948kb | C++23 | 3.3kb | 2024-12-17 10:43:20 | 2024-12-17 10:43:27 |
Judging History
answer
#include <bits/stdc++.h>
#define inf (0x7f7f7f7f)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long ll;
using namespace std;
template <class T>
inline void read(T &x){
int ch = 0, f = 0; x = 0;
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = 1;
for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
if(f) x = -x;
}
const int N = 2005;
int a[N][N], b[N][N]; // up down left right 1 2 3 4
int c[N][N], n, m, q;
int minn[N][N][12], maxx[N][N][12];
int lg[N];
bool check(int ii, int jj, int i, int j){
if(ii < 1 || ii > n || jj < 1 || jj > m) return false;
return a[ii][jj] == a[i][j] + 1;
}
bool get(int r1, int r2, int c1, int c2){
int maxx_ = 0, minn_ = 1e9;
int len = (c2 - c1 + 1);
int k = lg[len];
for(int i = r1; i <= r2; i++){
maxx_ = max(maxx_, max(maxx[i][c1][k], maxx[i][c2 - (1 << k) + 1][k]));
minn_ = min(minn_, min(minn[i][c1][k], minn[i][c2 - (1 << k) + 1][k]));
}
if(maxx_ - minn_ + 1 != (r2 - r1 + 1) * (c2 - c1 + 1)) return false;
int flg = 0;
for(int i = c1; i <= c2; i++){
if(a[r1][i] == maxx_){
flg = 1;
continue;
}
if(b[r1][i] == 1) return false;
}
for(int i = c1; i <= c2; i++){
if(a[r2][i] == maxx_){
flg = 1;
continue;
}
if(b[r2][i] == 2) return false;
}
for(int i = r1; i <= r2; i++){
if(a[i][c1] == maxx_){
flg = 1;
continue;
}
if(b[i][c1] == 3) return false;
}
for(int i = r1; i <= r2; i++){
if(a[i][c2] == maxx_){
flg = 1;
continue;
}
if(b[i][c2] == 4) return false;
}
if(r1 + 1 < r2 && c1 + 1 < c2){
int sum = c[r2 - 1][c2 - 1] + c[r1][c1] - c[r2 - 1][c1] - c[r1][c2 - 1];
if(sum - flg + 1 != (r2 - r1 - 1) * (c2 - c1 - 1)) return false;
}
return true;
}
int main(){
read(n), read(m), read(q);
lg[0] = -1;
for(int i = 1; i <= m; i++) lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) read(a[i][j]);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
if(check(i - 1, j, i, j)) b[i][j] = 1, c[i][j] = 1;
if(check(i + 1, j, i, j)) b[i][j] = 2, c[i][j] = 1;
if(check(i, j - 1, i, j)) b[i][j] = 3, c[i][j] = 1;
if(check(i, j + 1, i, j)) b[i][j] = 4, c[i][j] = 1;
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
c[i][j] += c[i - 1][j] + c[i][j - 1] - c[i - 1][j - 1];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++) minn[i][j][0] = a[i][j], maxx[i][j][0] = a[i][j];
for(int k = 1; k <= 11; k++){
for(int j = 1; j + (1 << k) - 1 <= m; j++){
minn[i][j][k] = min(minn[i][j][k - 1], minn[i][j + (1 << (k - 1))][k - 1]);
maxx[i][j][k] = max(maxx[i][j][k - 1], maxx[i][j + (1 << (k - 1))][k - 1]);
}
}
}
for(int r1, r2, c1, c2, i = 1; i <= q; i++){
read(r1), read(c1);
read(r2), read(c2);
if(get(r1, r2, c1, c2)) puts("YES");
else puts("NO");
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 13872kb
input:
5 7 10 10 11 12 13 14 15 16 9 2 3 32 31 30 17 8 1 4 25 26 29 18 7 6 5 24 27 28 19 52 51 50 23 22 21 20 1 1 5 7 1 1 4 1 2 2 5 3 1 4 5 7 1 1 4 3 1 1 5 3 2 2 2 2 2 2 2 3 3 4 5 7 3 3 4 4
output:
NO YES NO YES YES NO YES YES YES NO
result:
ok 10 token(s): yes count is 6, no count is 4
Test #2:
score: 0
Accepted
time: 95ms
memory: 19948kb
input:
40 40 1000000 1407 1408 1409 1410 1411 1412 1413 1414 1415 1416 1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428 1429 1430 1431 1432 1433 1434 1435 1436 1437 1438 1439 1440 1441 1442 1443 1444 1445 833118646 1406 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271 1272 1273 1274 1275 1...
output:
YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO NO YES YES NO NO NO NO YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO NO YES NO N...
result:
ok 1000000 token(s): yes count is 33440, no count is 966560
Test #3:
score: 0
Accepted
time: 91ms
memory: 15996kb
input:
20 40 1000000 712530981 739725064 974052742 274897187 728181031 385772526 547104847 317359884 998728907 380 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 489874493 376829232 667178919 18692866 510785465 744027226 254071032 301755232 586163239 990504496 472633727 3964923...
output:
YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO NO YES YES NO NO NO NO YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO NO YES NO N...
result:
ok 1000000 token(s): yes count is 20491, no count is 979509
Test #4:
score: -100
Wrong Answer
time: 96ms
memory: 18036kb
input:
35 40 1000000 506970519 105670365 1122 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 203812273 582705388 716509969 822812009 420102286 280391312 1121 992 871 872 873 874 875 876 877 878 87...
output:
YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO NO YES YES NO NO NO NO YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES YES YES NO NO NO NO NO NO NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO YES YES YES YES YES YES NO NO NO NO YES NO NO NO NO YES NO NO YES NO N...
result:
wrong answer expected NO, found YES [1648th token]