Task: | Forest density |
Sender: | Nallue |
Submission time: | 2024-09-23 16:43:28 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.57 s | details |
#3 | ACCEPTED | 0.55 s | details |
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 |