Submission details
Task:Forest density
Sender:hundlij1
Submission time:2025-09-22 17:45:51 +0300
Language:C++ (C++17)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.23 sdetails
#30.23 sdetails

Code

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;



void task1(){
    int n, q;
    cin >> n >> q;
    vector<int> nums(n);
    vector<int> cum(n +1, 0);
    
    for(int i = 1; i <= n; i++){
        int a;
        cin >> a;
        
        cum[i] = cum[i-1] ^ a;
    }

    for(int i = 0; i < q; i++){
        int a,b;
        cin >> a >> b;
        int sum = cum[b] ^ cum[a-1];

        cout << sum << endl;
    }
}

void task2(){
    int n, q;
    cin >> n >> q;
    vector<vector<int>> grid(n, vector<int>(n,0));
    vector<vector<int>> gridC(n, vector<int>(n,0));
    vector<vector<int>> ques(q, vector<int>(4));

    for(int i = 0; i < n; i++){

        string s;
        cin >> s;
        for(int j = 0; j < n; j++){
            if(s[j] == '.') 
                grid[i][j] = 0;
            else
                grid[i][j] = 1;
        }
    }

    for(int i = 0; i < q; i++){
        int a,b,c,d;
        cin >> a >> b >> c >> d;
        ques[i] = {a-2,b-2,c-1,d-1};
    }



    for(int i = 0; i < n; i++){
       
       for(int j = 0; j < n; j++){
           if(j == 0) gridC[i][j] = grid[i][j] + gridC[i-1][j];
           else if(i == 0) gridC[i][j] = grid[i][j] + gridC[i][j-1];
           else gridC[i][j] = grid[i][j] + gridC[i-1][j] + gridC[i][j-1] - gridC[i-1][j-1];
        }
    }

    for(int i = 0; i < q; i++){
        
        int sum = gridC[ques[i][2]][ques[i][3]] + gridC[ques[i][0]][ques[i][1]]
         - gridC[ques[i][0]][ques[i][3]] - gridC[ques[i][2]][ques[i][1]];
        cout << sum << endl;
    }
}


int main() {
    task2();
}

Test details

Test 1

Verdict:

input
10 100
**.*.*.**.
*.**.*..*.
.*****.**.
**....***.
...

correct output
10
14
5
7
8
...

user output
(empty)

Test 2

Verdict:

input
1000 200000
**.**.****..**.***..**.***.**....

correct output
41079
2824
15631
1548
8483
...

user output
(empty)

Test 3

Verdict:

input
1000 200000
******************************...

correct output
1000000
1000000
1000000
1000000
1000000
...

user output
(empty)