QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#411081 | #20. Robot Race | Nevll | 20 | 450ms | 195256kb | C++14 | 2.1kb | 2024-05-14 21:52:52 | 2024-05-14 21:52:52 |
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[1002][1002];
bitset<1001> B[1002][1002];
int ans[1001], l[1002][1002];
int n, m;
void solve(int l, int r, vector<query> q) {
if(l >= r) return;
if(q.empty()) 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] = 0;
if(A[i][k + 1]) B[i][k] |= B[i][k + 1];
if(A[i + 1][k]) B[i][k] |= B[i + 1][k];
}
}
}
// count mid + 1;
for(int c=1;c<=m;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] = 0;
if(A[i][k - 1]) B[i][k] |= B[i][k - 1];
if(A[i - 1][k]) B[i][k] |= 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>>y1>>x2>>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";
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 133ms
memory: 129988kb
input:
971 996 300 ....................................................................................................................................#.......................#................................................#..................................................................#..................
output:
YES NO YES YES YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES YES YES NO YES NO YES YES YES NO YES NO YES NO NO NO YES YES YES NO YES NO YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES NO YES YES YES NO YES NO YES YES YES YES YES NO YES NO YES NO YES NO YES YES YES ...
result:
ok 300 lines
Test #2:
score: 20
Accepted
time: 124ms
memory: 130808kb
input:
976 978 300 .......................#..............#..............#................#..............................................#.#......##............................#...............................#.....#...#...........#.#.................#.....#.#....#..#.........#......#...........................
output:
YES NO YES YES YES YES YES YES YES YES YES YES YES YES NO NO YES NO YES NO YES YES YES YES NO YES YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES NO YES YES YES NO YES NO YES NO NO NO YES NO YES NO YES YES YES YES YES NO YES NO YES NO NO YES YES YES NO NO YES YES NO NO YES NO YES YES YES YES Y...
result:
ok 300 lines
Test #3:
score: 20
Accepted
time: 131ms
memory: 132776kb
input:
991 984 300 .##.....#...#..#..#..#####....##.##.....#..#.#.##.#.......#.##....#.#.#..###..#.#.#..#.#..###...##........##.#..#.#..#.##..#.##...........##.........##...#..#.#.......#..#.......#.##.##.#........#..#....##.##...###................###...#.#..#........#....##....#.....##....##.....##.........
output:
NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO YES NO NO NO NO NO NO NO NO N...
result:
ok 300 lines
Test #4:
score: 20
Accepted
time: 120ms
memory: 132176kb
input:
988 998 300 ######.......#####.##..###..##.##.###..#...###.###..###...##......####..##.##.#..#....#..#.##.#####.###.####....######.#.###.#####..#####.###.##.....##...###..#.##....#....##.#.##....#..##..##....#.#.#...##..###.#...#.###..##.#.######..#....#.##.#.#.##.#.##.......##...#.#...##.#....#...#...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO...
result:
ok 300 lines
Test #5:
score: 20
Accepted
time: 85ms
memory: 131652kb
input:
984 977 300 #####.#################################.##################.#####################..###############################.###################################.#############.###.#####.###.###############.####################.#####################################.###.############.##.#######.#####.#...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 300 lines
Test #6:
score: 20
Accepted
time: 101ms
memory: 133524kb
input:
997 982 300 ##############.#######.#############.###################.#####################.###.#############################.#####################################################################.########.##################.####.######################.###################.##########..#################...
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO ...
result:
ok 300 lines
Test #7:
score: 20
Accepted
time: 119ms
memory: 130248kb
input:
973 988 300 ...................................................................................................................................................................................................................................................................................................
output:
YES NO YES NO YES YES YES NO YES YES YES NO YES NO YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES NO YES NO YES NO YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES YES YES NO YES NO YES NO YES YES YES YES YES YES YES NO YES YES YES YES...
result:
ok 300 lines
Test #8:
score: 20
Accepted
time: 128ms
memory: 130296kb
input:
974 998 300 ...................................................................................................................................................................................................................................................................................................
output:
YES NO YES YES YES YES YES NO YES NO YES YES YES NO YES NO YES YES YES NO YES NO YES YES YES YES YES NO YES YES YES YES YES NO YES NO YES NO YES YES YES YES YES NO YES YES YES NO YES YES YES NO YES NO YES YES YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES YES NO YES YES YES NO YES YES...
result:
ok 300 lines
Test #9:
score: 20
Accepted
time: 138ms
memory: 129992kb
input:
971 973 300 ...................................................................................................................................................................................................................................................................................................
output:
YES YES YES YES YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES NO YES NO YES YES YES YES YES YES YES YES YES YES NO NO YES NO YES YES YES YES YES NO YES NO YES NO NO YES YES NO YES YES YES NO NO YES YES YES YES YES NO YES YES NO YES YES YES NO YES NO YES NO YES YES YES NO YES YES YES NO YE...
result:
ok 300 lines
Test #10:
score: 20
Accepted
time: 134ms
memory: 131596kb
input:
984 978 300 ...................................................................................................................................................................................................................................................................................................
output:
YES NO YES NO YES YES YES NO YES NO NO NO YES YES YES NO YES NO YES NO YES NO YES YES NO NO NO YES YES NO YES NO YES YES YES NO NO YES YES NO YES NO NO YES YES YES NO NO YES YES NO YES YES NO YES NO YES YES NO YES YES NO YES NO YES YES YES NO YES NO NO NO YES YES YES NO YES NO YES YES YES NO YES NO ...
result:
ok 300 lines
Test #11:
score: 20
Accepted
time: 102ms
memory: 132956kb
input:
994 989 300 ...................................................................................................................................................................................................................................................................................................
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES YES NO NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO ...
result:
ok 300 lines
Test #12:
score: 20
Accepted
time: 102ms
memory: 131512kb
input:
983 974 300 ...................................................................................................................................................................................................................................................................................................
output:
NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO YES NO NO YES YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO ...
result:
ok 300 lines
Subtask #2:
score: 0
Wrong Answer
Test #13:
score: 0
Wrong Answer
time: 450ms
memory: 195256kb
input:
990 986 1000000 ..........................#..#......................#......................................................................................#................................#..................................................................................................................
output:
YES YES YES YES YES NO YES NO YES YES YES YES YES NO YES YES YES YES YES NO YES YES YES NO YES NO YES YES YES YES NO NO YES NO YES NO YES YES YES YES YES NO YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES YES YES YES YES NO YES NO YES NO YES YES YES NO YES NO YES NO YES YES YES NO YES NO YE...
result:
wrong answer 33106th lines differ - expected: 'YES', found: 'NO'