QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#87875 | #20. Robot Race | QwQcOrZ | 100 ✓ | 567ms | 200528kb | C++14 | 2.0kb | 2023-03-14 16:58:25 | 2023-03-14 16:58:25 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e3+5;
const int M=1e6+5;
struct Query {
int x1,y1,x2,y2,id;
};
int n,m,Q,l[N][N];
bool a[N][N],ans[M];
bitset<N>b[N][N];
void solve(int l,int r,vector<Query>q) {
if (q.empty()) {
return;
}
if (l>=r) {
return;
}
int mid=(l+r)/2;
for (int i=m;i>=1;i--) {
if (a[mid][i]) {
b[mid][i]=b[mid][i+1];
b[mid][i].set(i);
} else {
b[mid][i].reset();
}
}
for (int i=mid-1;i>=l;i--) {
for (int j=m;j>=1;j--) {
b[i][j].reset();
if (a[i][j]) {
if (a[i+1][j]) {
b[i][j]|=b[i+1][j];
}
if (a[i][j+1]) {
b[i][j]|=b[i][j+1];
}
}
}
}
for (int i=1;i<=m;i++) {
if (a[mid+1][i]) {
b[mid+1][i]=b[mid+1][i-1];
b[mid+1][i].set(i);
} else {
b[mid+1][i].reset();
}
}
for (int i=mid+2;i<=r;i++) {
for (int j=1;j<=m;j++) {
b[i][j].reset();
if (a[i][j]) {
if (a[i-1][j]) {
b[i][j]|=b[i-1][j];
}
if (a[i][j-1]) {
b[i][j]|=b[i][j-1];
}
}
}
}
vector<Query>A,B;
for (auto [x1,y1,x2,y2,id]:q) {
if (x2<=mid) {
A.emplace_back((Query){x1,y1,x2,y2,id});
} else if (x1>mid) {
B.emplace_back((Query){x1,y1,x2,y2,id});
} else {
ans[id]=(b[x1][y1]&b[x2][y2]).any();
}
}
solve(l,mid,A);
solve(mid+1,r,B);
}
signed main() {
ios::sync_with_stdio(false),cin.tie(0);
cout.precision(10),cout.setf(ios::fixed);
cin>>n>>m>>Q;
for (int i=1;i<=n;i++) {
string s;
cin>>s;
for (int j=1;j<=m;j++) {
a[i][j]=s[j-1]=='.';
l[i][j]=a[i][j]?l[i][j-1]:j;
}
}
vector<Query>q;
for (int i=0;i<Q;i++) {
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
if (x1>x2||y1>y2) {
ans[i]=0;
} else if (x1==x2) {
ans[i]=l[x2][y2]<y1;
} else {
q.emplace_back((Query){x1,y1,x2,y2,i});
}
}
solve(1,n,q);
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: 172ms
memory: 130192kb
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: 148ms
memory: 130796kb
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: 160ms
memory: 132680kb
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: 125ms
memory: 132464kb
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: 87ms
memory: 131776kb
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: 87ms
memory: 133516kb
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: 139ms
memory: 130516kb
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: 143ms
memory: 130476kb
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: 147ms
memory: 130024kb
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: 144ms
memory: 131876kb
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: 100ms
memory: 133080kb
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: 114ms
memory: 131816kb
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: 543ms
memory: 196316kb
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: 542ms
memory: 198920kb
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: 537ms
memory: 196828kb
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: 504ms
memory: 192492kb
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: 440ms
memory: 183808kb
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: 387ms
memory: 175176kb
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: 519ms
memory: 197260kb
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: 567ms
memory: 195960kb
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: 544ms
memory: 200528kb
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: 543ms
memory: 196916kb
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: 480ms
memory: 193672kb
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: 470ms
memory: 199464kb
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