QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411078 | #20. Robot Race | Nevll | 0 | 271ms | 157164kb | C++14 | 2.0kb | 2024-05-14 21:44:08 | 2024-05-14 21:44:08 |
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=1;k<=m;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[x2][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: 48ms
memory: 134012kb
input:
971 996 300 ....................................................................................................................................#.......................#................................................#..................................................................#..................
output:
YES 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 YES 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...
result:
wrong answer 3rd lines differ - expected: 'YES', found: 'NO'
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 271ms
memory: 157164kb
input:
990 986 1000000 ..........................#..#......................#......................................................................................#................................#..................................................................................................................
output:
NO NO YES NO NO NO YES YES NO NO NO NO NO NO NO NO YES NO YES NO NO NO YES NO NO NO NO YES 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 ...
result:
wrong answer 1st lines differ - expected: 'YES', found: 'NO'