Task: | Forest density |
Sender: | ashum-ta |
Submission time: | 2024-09-23 16:39:05 +0300 |
Language: | Python3 (PyPy3) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.04 s | details |
#2 | ACCEPTED | 0.29 s | details |
#3 | ACCEPTED | 0.26 s | details |
Code
def main():import sysinput = sys.stdin.readdata = input().splitlines()n, q = map(int, data[0].split())grid = data[1:n+1]# Create a prefix sum arrayprefix = [[0] * (n + 1) for _ in range(n + 1)]# Fill the prefix sum arrayfor i in range(1, n + 1):for j in range(1, n + 1):is_tree = 1 if grid[i - 1][j - 1] == '*' else 0prefix[i][j] = (is_tree + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1])results = []# Process each queryfor line in data[n + 1:n + 1 + q]:y1, x1, y2, x2 = map(int, line.split())count = (prefix[y2][x2]- prefix[y1 - 1][x2]- prefix[y2][x1 - 1]+ prefix[y1 - 1][x1 - 1])results.append(str(count))# Print all resultsprint("\n".join(results))if __name__ == "__main__":main()
Test details
Test 1
Verdict: ACCEPTED
input |
---|
10 100 **.*.*.**. *.**.*..*. .*****.**. **....***. ... |
correct output |
---|
10 14 5 7 8 ... |
user output |
---|
10 14 5 7 8 ... Truncated |
Test 2
Verdict: ACCEPTED
input |
---|
1000 200000 **.**.****..**.***..**.***.**.... |
correct output |
---|
41079 2824 15631 1548 8483 ... |
user output |
---|
41079 2824 15631 1548 8483 ... Truncated |
Test 3
Verdict: ACCEPTED
input |
---|
1000 200000 ******************************... |
correct output |
---|
1000000 1000000 1000000 1000000 1000000 ... |
user output |
---|
1000000 1000000 1000000 1000000 1000000 ... Truncated |