Task: | Forest density |
Sender: | paulschulte |
Submission time: | 2024-09-23 16:28:41 +0300 |
Language: | C++ (C++17) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.38 s | details |
#3 | ACCEPTED | 0.36 s | details |
Code
// ~/.vim/cpp_template.cpp#include <bits/stdc++.h>#include <iostream>#include <vector>#include <algorithm>#include <string>#define REP(i,a,b) for (int i = a; i < b; i++)// Type Aliases for 1D and 2D vectors with initialization#define vi(n, val) vector<int>(n, val) // 1D vector of ints with size n, initialized to val#define vll(n, val) vector<long long>(n, val) // 1D vector of long longs with size n, initialized to val#define ll long long#define vvi(n, m, val) vector<vector<int>>(n, vector<int>(m, val)) // 2D vector of ints (n x m), initialized to val#define vvll(n, m, val) vector<vector<long long>>(n, vector<long long>(m, val)) // 2D vector of long longs (n x m), initialized to valusing namespace std;template <typename T>void pV(const std::vector<T>& vec, const std::string& label = "Vector") {std::cout << label << ": [ ";for (const auto& elem : vec) {std::cout << elem << " ";}std::cout << "]" << std::endl;}using namespace std;void dfs(int s, vector<bool> *visited, vector<int> (*adj)[]) {if ((*visited)[s]) return;(*visited)[s] = true;// process node sfor (auto u: (*adj)[s]) {dfs(u, visited, adj);}}/*vector<int> adj[N];vector<bool> visited(N, false);int u, v;for(int i = 0; i < M;i++){cin >> u >> v;u--;v--;adj[u].push_back(v);adj[v].push_back(u);}*/int main() {ios::sync_with_stdio(0);cin.tie(0);// Your code starts hereint n, q;cin >> n >> q;vector<vector<int>> forest(n+1, vector<int>(n+1, 0));vector<vector<int>> fsum(n+1, vector<int>(n+1, 0));REP(i, 1, n+1){string s;cin >> s;REP(j, 0, n){forest[i][j+1] = s[j] == '*';}}// calc treeREP(i, 1, n+1){REP(j, 1, n+1){fsum[i][j] = forest[i][j] + fsum[i-1][j] + fsum[i][j-1] - fsum[i-1][j-1];}}// queriesREP(i, 0, q){int y1, x1, y2, x2;cin >> y1 >> x1 >> y2 >> x2;cout << fsum[y2][x2] - fsum[y2][x1-1] - fsum[y1-1][x2] + fsum[y1-1][x1-1] << 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 |