QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#543657 | #20. Robot Race | 5un_xiaomivita_msg | 100 ✓ | 382ms | 208460kb | C++14 | 2.1kb | 2024-09-01 17:49:08 | 2024-09-01 17:49:09 |
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;
}
詳細信息
Subtask #1:
score: 20
Accepted
Test #1:
score: 20
Accepted
time: 97ms
memory: 133020kb
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: 100ms
memory: 135836kb
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: 120ms
memory: 135836kb
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: 91ms
memory: 135904kb
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: 63ms
memory: 135736kb
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: 57ms
memory: 135328kb
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: 104ms
memory: 133828kb
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: 119ms
memory: 133796kb
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: 132896kb
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: 104ms
memory: 135504kb
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: 86ms
memory: 135036kb
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: 79ms
memory: 135828kb
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: 361ms
memory: 208460kb
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: 373ms
memory: 206436kb
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: 349ms
memory: 204776kb
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: 361ms
memory: 201412kb
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: 331ms
memory: 191112kb
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: 282ms
memory: 182396kb
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: 355ms
memory: 202328kb
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: 368ms
memory: 206664kb
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: 377ms
memory: 207008kb
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: 382ms
memory: 205456kb
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: 338ms
memory: 202984kb
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: 325ms
memory: 204164kb
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