Task: | Forest density |
Sender: | ZDHKLV |
Submission time: | 2024-09-23 17:21:38 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.56 s | details |
#3 | ACCEPTED | 0.54 s | details |
Code
#include <bits/stdc++.h>using namespace std;int main() {int n, q;cin >> n >> q;int **forest = new int*[n];for (int i = 0; i < n; i++)forest[i] = new int[n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {char c;cin >> c;forest[i][j] = (c == '*') ? 1 : 0;}}long long **prefix = new long long*[n];for (int i = 0; i < n; i++)prefix[i] = new long long[n];prefix[0][0] = forest[0][0];for (int j = 1; j < n; j++)prefix[0][j] = prefix[0][j-1] + forest[0][j];for (int i = 1; i < n; i++) {long long count_on_line = forest[i][0];prefix[i][0] = prefix[i-1][0] + forest[i][0];for (int j = 1; j < n; j++) {count_on_line += forest[i][j];prefix[i][j] = prefix[i-1][j] + count_on_line;}}long long *output = new long long[q];for (int i = 0; i < q; i++) {int y1, x1, y2, x2;cin >> y1 >> x1 >> y2 >> x2;y1--, x1--, y2--, x2--;long long a = prefix[y2][x2];long long b = (y1 > 0) ? prefix[y1-1][x2] : 0;long long c = (x1 > 0) ? prefix[y2][x1-1] : 0;long long d = (x1 > 0 && y1 > 0) ? prefix[y1-1][x1-1] : 0;output[i] = a - b - c + d;}for (int i = 0; i < q; i++)cout << output[i] << 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 |