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

Compiler report

input/code.cpp: In function 'std::vector<int> prefix_sum(std::vector<int>&)':
input/code.cpp:10:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |     for (int i = 1; i < arr.size(); ++i) {
      |                     ~~^~~~~~~~~~~~
input/code.cpp: In function 'std::vector<std::vector<int> > prefix_sum(std::vector<std::vector<int> >)':
input/code.cpp:20:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     for (size_t j = 1; j < n; j++)
      |                        ~~^~~
input/code.cpp:26:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     for (size_t i = 1; i < n; i++)
      |                        ~~^~~
input/code.cpp:29:30: warning: comparison of integer expressions of different signedne...

Code

#include <bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << ': ' << x << endl;
vector<int> prefix_sum(vector<int>& arr) {
vector<int> psum(arr.size());
psum[0] = arr[0];
for (int i = 1; i < arr.size(); ++i) {
psum[i] = psum[i - 1] + arr[i];
}
return psum;
}
vector<vector<int>> prefix_sum(vector<vector<int>> forest) {
int n = forest.size();
vector<vector<int>> psum (n, vector<int>(n));
psum[0][0] = forest[0][0];
for (size_t j = 1; j < n; j++)
{
psum[0][j] = psum[0][j-1] + forest[0][j];
}
for (size_t i = 1; i < n; i++)
{
psum[i][0] = forest[i][0] + psum[i-1][0];
for (size_t j = 1; j < n; j++)
{
psum[i][j] = forest[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];
}
}
return psum;
}
int main() {
int n,q;
cin >> n >> q;
vector<vector<int>> forest (n, vector<int>(n));
for (size_t i = 0; i < n; i++)
{
for (size_t j = 0; j < n; j++)
{
char c;
cin >> c;
forest[i][j] = (c == '.') ? 0 : 1;
}
}
int y1[q], x1[q], y2[q], x2[q];
for (size_t i = 0; i < q; i++)
{
cin >> y1[i] >> x1[i] >> y2[i] >> x2[i];
y1[i]--;
x1[i]--;
y2[i]--;
x2[i]--;
}
vector<vector<int>> psum = prefix_sum(forest);
for (size_t i = 0; i < q; i++)
{
int number;
if (x1[i] > 0 && y1[i] > 0) {
number = psum[y2[i]][x2[i]] - psum[y2[i]][x1[i]-1] - psum[y1[i]-1][x2[i]] + psum[y1[i]-1][x1[i]-1];
}
else if (x1[i] > 0 && y1[i] == 0) {
number = psum[y2[i]][x2[i]] - psum[y2[i]][x1[i]-1];
}
else if (x1[i] == 0 && y1[i] > 0) {
number = psum[y2[i]][x2[i]] - psum[y1[i]-1][x2[i]];
}
else {
number = psum[y2[i]][x2[i]];
}
cout << number << 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