CSES - Aalto Competitive Programming 2024 - wk4 - Mon - Results
Submission details
Task:Forest density
Sender:snude
Submission time:2024-09-23 17:52:33 +0300
Language:C++ (C++11)
Status:READY
Result:
Test results
testverdicttime
#10.00 sdetails
#20.57 sdetails
#30.54 sdetails

Code

#include <cassert>
#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

// Create sum array, REMEMBER TO TAKE BY REFERENCE
void create_sub_sum_array(vector<int> &input, int length, vector<int> &aux)
{
    assert(length > 0);
    aux[0] = input[0];
    for (int i = 1; i < length; i++) {
        aux[i] = aux[i - 1] + input[i];
    }
}

// Get subarray sum
int sub_array_sum(vector<int> &sums, int a, int b)
{
    assert(a <= b);
    int reduction = a - 1 < 0 ? 0 : sums[a - 1];
    return sums[b] - reduction;
}

int main(int argc, char *argv[])
{
	// Read the input parameters
	int n, q;
	cin >> n >> q;

	// Read values from one line
    // int input[n][n];
    vector<int> input[n];
    for (int j = 0; j < n; j++) {
        for (int i = 0; i < n; i++) {
            char tmp;
            cin >> tmp;
            if (tmp == '*') input[j].push_back(1); // = 1;
            else input[j].push_back(0);
            // cin >> input[j][i];
        }
    }

    int sum[n][n];
    sum[0][0] = input[0][0];
    for (int j = 0; j < n; j++) {
        int row_sum = 0;
        for (int i = 0; i < n; i++) {
            row_sum += input[j][i];
            sum[j][i] = row_sum;
            if (j >= 1) {
                sum[j][i] += sum[j-1][i];
            }        }
    }

    // for (int j = 0; j < n; j++) {
    //     for (int i = 0; i < n; i++) {
    //         cout << sum[j][i] << " ";
    //     }
    //     cout << "\n";
    // }


	for (int i = 0; i < q; i++) {
        int y1, x1, y2, x2;
        cin >> x1 >> y1 >> x2 >> y2;
        // fix coordinates
        y1--;
        y2--;
        x1--;
        x2--;
        // cout << y1 << x1 << y2 << x2 << "\n";
        if (x1 >= 1 && y1 >= 1) {
            cout << sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1-1] << "\n";
            continue;
            // cout << sum[x2][y2] << sum[x1 - 1][y2] << sum[x2][y1 - 1] << sum[x1 - 1][y1-1] << "\n";
        }
        if (x1 == 0 && y1 == 0){
            cout << sum[x2][y2];
            continue;
        }
        if (y1 == 0) {
            cout << sum[x2][y2] - sum[x1-1][y2] << "\n";
            continue;
        }
        if (x1 == 0) {
            cout << sum[x2][y2] - sum[x2][y1-1] << "\n";
            continue;
        }
        // cout << sum[x2][y2] - sum[x1][y2] - sum[x2][y1] + sum[x1][y1] << "\n";
	}

	// cout << "TODO: result" << "\n";
	return 0;
}

Test details

Test 1

Verdict:

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

correct output
10
14
5
7
8
...

user output
10
14
5
7
8
...
Truncated

Test 2

Verdict:

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

correct output
41079
2824
15631
1548
8483
...

user output
41079
2824
15631
1548
8483
...
Truncated

Test 3

Verdict:

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

correct output
1000000
1000000
1000000
1000000
1000000
...

user output
100000010000001000000100000010...
Truncated