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

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SEG_OP(a,b) a ^ b
const int N = 1001;
int S[N][N];
int n, q;
int main() {
cin >> n >> q;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
char c;
cin >> c;
S[i][j] = c == '*';
}
}
for (int i = 1; i <= n; ++i) {
int s = 0;
for (int j = 1; j <= n; ++j) {
s += S[i][j];
S[i][j] = s + S[i-1][j];
}
}
for (int i = 0; i < q; ++i) {
int x1, y1, x2, y2;
cin >> y1 >> x1 >> y2 >> x2;
if (x2 < x1) swap(x1,x2);
if (y2 < y1) swap(y1,y2);
--x1; --y1;
cout << S[y1][x1] + S[y2][x2] - S[y2][x1] - S[y1][x2] << '\n';
}
}

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