CSES - Aalto Competitive Programming 2024 - wk4 - Mon - Results
Submission details
Task:Forest density
Sender:louaha1
Submission time:2024-09-23 16:57:03 +0300
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.11 sdetails
#3ACCEPTED0.09 sdetails

Code

#include <iostream>
#include <vector>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
// Create the forest grid and prefix sum array
vector<vector<int>> prefix(n + 1, vector<int>(n + 1, 0));
// Read the forest map and build the prefix sum array
for (int i = 1; i <= n; i++) {
string row;
cin >> row;
for (int j = 1; j <= n; j++) {
// Prefix sum formula
prefix[i][j] = (row[j - 1] == '*' ? 1 : 0) +
prefix[i - 1][j] +
prefix[i][j - 1] -
prefix[i - 1][j - 1];
}
}
// Answer each query
for (int i = 0; i < q; i++) {
int y1, x1, y2, x2;
cin >> y1 >> x1 >> y2 >> x2;
// Calculate the number of trees in the rectangle using the prefix sum
int result = prefix[y2][x2] -
prefix[y1 - 1][x2] -
prefix[y2][x1 - 1] +
prefix[y1 - 1][x1 - 1];
cout << result << '\n';
}
return 0;
}

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