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

Code

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
void preCalc(vector<vector<int> > v, vector<vector<int> >& aux) {
int n = v.size();
aux = v;
for (int i = 1; i < n; i++)
for (int j = 0; j < n; j++)
aux[i][j] = v[i][j] + aux[i - 1][j];
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
aux[i][j] += aux[i][j - 1];
}
int calc(vector<vector<int> >& aux, int tli, int tlj, int rbi,
int rbj) {
int sol = aux[rbi][rbj];
if (tli > 0)
sol -= aux[tli - 1][rbj];
if (tlj > 0)
sol -= aux[rbi][tlj - 1];
if (tli > 0 && tlj > 0)
sol += aux[tli - 1][tlj - 1];
return sol;
}
int main() {
// cin >> n >> m;
// vector<vector<char> > map(n, vector<char>(m));
// vector<vector<pair<int, int> > > path(n, vector<pair<int, int> >(m));
int n, q;
cin >> n >> q;
vector<vector<int> > f(n, vector<int>(n));
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
char x;
cin >> x;
if (x == '.')
f[i][j] = 0;
else
f[i][j] = 1;
}
}
vector<vector<int> > aux(n, vector<int>(n));
preCalc(f, aux);
for (int i = 0; i < q; i++) {
int tli, tlj, rbi, rbj;
cin >> tli >> tlj >> rbi >> rbj;
cout << calc(aux, tli - 1, tlj - 1, rbi - 1, rbj - 1) << endl;
}
}

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