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

Code

#include <iostream>
#include <vector>
using namespace std;
void preProcess(const vector<vector<int>>& mat, vector<vector<int>>& aux)
{
int N = mat[0].size();
int M = mat.size();
for (int i=0; i<N; i++) aux[0][i] = mat[0][i];
for (int i=1; i<M; i++){
for (int j=0; j<N; j++){
aux[i][j] = mat[i][j] + aux[i-1][j];
}
}
for (int i=0; i<M; i++)
for (int j=1; j<N; j++)
aux[i][j] += aux[i][j-1];
}
int sumQuery(const vector<vector<int>>& aux, int tli, int tlj, int rbi, int rbj)
{
int res = aux[rbi][rbj];
if (tli > 0)
res = res - aux[tli-1][rbj];
if (tlj > 0)
res = res - aux[rbi][tlj-1];
if (tli > 0 && tlj > 0)
res = res + aux[tli-1][tlj-1];
return res;
}
int main(){
int n,q;
cin >> n >> q;
vector<vector<int>> mat(n, vector<int>(n));
for(int i=0; i<n; i++){
for(int l=0; l<n; l++){
char p;
cin >> p;
if(p=='.'){
mat[i][l] = 0;
}
else mat[i][l] = 1;
}
}
vector<vector<int>> aux(n, vector<int>(n));
preProcess(mat, aux);
for(int i=0; i<q; i++){
int y1,x1,y2,x2;
cin >> y1 >> x1 >> y2 >> x2;
cout << sumQuery(aux,y1-1,x1-1,y2-1,x2-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