oj.uz

Submission #429525

# Submission time Handle Problem Language Result Execution time Memory
429525 2021-06-16T05:17:07 Z 반딧불(#7598) Robot Race (CPSPC17_race) C++17
100 / 100
 1065 ms 171632 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Query{
    int x1, y1, x2, y2, idx;
    Query(){}
    Query(int x1, int y1, int x2, int y2, int idx): x1(x1), y1(y1), x2(x2), y2(y2), idx(idx){}
};

int n, m, q;
bool arr[1002][1002]; /// 0: ������ �� ����, 1: ������ �� ����
bool ans[1000002];

bitset<1002> DP[1002][1002];
int tarr[1002];

void dnc(int s, int e, vector<Query>& query){
    if(s>e) return;
    if(s==e){
        for(int i=1; i<=m; i++){
            if(!arr[s][i]) tarr[i] = 0;
            else if(!arr[s][i-1]) tarr[i] = i;
            else tarr[i] = tarr[i-1];
        }
        for(Query qr: query){
            ans[qr.idx] = (tarr[qr.y1] == tarr[qr.y2]);
        }
        return;
    }
    int mid = (s+e)>>1;

    for(int i=m; i>=1; i--){
        if(!arr[mid][i]){
            DP[mid][i].reset();
            continue;
        }
        DP[mid][i] = DP[mid][i+1];
        DP[mid][i][i] = 1;
    }
    for(int i=mid-1; i>=s; i--){
        for(int j=m; j>=1; j--){
            if(!arr[i][j]){
                DP[i][j].reset();
                continue;
            }
            DP[i][j] = DP[i+1][j] | DP[i][j+1];
        }
    }

    for(int i=1; i<=m; i++){
        if(!arr[mid+1][i]){
            DP[mid+1][i].reset();
            continue;
        }
        DP[mid+1][i] = DP[mid+1][i-1];
        DP[mid+1][i][i] = 1;
    }
    for(int i=mid+2; i<=e; i++){
        for(int j=1; j<=m; j++){
            if(!arr[i][j]){
                DP[i][j].reset();
                continue;
            }
            DP[i][j] = DP[i-1][j] | DP[i][j-1];
        }
    }

//    printf("Session %d %d\n", s, e);
//    for(int i=s; i<=e; i++){
//        for(int j=1; j<=m; j++){
//            printf("%d %d: %s\n", i, j, DP[i][j].to_string().c_str());
//        }
//    }

    vector<Query> l, r;
    for(Query qr: query){
        if(qr.x2 <= mid) l.push_back(qr);
        else if(qr.x1 >= mid+1) r.push_back(qr);
        else{
            ans[qr.idx] = (DP[qr.x1][qr.y1] & DP[qr.x2][qr.y2]).any();
        }
    }
    dnc(s, mid, l);
    dnc(mid+1, e, r);
}

int main(){
    scanf("%d %d %d", &n, &m, &q);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            scanf(" %c", &c);
            if(c == '#') arr[i][j] = 0;
            else arr[i][j] = 1;
        }
    }

    vector<Query> query;
    for(int i=1; i<=q; i++){
        int a, b, c, d;
        scanf("%d %d %d %d", &a, &b, &c, &d);
        if(a<=c && b<=d) query.push_back(Query(a, b, c, d, i));
    }

    dnc(1, n, query);
    for(int i=1; i<=q; i++){
        printf("%s\n", ans[i] ? "YES" : "NO");
    }
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d %d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:95:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |             scanf(" %c", &c);
      |             ~~~~~^~~~~~~~~~~
Main.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         scanf("%d %d %d %d", &a, &b, &c, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 125988 KB Output is correct
2 Correct 344 ms 125524 KB Output is correct
3 Correct 355 ms 123240 KB Output is correct
4 Correct 362 ms 126620 KB Output is correct
5 Correct 343 ms 124740 KB Output is correct
6 Correct 307 ms 123664 KB Output is correct
7 Correct 348 ms 123540 KB Output is correct
8 Correct 343 ms 123824 KB Output is correct
9 Correct 347 ms 126400 KB Output is correct
10 Correct 355 ms 126796 KB Output is correct
11 Correct 353 ms 125432 KB Output is correct
12 Correct 322 ms 123344 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 365 ms 125988 KB Output is correct
2 Correct 344 ms 125524 KB Output is correct
3 Correct 355 ms 123240 KB Output is correct
4 Correct 362 ms 126620 KB Output is correct
5 Correct 343 ms 124740 KB Output is correct
6 Correct 307 ms 123664 KB Output is correct
7 Correct 348 ms 123540 KB Output is correct
8 Correct 343 ms 123824 KB Output is correct
9 Correct 347 ms 126400 KB Output is correct
10 Correct 355 ms 126796 KB Output is correct
11 Correct 353 ms 125432 KB Output is correct
12 Correct 322 ms 123344 KB Output is correct
13 Correct 1065 ms 169624 KB Output is correct
14 Correct 1025 ms 171632 KB Output is correct
15 Correct 1022 ms 170732 KB Output is correct
16 Correct 1020 ms 168660 KB Output is correct
17 Correct 950 ms 159068 KB Output is correct
18 Correct 986 ms 155900 KB Output is correct
19 Correct 1059 ms 169484 KB Output is correct
20 Correct 1048 ms 170164 KB Output is correct
21 Correct 1052 ms 165760 KB Output is correct
22 Correct 1038 ms 170412 KB Output is correct
23 Correct 972 ms 167900 KB Output is correct
24 Correct 1000 ms 164212 KB Output is correct