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

Code

#include <bits/stdc++.h>
using namespace std;
#define I_2D(row, col, width) ((row) * (width) + (col))
#define PRINT_ARR(arr, n) \
do { \
for (int i = 0; i < n; i++) { \
cout << arr[i] << " "; \
} \
cout << "\n"; \
} while (0)
typedef long long ll;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
ll p_sum[n * n];
char c;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> c;
if (c == '\n')
cin >> c;
p_sum[I_2D(i, j, n)] = c == '*' ? 1 : 0;
if (i > 0) {
p_sum[I_2D(i, j, n)] += p_sum[I_2D(i - 1, j, n)];
}
if (j > 0) {
p_sum[I_2D(i, j, n)] += p_sum[I_2D(i, j - 1, n)];
}
if (j > 0 && i > 0) {
p_sum[I_2D(i, j, n)] -= p_sum[I_2D(i - 1, j - 1, n)];
}
}
}
int y1, x1, y2, x2;
ll s;
for (int i = 0; i < q; i++) {
cin >> y1 >> x1 >> y2 >> x2;
--y1, --x1, --y2, --x2;
s = p_sum[I_2D(y2, x2, n)];
if (x1 > 0) {
s -= p_sum[I_2D(y2, x1 - 1, n)];
}
if (y1 > 0) {
s -= p_sum[I_2D(y1 - 1, x2, n)];
}
if (x1 > 0 && y1 > 0) {
s += p_sum[I_2D(y1 - 1, x1 - 1, n)];
}
cout << s << endl;
}
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