CSES - Aalto Competitive Programming 2024 - wk4 - Mon - Results
Submission details
Task:Forest density
Sender:ashum-ta
Submission time:2024-09-23 16:39:05 +0300
Language:Python3 (PyPy3)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.04 sdetails
#2ACCEPTED0.29 sdetails
#3ACCEPTED0.26 sdetails

Code

def main():
import sys
input = sys.stdin.read
data = input().splitlines()
n, q = map(int, data[0].split())
grid = data[1:n+1]
# Create a prefix sum array
prefix = [[0] * (n + 1) for _ in range(n + 1)]
# Fill the prefix sum array
for i in range(1, n + 1):
for j in range(1, n + 1):
is_tree = 1 if grid[i - 1][j - 1] == '*' else 0
prefix[i][j] = (is_tree + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1])
results = []
# Process each query
for 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 results
print("\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