QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#700702 | #20. Robot Race | TheZone | 100 ✓ | 405ms | 205260kb | C++23 | 2.6kb | 2024-11-02 13:18:45 | 2024-11-02 13:19:13 |
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<1002> B[1002][1002];
int ans[1000002], 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].reset();
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].reset();
else {
B[i][k].reset();
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].reset();
else {
B[i][k].reset();
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: 111ms
memory: 135972kb
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: 89ms
memory: 133628kb
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: 109ms
memory: 135248kb
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: 103ms
memory: 134516kb
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: 65ms
memory: 135080kb
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: 60ms
memory: 135876kb
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: 99ms
memory: 132628kb
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: 109ms
memory: 133092kb
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: 128ms
memory: 133868kb
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: 106ms
memory: 135704kb
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: 82ms
memory: 136120kb
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: 71ms
memory: 135468kb
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: 80
Accepted
Test #13:
score: 80
Accepted
time: 392ms
memory: 199772kb
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:
ok 1000000 lines
Test #14:
score: 80
Accepted
time: 396ms
memory: 203140kb
input:
979 970 1000000 .#....#....##...#..#..............#................#..................#.........#...........#...........................#..#........#......#.................................................###.#...#..#....................#..#.#.....#..#............#.........#.........#..................
output:
YES YES YES NO YES NO YES NO YES NO YES YES YES NO YES YES YES YES NO YES YES YES YES YES YES YES YES YES YES NO YES YES YES YES NO NO YES NO YES YES YES NO YES NO YES NO NO NO YES YES NO NO YES NO YES YES NO NO YES NO YES NO YES YES YES NO NO NO NO NO YES NO YES NO YES YES NO YES YES NO YES NO YES ...
result:
ok 1000000 lines
Test #15:
score: 80
Accepted
time: 389ms
memory: 202024kb
input:
995 975 1000000 #.#...#.........#.#.#...#...#.#........##......#.#..###.##.##.#....##.#.##..........##.............#....###..#...#..........#.##.#...#.#......#...#.#......#........#.......#.....###..##..##.#.#.....#.........##...#.....#..#..##......#........#.#####..#.#..##.........###........#.#......
output:
NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO YES 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 YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES NO NO NO YES NO NO NO NO NO NO ...
result:
ok 1000000 lines
Test #16:
score: 80
Accepted
time: 379ms
memory: 198040kb
input:
970 993 1000000 .#..#.##.#.##....#.#.#.#...##.###..#####.#.###.####.###...##..........##.##.#.#.#.##..#..####..#..#.#.###.####...##.#.##.##.#..###..#.####.##.#.#.#.###..#.##.###..#.......#######.########.#####...#.####.#.#.#.###....##.###..#...#.##.###...#...##..#..#####......####....##.....##.#...#...
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 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 NO NO NO NO NO NO...
result:
ok 1000000 lines
Test #17:
score: 80
Accepted
time: 329ms
memory: 188432kb
input:
981 993 1000000 ##.##########################.######.#####.#.###.#####.#####################.########.####.###...####################.#################.##############..#####.######.##################.#################################.#####.######.############.##.############.##########..#########.##...
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 1000000 lines
Test #18:
score: 80
Accepted
time: 318ms
memory: 182460kb
input:
981 972 1000000 #####.###################..################.#########.#####################################.#########.##################.###.##################.##.#####################################.##################################################################.###################.######.#####...
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 1000000 lines
Test #19:
score: 80
Accepted
time: 398ms
memory: 201560kb
input:
992 973 1000000 ...............................................................................................................................................................................................................................................................................................
output:
YES NO NO NO YES NO YES NO YES NO YES NO YES YES YES YES YES YES YES NO YES NO YES NO YES NO YES NO YES YES YES NO YES YES YES YES YES NO YES NO YES YES YES NO YES NO YES NO YES YES 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 YES YES YES YES NO...
result:
ok 1000000 lines
Test #20:
score: 80
Accepted
time: 403ms
memory: 200800kb
input:
987 991 1000000 ...............................................................................................................................................................................................................................................................................................
output:
YES YES YES YES YES YES YES NO YES YES YES YES YES NO YES YES YES NO YES NO YES YES YES NO YES YES YES YES YES YES YES NO YES YES YES NO YES NO YES YES YES NO YES YES YES NO YES YES YES NO YES NO YES NO YES NO YES YES YES YES YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES NO YES YES YES YES YE...
result:
ok 1000000 lines
Test #21:
score: 80
Accepted
time: 405ms
memory: 205260kb
input:
992 982 1000000 ...............................................................................................................................................................................................................................................................................................
output:
NO NO YES NO YES NO YES NO YES NO YES NO YES YES YES NO YES NO NO YES YES YES YES YES YES NO YES NO YES YES NO NO YES YES YES NO YES NO YES YES YES NO YES NO NO NO YES YES YES YES YES NO YES YES YES NO YES NO YES NO YES YES YES NO YES YES YES NO YES YES YES NO YES YES YES YES YES NO YES YES YES NO Y...
result:
ok 1000000 lines
Test #22:
score: 80
Accepted
time: 400ms
memory: 200372kb
input:
996 991 1000000 ...............................................................................................................................................................................................................................................................................................
output:
YES NO YES YES NO NO YES NO YES NO YES YES NO YES YES NO YES NO YES YES YES YES YES NO NO YES YES YES YES NO YES YES NO NO YES NO YES YES YES NO NO NO YES NO YES YES YES NO NO NO YES YES YES NO YES NO YES NO NO NO YES NO YES NO YES YES NO NO NO NO YES NO YES NO NO NO NO NO YES YES YES YES NO YES YES...
result:
ok 1000000 lines
Test #23:
score: 80
Accepted
time: 348ms
memory: 199688kb
input:
976 973 1000000 ...............................................................................................................................................................................................................................................................................................
output:
NO NO YES NO NO NO YES YES NO YES NO NO NO NO NO NO NO NO YES NO NO NO NO NO NO NO NO NO YES NO NO NO NO NO YES NO NO NO YES NO YES NO NO NO NO NO NO NO YES NO NO YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO YES 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 N...
result:
ok 1000000 lines
Test #24:
score: 80
Accepted
time: 364ms
memory: 203840kb
input:
998 985 1000000 ...............................................................................................................................................................................................................................................................................................
output:
NO NO NO NO YES 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 YES NO NO NO NO NO NO YES YES 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 YES NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO NO N...
result:
ok 1000000 lines
Extra Test:
score: 0
Extra Test Passed