QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#380870#2435. Triangles8BQube#AC ✓1190ms372224kbC++203.1kb2024-04-07 14:06:102024-04-07 14:06:11

Judging History

你现在查看的是最新测评结果

  • [2024-04-07 14:06:11]
  • 评测
  • 测评结果:AC
  • 用时:1190ms
  • 内存:372224kb
  • [2024-04-07 14:06:10]
  • 提交

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