QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411076 | #20. Robot Race | Nevll | 0 | 284ms | 155756kb | C++14 | 2.0kb | 2024-05-14 21:42:16 | 2024-05-14 21:42:17 |
Judging History
answer
# include <bits/stdc++.h>
# define ll long long
# define fi first
# define se second
# define pii pair<int, int>
using namespace std;
struct query {
int x1, x2, y1, y2, idx;
};
vector<query> qry;
bool A[1001][1001];
bitset<1001> B[1001][1001];
int ans[1001], l[1001][1001];
int n, m;
void solve(int l, int r, vector<query> q) {
if(l >= r) return;
if(q.size() == 0) return;
int mid = (l + r) / 2;
/// count for mid
for(int c=m;c>=1;c--) {
if(!A[mid][c]) B[mid][c] = 0;
else {
B[mid][c] = B[mid][c + 1];
B[mid][c].set(c);
}
}
// count above mid
for(int i=mid-1;i>=l;i--) {
for(int k=m;k>=1;k--) {
if(!A[i][k]) B[i][k] = 0;
else {
B[i][k] = B[i][k + 1] | B[i + 1][k];
}
}
}
// count mid + 1;
for(int c=m;c>=1;c--) {
if(!A[mid + 1][c]) B[mid + 1][c] = 0;
else {
B[mid + 1][c] = B[mid + 1][c + 1];
B[mid + 1][c].set(c);
}
}
for(int i=mid+2;i<=r;i++) {
for(int k=m;k>=1;k--) {
if(!A[i][k]) B[i][k] = 0;
else {
B[i][k] = B[i][k + 1] | B[i - 1][k];
}
}
}
vector<query> C, D;
C.clear();
D.clear();
for(query p : q) {
if(p.x2 <= mid) {
C.push_back(p);
} else if(p.x1 > mid) {
D.push_back(p);
} else {
ans[p.idx] = (B[p.x1][p.y1]&B[p.x2][p.y2]).any();
}
}
solve(l, mid, C);
solve(mid+1, r, D);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int Q;
cin>>n>>m>>Q;
for(int i=1;i<=n;i++) {
string s;
cin>>s;
for(int k=1;k<=m;k++) {
A[i][k] = (s[k - 1]=='.');
if(A[i][k]) l[i][k] = l[i][k - 1];
else l[i][k] = k;
}
}
for(int i=0;i<Q;i++) {
int x1, x2, y1, y2;
cin>>x1>>x2>>y1>>y2;
if(x1 > x2 || y1 > y2) ans[i] = 0;
else if(x1 == x2) {
if(l[x1][y2] < y1) ans[i] = 1;
else ans[i] = 0;
} else {
qry.push_back((query){x1, x2, y1, y2, i});
}
}
solve(1, n, qry);
for(int i=0;i<Q;i++) {
if(ans[i]) cout<<"YES\n";
else cout<<"NO\n";
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 52ms
memory: 130108kb
input:
971 996 300 ....................................................................................................................................#.......................#................................................#..................................................................#..................
output:
NO NO NO NO NO YES NO YES NO YES YES NO NO NO NO NO YES NO NO NO NO NO YES NO YES NO YES NO YES NO NO NO YES YES YES YES YES YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES YES NO NO NO YES YES YES NO NO NO YES YES YES NO NO NO NO NO NO NO YES NO NO NO YES NO YES NO NO NO NO YES NO YES N...
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 284ms
memory: 155756kb
input:
990 986 1000000 ..........................#..#......................#......................................................................................#................................#..................................................................................................................
output:
NO NO NO NO NO NO YES YES NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO YES NO YES NO NO YES YES NO YES NO NO NO NO NO YES NO YES YES NO YES NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO YES YES NO YES YES YES NO ...
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'