oj.uz

Submission #429680

# Submission time Handle Problem Language Result Execution time Memory
429680 2021-06-16T08:38:58 Z 장태환(#7566) Robot Race (CPSPC17_race) C++17
100 / 100
 1303 ms 288196 KB 
#include <bits/stdc++.h>
using namespace std;
bitset<1003> le[1003][1003];
bitset<1003> re[1003][1003];
int qinf[1000001][4];
char arr[1003][1003];
int N,M;
int ans[1000001];
void dc(int s,int e,vector<int>q)
{
    if(q.size()==0||s>e)
        return;
    int m=(s+e)/2;
    int i;
    for(i=m;i<=e;i++)
    {
        int j;
        for(j=1;j<=M;j++)
        {
            le[i][j]=0;
            if(arr[i][j]=='#')
                continue;
            if(i==m)
                le[i][j][j]=1;
            else
                le[i][j]|=le[i-1][j];
            le[i][j]|=le[i][j-1];
        }
    }
    for(i=m;i>=s;i--)
    {
        int j;
        for(j=M;j>0;j--)
        {
            re[i][j]=0;
            if(arr[i][j]=='#')
                continue;
            if(i==m)
                re[i][j][j]=1;
            else
                re[i][j]|=re[i+1][j];
            re[i][j]|=re[i][j+1];
        }
    }
    vector<int>lq,rq;
    for(i=0;i<q.size();i++)
    {
        if(qinf[q[i]][2]<m)
        {
            lq.push_back(q[i]);
        }
        else if(qinf[q[i]][0]>m)
        {
            rq.push_back(q[i]);
        }
        else
        {
            ans[q[i]]=(re[qinf[q[i]][0]][qinf[q[i]][1]]&le[qinf[q[i]][2]][qinf[q[i]][3]]).any();
        }
    }
    dc(s,m-1,lq);
    dc(m+1,e,rq);
}
int main()
{
    int Q;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M >> Q;
    int i;
    for(i=0;i<N;i++)
    {
        cin >> (arr[i+1]+1);
    }
    vector<int>qs;
    for(i=0;i<Q;i++)
    {
        cin >> qinf[i][0]>>qinf[i][1]>>qinf[i][2]>>qinf[i][3];
        qs.push_back(i);
    }
    dc(1,N,qs);
    for(i=0;i<Q;i++)
    {
        cout <<(ans[i]?"YES":"NO")<<'\n';
    }
}

Compilation message

Main.cpp: In function 'void dc(int, int, std::vector<int>)':
Main.cpp:46:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(i=0;i<q.size();i++)
      |             ~^~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 248260 KB Output is correct
2 Correct 390 ms 249268 KB Output is correct
3 Correct 340 ms 243632 KB Output is correct
4 Correct 322 ms 248272 KB Output is correct
5 Correct 254 ms 246488 KB Output is correct
6 Correct 225 ms 242924 KB Output is correct
7 Correct 405 ms 244352 KB Output is correct
8 Correct 361 ms 244156 KB Output is correct
9 Correct 409 ms 249156 KB Output is correct
10 Correct 350 ms 249940 KB Output is correct
11 Correct 324 ms 247300 KB Output is correct
12 Correct 291 ms 243784 KB Output is correct

Subtask #2
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 248260 KB Output is correct
2 Correct 390 ms 249268 KB Output is correct
3 Correct 340 ms 243632 KB Output is correct
4 Correct 322 ms 248272 KB Output is correct
5 Correct 254 ms 246488 KB Output is correct
6 Correct 225 ms 242924 KB Output is correct
7 Correct 405 ms 244352 KB Output is correct
8 Correct 361 ms 244156 KB Output is correct
9 Correct 409 ms 249156 KB Output is correct
10 Correct 350 ms 249940 KB Output is correct
11 Correct 324 ms 247300 KB Output is correct
12 Correct 291 ms 243784 KB Output is correct
13 Correct 1249 ms 283204 KB Output is correct
14 Correct 1243 ms 285552 KB Output is correct
15 Correct 1219 ms 288196 KB Output is correct
16 Correct 1209 ms 287988 KB Output is correct
17 Correct 1093 ms 281088 KB Output is correct
18 Correct 999 ms 280296 KB Output is correct
19 Correct 1262 ms 286148 KB Output is correct
20 Correct 1303 ms 287032 KB Output is correct
21 Correct 1258 ms 281168 KB Output is correct
22 Correct 1277 ms 287848 KB Output is correct
23 Correct 1148 ms 283396 KB Output is correct
24 Correct 1175 ms 281140 KB Output is correct