QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#817727#2604. Spiral Matrix通顶雪道 (Qiuyang Mang, Youran Sun, Qingshuo Guo)#AC ✓348ms144924kbC++232.9kb2024-12-17 11:03:522024-12-17 11:03:52

Judging History

This is the latest submission verdict.

  • [2024-12-17 11:03:52]
  • Judged
  • Verdict: AC
  • Time: 348ms
  • Memory: 144924kb
  • [2024-12-17 11:03:52]
  • Submitted

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 n,m,q;
int a[N][N], out[N][N][4], in[N][N][4]; // up down left right 1 2 3 4
bool check1(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 check2(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;
}
int inget(int r1, int r2, int c1, int c2, int k){
    return in[r2][c2][k] - in[r1 - 1][c2][k] - in[r2][c1 - 1][k] + in[r1 - 1][c1 - 1][k];
}
int outget(int r1, int r2, int c1, int c2, int k){
    return out[r2][c2][k] - out[r1 - 1][c2][k] - out[r2][c1 - 1][k] + out[r1 - 1][c1 - 1][k];
}
bool get(int r1, int r2, int c1, int c2){
    int sumout = 0, sumin = 0;
    for(int k = 0; k < 4; k++){
        sumin += inget(r1, r2, c1, c2, k);
        sumout += outget(r1, r2, c1, c2, k);
    }
    sumin -= inget(r1, r1, c1, c2, 0);
    sumin -= inget(r2, r2, c1, c2, 1);
    sumin -= inget(r1, r2, c1, c1, 2);
    sumin -= inget(r1, r2, c2, c2, 3);
    sumout -= outget(r1, r1, c1, c2, 0);
    sumout -= outget(r2, r2, c1, c2, 1);
    sumout -= outget(r1, r2, c1, c1, 2);
    sumout -= outget(r1, r2, c2, c2, 3);
    int sum = (r2 - r1 + 1) * (c2 - c1 + 1) - 1;
    if(sumin != sum || sumout != sum) return false;
    return true;
}
int main(){
    read(n), read(m), read(q);
    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(check1(i - 1, j, i, j)) out[i][j][0] = 1;
            if(check1(i + 1, j, i, j)) out[i][j][1] = 1;
            if(check1(i, j - 1, i, j)) out[i][j][2] = 1;
            if(check1(i, j + 1, i, j)) out[i][j][3] = 1;
            if(check2(i - 1, j, i, j)) in[i][j][0] = 1;
            if(check2(i + 1, j, i, j)) in[i][j][1] = 1;
            if(check2(i, j - 1, i, j)) in[i][j][2] = 1;
            if(check2(i, j + 1, i, j)) in[i][j][3] = 1;
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            for(int k = 0; k < 4; k++){
                out[i][j][k] += out[i - 1][j][k] + out[i][j - 1][k] - out[i - 1][j - 1][k];
                in[i][j][k] += in[i - 1][j][k] + in[i][j - 1][k] - in[i - 1][j - 1][k];
            }
        }
    }
    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: 1ms
memory: 9692kb

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: 63ms
memory: 9840kb

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: 62ms
memory: 9832kb

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: 0
Accepted
time: 54ms
memory: 11892kb

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:

ok 1000000 token(s): yes count is 27949, no count is 972051

Test #5:

score: 0
Accepted
time: 58ms
memory: 9856kb

input:

40 35 1000000
162953361 984626742 373339308 218677487 798339010 988800670 275685841 876059532 207515629 898974360 124931522 34273380 173746143 810234941 869471812 906854975 30075286 796851273 565287921 916307925 969927053 243924099 199458589 908124263 661753693 650925273 611843818 949728436 50328879...

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 27141, no count is 972859

Test #6:

score: 0
Accepted
time: 348ms
memory: 144728kb

input:

2000 2000 1000000
3990007 3990008 3990009 3990010 3990011 3990012 3990013 3990014 3990015 3990016 3990017 3990018 3990019 3990020 3990021 3990022 3990023 3990024 3990025 3990026 3990027 3990028 3990029 3990030 3990031 3990032 3990033 3990034 3990035 3990036 3990037 3990038 3990039 3990040 3990041 39...

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 12689, no count is 987311

Test #7:

score: 0
Accepted
time: 345ms
memory: 144832kb

input:

2000 2000 1000000
3990007 3990008 3990009 3990010 3990011 3990012 3990013 3990014 3990015 3990016 3990017 3990018 3990019 3990020 3990021 3990022 3990023 3990024 3990025 3990026 3990027 3990028 3990029 3990030 3990031 3990032 3990033 3990034 3990035 3990036 3990037 3990038 3990039 3990040 3990041 39...

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 11946, no count is 988054

Test #8:

score: 0
Accepted
time: 348ms
memory: 144816kb

input:

1999 2000 1000000
3990006 3982021 3982022 3982023 3982024 3982025 3982026 3982027 3982028 3982029 3982030 3982031 3982032 3982033 3982034 3982035 3982036 3982037 3982038 3982039 3982040 3982041 3982042 3982043 3982044 3982045 3982046 3982047 3982048 3982049 3982050 3982051 3982052 3982053 3982054 39...

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 10542, no count is 989458

Test #9:

score: 0
Accepted
time: 343ms
memory: 144868kb

input:

2000 1999 1000000
568567276 288033243 588895052 921541917 631879615 415511839 642762690 566852618 867116844 791218009 897609370 28716586 38234027 126036865 940194493 359908578 951298264 337479791 203767931 584736862 601223620 996231807 209383316 715401406 327458514 896066356 319800783 82971347 30211...

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 11179, no count is 988821

Test #10:

score: 0
Accepted
time: 338ms
memory: 144924kb

input:

2000 2000 1000000
3990007 3990008 3990009 3990010 3990011 3990012 3990013 3990014 3990015 3990016 3990017 3990018 3990019 3990020 3990021 3990022 3990023 3990024 3990025 3990026 3990027 3990028 3990029 3990030 3990031 3990032 3990033 3990034 3990035 3990036 3990037 3990038 3990039 3990040 3990041 39...

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 10087, no count is 989913

Test #11:

score: 0
Accepted
time: 347ms
memory: 144728kb

input:

2000 2000 1000000
3990007 3990008 3990009 3990010 3990011 3990012 3990013 3990014 3990015 3990016 3990017 3990018 3990019 3990020 3990021 3990022 3990023 3990024 3990025 3990026 3990027 3990028 3990029 3990030 3990031 3990032 3990033 3990034 3990035 3990036 3990037 3990038 3990039 3990040 3990041 39...

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 7378, no count is 992622