QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#380870 | #2435. Triangles | 8BQube# | AC ✓ | 1190ms | 372224kb | C++20 | 3.1kb | 2024-04-07 14:06:10 | 2024-04-07 14:06:11 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define ALL(v) v.begin(), v.end()
#define pb push_back
#define SZ(a) ((int)a.size())
const int N = 3005, M = 6005;
int L[N][M], R[N][M], U[N][M], D[N][M], H[N][M], HR[N][M];
int bit[M];
void add(int x, int k) {
while (x < M)
bit[x] += k, x += x & -x;
}
ll qr(int x) {
ll ret = 0;
while (x)
ret += bit[x], x -= x & -x;
return ret;
}
vector<int> rm[M];
int main() {
ios::sync_with_stdio(0), cin.tie(0);
int r, _c;
cin >> r >> _c;
int c = (_c + 1) / 2 + (r - 1);
cin.ignore();
for (int i = 1; i <= r; i++) {
string s;
getline(cin, s);
int bs = ((i & 1) ? 0 : 2);
int rb = i / 2 + 1;
for (int j = rb; j <= c; j++) {
int t = bs + (j - rb) * 4;
assert(SZ(s) <= t || s[t] == 'x');
if (t + 2 < SZ(s) && s[t + 2] == '-')
R[i][j] = 1, L[i][j + 1] = 1;
}
if (i == r)
break;
getline(cin, s);
// H
bs = ((i & 1) ? 1 : 3);
for (int j = rb; j <= c; j++) {
int t = bs + (j - rb) * 4;
if (t < SZ(s) && s[t] == '\\')
H[i][j] = 1, HR[i + 1][j + 1] = 1;
}
// D
bs = ((i & 1) ? -1: 1);
for (int j = rb; j <= c; j++) {
int t = bs + (j - rb) * 4;
if (t >= 0 && t < SZ(s) && s[t] == '/')
D[i][j] = 1, U[i + 1][j] = 1;
}
}
for (int i = 1; i <= r; i++)
for (int j = 1; j <= c; j++) {
if (L[i][j]) L[i][j] += L[i][j - 1];
if (U[i][j]) U[i][j] += U[i - 1][j];
if (HR[i][j]) HR[i][j] += HR[i - 1][j - 1];
}
for (int i = r; i >= 1; i--)
for (int j = c; j >= 1; j--) {
if (R[i][j]) R[i][j] += R[i][j + 1];
if (D[i][j]) D[i][j] += D[i + 1][j];
if (H[i][j]) H[i][j] += H[i + 1][j + 1];
}
ll ans = 0;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= c; j++)
rm[j].clear();
memset(bit, 0, sizeof(bit));
for (int j = 1; j <= c; j++) {
ans += qr(j) - qr(j - min(L[i][j], D[i][j]) - 1);
if (H[i][j])
add(j, 1), rm[j + H[i][j]].pb(j);
for (int x : rm[j])
add(x, -1);
}
}
for (int i = 1; i <= r; i++) {
for (int j = c; j >= 1; j--)
rm[j].clear();
memset(bit, 0, sizeof(bit));
for (int j = c; j >= 1; j--) {
ans += qr(j + min(R[i][j], U[i][j])) - qr(j - 1);
if (HR[i][j])
add(j, 1), rm[j - HR[i][j]].pb(j);
for (int x : rm[j])
add(x, -1);
}
}
cout << ans << endl;
// for (int i = 1; i <= r; i++)
// for (int j = 1; j <= r; j++) {
// cerr << i << " " << j << " " << L[i][j] << " " << R[i][j] << " " << U[i][j] << " " << D[i][j] << " " << HR[i][j] << " " << H[i][j] << endl;
// }
}
Details
Test #1:
score: 100
Accepted
time: 2ms
memory: 13768kb
Test #2:
score: 0
Accepted
time: 2ms
memory: 13904kb
Test #3:
score: 0
Accepted
time: 0ms
memory: 3656kb
Test #4:
score: 0
Accepted
time: 0ms
memory: 14088kb
Test #5:
score: 0
Accepted
time: 1ms
memory: 13808kb
Test #6:
score: 0
Accepted
time: 1ms
memory: 7912kb
Test #7:
score: 0
Accepted
time: 0ms
memory: 3512kb
Test #8:
score: 0
Accepted
time: 0ms
memory: 3520kb
Test #9:
score: 0
Accepted
time: 0ms
memory: 13768kb
Test #10:
score: 0
Accepted
time: 2ms
memory: 13900kb
Test #11:
score: 0
Accepted
time: 0ms
memory: 14132kb
Test #12:
score: 0
Accepted
time: 2ms
memory: 15980kb
Test #13:
score: 0
Accepted
time: 0ms
memory: 18304kb
Test #14:
score: 0
Accepted
time: 2ms
memory: 3660kb
Test #15:
score: 0
Accepted
time: 0ms
memory: 17984kb
Test #16:
score: 0
Accepted
time: 0ms
memory: 22504kb
Test #17:
score: 0
Accepted
time: 2ms
memory: 28212kb
Test #18:
score: 0
Accepted
time: 2ms
memory: 18000kb
Test #19:
score: 0
Accepted
time: 0ms
memory: 15928kb
Test #20:
score: 0
Accepted
time: 0ms
memory: 15956kb
Test #21:
score: 0
Accepted
time: 0ms
memory: 15932kb
Test #22:
score: 0
Accepted
time: 3ms
memory: 20412kb
Test #23:
score: 0
Accepted
time: 4ms
memory: 28536kb
Test #24:
score: 0
Accepted
time: 85ms
memory: 155736kb
Test #25:
score: 0
Accepted
time: 0ms
memory: 13824kb
Test #26:
score: 0
Accepted
time: 23ms
memory: 153264kb
Test #27:
score: 0
Accepted
time: 16ms
memory: 85900kb
Test #28:
score: 0
Accepted
time: 16ms
memory: 86036kb
Test #29:
score: 0
Accepted
time: 19ms
memory: 86032kb
Test #30:
score: 0
Accepted
time: 23ms
memory: 83600kb
Test #31:
score: 0
Accepted
time: 32ms
memory: 83528kb
Test #32:
score: 0
Accepted
time: 31ms
memory: 83592kb
Test #33:
score: 0
Accepted
time: 39ms
memory: 83824kb
Test #34:
score: 0
Accepted
time: 29ms
memory: 83712kb
Test #35:
score: 0
Accepted
time: 34ms
memory: 84020kb
Test #36:
score: 0
Accepted
time: 3ms
memory: 15884kb
Test #37:
score: 0
Accepted
time: 111ms
memory: 157436kb
Test #38:
score: 0
Accepted
time: 0ms
memory: 28236kb
Test #39:
score: 0
Accepted
time: 0ms
memory: 22292kb
Test #40:
score: 0
Accepted
time: 3ms
memory: 15836kb
Test #41:
score: 0
Accepted
time: 0ms
memory: 18204kb
Test #42:
score: 0
Accepted
time: 0ms
memory: 24376kb
Test #43:
score: 0
Accepted
time: 2ms
memory: 20028kb
Test #44:
score: 0
Accepted
time: 909ms
memory: 366812kb
Test #45:
score: 0
Accepted
time: 740ms
memory: 371616kb
Test #46:
score: 0
Accepted
time: 792ms
memory: 371528kb
Test #47:
score: 0
Accepted
time: 1107ms
memory: 371168kb
Test #48:
score: 0
Accepted
time: 1138ms
memory: 372224kb
Test #49:
score: 0
Accepted
time: 1190ms
memory: 371560kb
Test #50:
score: 0
Accepted
time: 963ms
memory: 371808kb