QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#411110 | #20. Robot Race | Nevll | 100 ✓ | 395ms | 206976kb | C++14 | 2.1kb | 2024-05-14 22:52:43 | 2024-05-14 22:52:44 |
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: 105ms
memory: 135332kb
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: 0
Accepted
time: 88ms
memory: 135876kb
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: 0
Accepted
time: 106ms
memory: 135960kb
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: 0
Accepted
time: 97ms
memory: 135100kb
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: 0
Accepted
time: 58ms
memory: 135392kb
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: 0
Accepted
time: 54ms
memory: 135524kb
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: 0
Accepted
time: 102ms
memory: 133780kb
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: 0
Accepted
time: 99ms
memory: 133460kb
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: 0
Accepted
time: 103ms
memory: 134092kb
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: 0
Accepted
time: 112ms
memory: 133948kb
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: 0
Accepted
time: 97ms
memory: 135800kb
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: 0
Accepted
time: 62ms
memory: 135896kb
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: 395ms
memory: 202648kb
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: 0
Accepted
time: 379ms
memory: 204384kb
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: 0
Accepted
time: 355ms
memory: 204576kb
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: 0
Accepted
time: 347ms
memory: 201236kb
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: 0
Accepted
time: 300ms
memory: 191212kb
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: 0
Accepted
time: 305ms
memory: 179508kb
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: 0
Accepted
time: 392ms
memory: 202476kb
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: 0
Accepted
time: 386ms
memory: 205688kb
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: 0
Accepted
time: 367ms
memory: 206976kb
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: 0
Accepted
time: 377ms
memory: 206128kb
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: 0
Accepted
time: 325ms
memory: 205388kb
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: 0
Accepted
time: 347ms
memory: 206708kb
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