Submission #2238808
Source Code Expand
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define EACH(i, c) for (auto &(i): c)
#define all(c) begin(c),end(c)
#define EXIST(s, e) ((s).find(e)!=(s).end())
#define SORT(c) sort(begin(c),end(c))
#define pb emplace_back
#define MP make_pair
#define SZ(a) int((a).size())
//#define LOCAL 0
//#ifdef LOCAL
//#define DEBUG(s) cout << (s) << endl
//#define dump(x) cerr << #x << " = " << (x) << endl
//#define BR cout << endl;
//#else
//#define DEBUG(s) do{}while(0)
//#define dump(x) do{}while(0)
//#define BR
//#endif
//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x) cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する
template<typename T>
class Sum2d {
vector<vector<T> > vv;
unsigned xSize{};
unsigned ySize{};
public:
Sum2d(unsigned xSize, unsigned ySize) {
vector<vector<T> > vv(xSize + 2, vector<T>(ySize + 2));
this->vv = vv;
this->xSize = xSize + 2;
this->ySize = ySize + 2;
}
void add(int x, int y, T value) {
x++;
y++;
this->vv[x][y] += value;
}
void set_sum() {
for (int i = 0; i < xSize - 1; i++) {
for (int j = 0; j < ySize; j++) {
this->vv[i + 1][j] += vv[i][j];
}
}
for (int i = 0; i < xSize; i++) {
for (int j = 0; j < ySize - 1; j++) {
this->vv[i][j + 1] += vv[i][j];
}
}
}
//[sx,tx],[sy,ty]の範囲を求めるZE
T calc(int sx, int sy, int tx, int ty) {
tx++;
ty++;
return this->vv[tx][ty] + this->vv[sx][sy] - this->vv[tx][sy] - this->vv[sx][ty];
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, M, Q;
cin >> N >> M >> Q;
vector<vector<int> > S(N, vector<int>(M, 0));
rep(i, 0, N) {
rep(j, 0, M) {
char tmp;
cin >> tmp;
if (tmp == '1') S[i][j] = 1;
}
}
Sum2d<int> edge(2 * N - 1, 2 * M - 1), ver(2 * N - 1, 2 * M - 1);
rep(i, 0, N) {
rep(j, 0, M) {
if (S[i][j]) {
ver.add(2 * i, 2 * j, 1);
}
}
}
for (int i = 1; i < N; i++) {
if (S[i - 1][0] == S[i][0] && S[i][0] == 1) {
edge.add(2 * i - 1, 0, 1);
}
}
for (int i = 1; i < M; i++) {
if (S[0][i - 1] == S[0][i] && S[0][i] == 1) {
edge.add(0, 2 * i - 1, 1);
}
}
for (int i = 1; i < N; i++) {
for (int j = 1; j < M; j++) {
if (S[i - 1][j] == S[i][j] && S[i][j] == 1) {
edge.add(2 * i - 1, 2 * j, 1);
}
if (S[i][j - 1] == S[i][j] && S[i][j] == 1) {
edge.add(2 * i, 2 * j - 1, 1);
}
}
}
bool debug = true;
auto stat = [&]() {
cout << "--" << endl;
// rep(i, 0, N) {
// rep(j, 0, M) {
// cout << ver.calc(i, j, i, j) << " ";
// }
// cout << endl;
// }
// cout << "--" << endl;
// rep(i, 0, N) {
// rep(j, 0, M) {
// cout << edge.calc(i, j, i, j) << " ";
// }
// cout << endl;
// }
rep(i, 0, N) {
rep(j, 0, M) {
cout << ver.calc(0, 0, i, j) << " ";
}
cout << endl;
}
cout << "--" << endl;
rep(i, 0, N) {
rep(j, 0, M) {
cout << edge.calc(0, 0, i, j) << " ";
}
cout << endl;
}
};
auto stat2 = [&]() {
cout << "-stat2-" << endl;
rep(i, 0, N) {
rep(j, 0, M) {
cout << ver.calc(i, j, i, j) << " ";
}
cout << endl;
}
cout << "--" << endl;
rep(i, 0, N) {
rep(j, 0, M) {
cout << edge.calc(i, j, i, j) << " ";
}
cout << endl;
}
};
if (debug) {
// stat();
}
ver.set_sum();
edge.set_sum();
if (debug) {
// stat();
// stat2();
}
while (Q--) {
int x1, x2, y1, y2;
cin >> x1 >> y1 >> x2 >> y2;
x1--;
x2--;
y1--;
y2--;
x1 *= 2;
x2 *= 2;
y1 *= 2;
y2 *= 2;
// cout << ver.calc(x1, y1, x2, y2) << " - " << edge.calc(x1, y1, x2, y2) << endl;
cout << ver.calc(x1, y1, x2, y2) - edge.calc(x1, y1, x2, y2) << endl;
}
return 0;
}
Submission Info
Submission Time |
|
Task |
C - Nuske vs Phantom Thnook |
User |
homesentinel |
Language |
C++14 (Clang 3.8.0) |
Score |
700 |
Code Size |
5480 Byte |
Status |
AC |
Exec Time |
1704 ms |
Memory |
206848 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
700 / 700 |
Status |
|
|
Set Name |
Test Cases |
Sample |
s1.txt, s2.txt |
All |
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, s1.txt, s2.txt |
Case Name |
Status |
Exec Time |
Memory |
01.txt |
AC |
1631 ms |
205184 KB |
02.txt |
AC |
1704 ms |
205056 KB |
03.txt |
AC |
1610 ms |
204672 KB |
04.txt |
AC |
1682 ms |
203904 KB |
05.txt |
AC |
1611 ms |
205312 KB |
06.txt |
AC |
1685 ms |
205056 KB |
07.txt |
AC |
1515 ms |
194816 KB |
08.txt |
AC |
1610 ms |
196736 KB |
09.txt |
AC |
1511 ms |
176384 KB |
10.txt |
AC |
1673 ms |
204928 KB |
11.txt |
AC |
1597 ms |
205184 KB |
12.txt |
AC |
1209 ms |
74112 KB |
13.txt |
AC |
881 ms |
2560 KB |
14.txt |
AC |
901 ms |
1920 KB |
15.txt |
AC |
805 ms |
640 KB |
16.txt |
AC |
897 ms |
1152 KB |
17.txt |
AC |
885 ms |
1792 KB |
18.txt |
AC |
900 ms |
1408 KB |
19.txt |
AC |
887 ms |
1152 KB |
20.txt |
AC |
1544 ms |
184064 KB |
21.txt |
AC |
1540 ms |
204544 KB |
22.txt |
AC |
1674 ms |
204928 KB |
23.txt |
AC |
904 ms |
3072 KB |
24.txt |
AC |
1678 ms |
204928 KB |
25.txt |
AC |
864 ms |
768 KB |
26.txt |
AC |
881 ms |
1408 KB |
27.txt |
AC |
890 ms |
1024 KB |
28.txt |
AC |
905 ms |
1408 KB |
29.txt |
AC |
883 ms |
2048 KB |
30.txt |
AC |
895 ms |
1280 KB |
31.txt |
AC |
1564 ms |
206848 KB |
32.txt |
AC |
1632 ms |
205312 KB |
33.txt |
AC |
1560 ms |
204928 KB |
34.txt |
AC |
1640 ms |
205184 KB |
35.txt |
AC |
1553 ms |
204800 KB |
36.txt |
AC |
1632 ms |
206208 KB |
37.txt |
AC |
1541 ms |
204800 KB |
38.txt |
AC |
1645 ms |
204672 KB |
39.txt |
AC |
1612 ms |
205312 KB |
40.txt |
AC |
1659 ms |
205184 KB |
41.txt |
AC |
1573 ms |
204928 KB |
42.txt |
AC |
1633 ms |
204800 KB |
43.txt |
AC |
1593 ms |
204416 KB |
44.txt |
AC |
1636 ms |
204544 KB |
45.txt |
AC |
1 ms |
256 KB |
46.txt |
AC |
1 ms |
256 KB |
47.txt |
AC |
1 ms |
256 KB |
48.txt |
AC |
1 ms |
256 KB |
s1.txt |
AC |
1 ms |
256 KB |
s2.txt |
AC |
1 ms |
256 KB |