QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#411081#20. Robot RaceNevll20 450ms195256kbC++142.1kb2024-05-14 21:52:522024-05-14 21:52:52

Judging History

你现在查看的是最新测评结果

  • [2024-05-14 21:52:52]
  • 评测
  • 测评结果:20
  • 用时:450ms
  • 内存:195256kb
  • [2024-05-14 21:52:52]
  • 提交

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'