QOJ.ac
QOJ
ID | Submission ID | Problem | Hacker | Owner | Result | Submit time | Judge time |
---|---|---|---|---|---|---|---|
#946 | #208934 | #21696. 【NOIP Round #3】数圈圈 | yangtb2024 | zeq2022 | Failed. | 2024-10-10 15:25:14 | 2024-10-10 15:25:14 |
Details
Extra Test:
Accepted
time: 0ms
memory: 20032kb
input:
5 5 bbbab ababa bbbab abaaa aabbb
output:
0
result:
ok "0"
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#208934 | #21696. 【NOIP Round #3】数圈圈 | zeq2022 | 100 ✓ | 2875ms | 210356kb | C++14 | 4.2kb | 2023-10-09 22:12:32 | 2024-10-23 22:42:46 |
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
int a[2005][2005], b[2005][2005];
int suf[2][2005][2005], pre[2][2005][2005];
int L[2005][2005], R[2005][2005];
int D[2005][2005], U[2005][2005];
ll zeq[2][2][2005][2005];
void add0(ll *c, int x, int y) {
for (; x <= 2000; x += x & -x) c[x] += y;
}
void add1(ll *c, int x, int y) {
for (; x; x -= x & -x) c[x] += y;
}
ll query0(ll *c, int x) {
ll res = 0;
for (; x; x -= x & -x) res += c[x];
return res;
}
ll query1(ll *c, int x) {
ll res = 0;
for (; x <= 2000; x += x & -x) res += c[x];
return res;
}
ll solve(int ax, int ay, int bx, int by) {
if (ax >= bx || ay >= by) return 0;
ll ret = 0;
if (by - ay >= bx - ax) {
int mid = (ay + by) >> 1;
ret = solve(ax, ay, bx, mid) + solve(ax, mid + 1, bx, by);
for (int i = ax; i <= bx; ++i) {
int left = max(L[i][mid], ay);
int right = min(R[i][mid], by);
for (int j = left; j <= mid; ++j) {
add1(zeq[0][1][i], D[i][j], 1);
add0(zeq[0][0][i], U[i][j], 1);
}
for (int j = mid + 1; j <= right; ++j) {
add1(zeq[1][1][i], D[i][j], 1);
add0(zeq[1][0][i], U[i][j], 1);
}
}
for (int u = ax; u < bx; ++u) {
int Lu = max(L[u][mid], ay), Ru = min(R[u][mid], by);
for (int v = u + 1; v <= bx; ++v) {
int Lv = max(L[v][mid], ay), Rv = min(R[v][mid], by);
ll L = 0, R = 0;
if (Lu >= Lv) L = query1(zeq[0][1][u], v);
else L = query0(zeq[0][0][v], u);
if (Ru <= Rv) R = query1(zeq[1][1][u], v);
else R = query0(zeq[1][0][v], u);
ret += L * R;
}
}
for (int i = ax; i <= bx; ++i) {
int left = max(L[i][mid], ay);
int right = min(R[i][mid], by);
for (int j = left; j <= mid; ++j) {
add1(zeq[0][1][i], D[i][j], -1);
add0(zeq[0][0][i], U[i][j], -1);
}
for (int j = mid + 1; j <= right; ++j) {
add1(zeq[1][1][i], D[i][j], -1);
add0(zeq[1][0][i], U[i][j], -1);
}
}
} else {
int mid = (ax + bx) >> 1;
ret = solve(ax, ay, mid, by) + solve(mid + 1, ay, bx, by);
for (int i = ay; i <= by; ++i) {
int up = max(U[mid][i], ax);
int down = min(D[mid][i], bx);
for (int j = up; j <= mid; ++j) {
add0(zeq[0][0][i], L[j][i], 1);
add1(zeq[1][0][i], R[j][i], 1);
}
for (int j = mid + 1; j <= down; ++j) {
add0(zeq[0][1][i], L[j][i], 1);
add1(zeq[1][1][i], R[j][i], 1);
}
}
for (int u = ay; u < by; ++u) {
int Uu = max(U[mid][u], ax), Du = min(D[mid][u], bx);
for (int v = u + 1; v <= by; ++v) {
int Vu = max(U[mid][v], ax), Dv = min(D[mid][v], bx);
ll U = 0, D = 0;
if (Uu >= Vu) U = query1(zeq[1][0][u], v);
else U = query0(zeq[0][0][v], u);
if (Du <= Dv) D = query1(zeq[1][1][u], v);
else D = query0(zeq[0][1][v], u);
ret += U * D;
}
}
for (int i = ay; i <= by; ++i) {
int up = max(U[mid][i], ax);
int down = min(D[mid][i], bx);
for (int j = up; j <= mid; ++j) {
add0(zeq[0][0][i], L[j][i], -1);
add1(zeq[1][0][i], R[j][i], -1);
}
for (int j = mid + 1; j <= down; ++j) {
add0(zeq[0][1][i], L[j][i], -1);
add1(zeq[1][1][i], R[j][i], -1);
}
}
}
return ret;
}
int main() {
// freopen("ex_circle8.in", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j) {
char c;
cin >> c;
a[i][j] = c - 'a' + 1;
}
for (int j = 1; j <= m; ++j) {
U[1][j] = 1;
for (int i = 2; i <= n; ++i) {
if (a[i - 1][j] == a[i][j]) {
U[i][j] = U[i - 1][j];
} else U[i][j] = i;
}
D[n][j] = n;
for (int i = n - 1; i; --i) {
if (a[i + 1][j] == a[i][j]) {
D[i][j] = D[i + 1][j];
} else D[i][j] = i;
}
}
for (int i = 1; i <= n; ++i) {
L[i][1] = 1;
for (int j = 2; j <= m; ++j) {
if (a[i][j - 1] == a[i][j]) {
L[i][j] = L[i][j - 1];
} else L[i][j] = j;
}
R[i][m] = m;
for (int j = m - 1; j; --j) {
if (a[i][j + 1] == a[i][j]) {
R[i][j] = R[i][j + 1];
} else R[i][j] = j;
}
}
cout << solve(1, 1, n, m);
return 0;
}
/*
5 5
bbbab
ababa
bbbab
abaaa
aabbb
*/