Submission #30543076

Source Code Expand

// Subtask4: O(N^2+M+Q)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (int i = 0; i < n; i++)
#define rev(i, n) for (int i = n; i > 0; i--)

int N, M;
int A[300005];
ll sum[4005][4005][4];
int cnt[4005][4005][4];
int main() {
    cin >> N >> M;
    assert(N <= 2000);
    ll total = 0;
    rep(i, M) {
        cin >> A[i];
        if (i) {
            total += abs(A[i] - A[i - 1]);
            int p = A[i], q = A[i - 1];
            if (p > q) swap(p, q);
            int d = q - p - 1;

            {
                int e = d - (2000 + p - q);
                cnt[2000 + (p - d + 1)][q][0]++;
                cnt[2000 + (p - d + 1)][q + 1][0]--;
                cnt[2000 + p + 1][q][0]--;
                cnt[2000 + p + 1][q + d + 1][0]++;
                cnt[2000 + p + 2][q + 1][0]++;
                cnt[2000 + p + 2][q + d + 1][0]--;

                sum[2000 + (p - d + 1)][q][0] += e;
                sum[2000 + (p - d + 1)][q + 1][0] -= e;
                sum[2000 + p + 1][q][0] -= e;
                sum[2000 + p + 1][q + d + 1][0] += e;
                sum[2000 + p + 2][q + 1][0] += e;
                sum[2000 + p + 2][q + d + 1][0] -= e;
            }

            if (d >= 2) {
                int e = (d - 1) - (-(2000 + p + 1) - q);
                cnt[2000 + p + 1][q + d - 2][1]++;
                cnt[2000 + p + 2][q + d - 2][1]--;
                cnt[2000 + p + 1][q - 1][1]--;
                cnt[2000 + p + d + 1][q - 1][1]++;
                cnt[2000 + p + 2][q - 2][1]++;
                cnt[2000 + p + d + 1][q - 2][1]--;

                sum[2000 + p + 1][q + d - 2][1] += e;
                sum[2000 + p + 2][q + d - 2][1] -= e;
                sum[2000 + p + 1][q - 1][1] -= e;
                sum[2000 + p + d + 1][q - 1][1] += e;
                sum[2000 + p + 2][q - 2][1] += e;
                sum[2000 + p + d + 1][q - 2][1] -= e;
            }

            if (d >= 3) {
                int e = (d - 2) - (-(2000 + p + 1) + (q - 1));
                cnt[2000 + p + 1][q - (d - 2)][2]++;
                cnt[2000 + p + 2][q - (d - 2)][2]--;
                cnt[2000 + p + 1][q][2]--;
                cnt[2000 + p + d][q][2]++;
                cnt[2000 + p + 2][q + 1][2]++;
                cnt[2000 + p + d][q + 1][2]--;

                sum[2000 + p + 1][q - (d - 2)][2] += e;
                sum[2000 + p + 2][q - (d - 2)][2] -= e;
                sum[2000 + p + 1][q][2] -= e;
                sum[2000 + p + d][q][2] += e;
                sum[2000 + p + 2][q + 1][2] += e;
                sum[2000 + p + d][q + 1][2] -= e;
            }

            if (d >= 2) {
                int e = (d - 1) - (2000 + p + (q - 1));
                cnt[2000 + p - (d - 2)][q - 1][3]++;
                cnt[2000 + p - (d - 2)][q - 2][3]--;
                cnt[2000 + p + 1][q - 1][3]--;
                cnt[2000 + p + 1][q - d - 1][3]++;
                cnt[2000 + p + 2][q - 2][3]++;
                cnt[2000 + p + 2][q - d - 1][3]--;

                sum[2000 + p - (d - 2)][q - 1][3] += e;
                sum[2000 + p - (d - 2)][q - 2][3] -= e;
                sum[2000 + p + 1][q - 1][3] -= e;
                sum[2000 + p + 1][q - d - 1][3] += e;
                sum[2000 + p + 2][q - 2][3] += e;
                sum[2000 + p + 2][q - d - 1][3] -= e;
            }
        }
    }
    rep(i, 4000) rep(j, 4000) {
        cnt[i][j + 1][0] += cnt[i][j][0];
        sum[i][j + 1][0] += sum[i][j][0];

        cnt[i + 1][j][2] += cnt[i][j][2];
        sum[i + 1][j][2] += sum[i][j][2];
    }
    rep(i, 4000) rep(j, 4000) {
        cnt[i + 1][j][0] += cnt[i][j][0];
        sum[i + 1][j][0] += sum[i][j][0];

        cnt[i][j + 1][2] += cnt[i][j][2];
        sum[i][j + 1][2] += sum[i][j][2];
    }
    rep(i, 4000) rep(j, 4000) {
        cnt[i + 1][j + 1][0] += cnt[i][j][0];
        sum[i + 1][j + 1][0] += sum[i][j][0];

        cnt[i + 1][j + 1][2] += cnt[i][j][2];
        sum[i + 1][j + 1][2] += sum[i][j][2];
    }

    rep(i, 4000) rev(j, 4000) {
        cnt[i + 1][j][1] += cnt[i][j][1];
        sum[i + 1][j][1] += sum[i][j][1];

        cnt[i][j - 1][3] += cnt[i][j][3];
        sum[i][j - 1][3] += sum[i][j][3];
    }
    rep(i, 4000) rev(j, 4000) {
        cnt[i][j - 1][1] += cnt[i][j][1];
        sum[i][j - 1][1] += sum[i][j][1];

        cnt[i + 1][j][3] += cnt[i][j][3];
        sum[i + 1][j][3] += sum[i][j][3];
    }
    rep(i, 4000) rev(j, 4000) {
        cnt[i + 1][j - 1][1] += cnt[i][j][1];
        sum[i + 1][j - 1][1] += sum[i][j][1];

        cnt[i + 1][j - 1][3] += cnt[i][j][3];
        sum[i + 1][j - 1][3] += sum[i][j][3];
    }

    int Q;
    cin >> Q;
    while (Q--) {
        int S, T;
        cin >> S >> T;

        ll ans = 0;
        ans += sum[S + 2000][T][0];
        ans += (ll)cnt[S + 2000][T][0] * (2000 + S - T);

        ans += sum[S + 2000][T][1];
        ans += (ll)cnt[S + 2000][T][1] * (-(2000 + S) - T);

        ans += sum[S + 2000][T][2];
        ans += (ll)cnt[S + 2000][T][2] * (-(2000 + S) + T);

        ans += sum[S + 2000][T][3];
        ans += (ll)cnt[S + 2000][T][3] * ((S + 2000) + T);

        cout << total - ans << endl;
    }
}

Submission Info

Submission Time
Task F - ワープ
User define
Language C++ (GCC 9.2.1)
Score 430
Code Size 5326 Byte
Status RE
Exec Time 1591 ms
Memory 757228 KiB

Judge Result

Set Name Sample Subtask1 Subtask2 Subtask3 Subtask4 Subtask5 Subtask6
Score / Max Score 0 / 0 0 / 20 50 / 50 100 / 100 280 / 280 0 / 300 0 / 50
Status
AC × 3
RE × 7
AC × 7
AC × 14
AC × 21
RE × 14
AC × 24
RE × 21
Set Name Test Cases
Sample example_1.txt, example_2.txt, example_3.txt
Subtask1 sub1_0.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt
Subtask2 sub2_0.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt
Subtask3 sub2_0.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub3_0.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt
Subtask4 sub2_0.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub3_0.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt, sub4_0.txt, sub4_1.txt, sub4_2.txt, sub4_3.txt, sub4_4.txt, sub4_5.txt, sub4_6.txt
Subtask5 sub1_0.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub5_0.txt, sub5_1.txt, sub5_2.txt, sub5_3.txt, sub5_4.txt, sub5_5.txt, sub5_6.txt
Subtask6 example_1.txt, example_2.txt, example_3.txt, sub1_0.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub1_5.txt, sub1_6.txt, sub2_0.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt, sub3_0.txt, sub3_1.txt, sub3_2.txt, sub3_3.txt, sub3_4.txt, sub3_5.txt, sub3_6.txt, sub4_0.txt, sub4_1.txt, sub4_2.txt, sub4_3.txt, sub4_4.txt, sub4_5.txt, sub4_6.txt, sub5_0.txt, sub5_1.txt, sub5_2.txt, sub5_3.txt, sub5_4.txt, sub5_5.txt, sub5_6.txt, sub6_0.txt, sub6_1.txt, sub6_2.txt, sub6_3.txt, sub6_4.txt, sub6_5.txt, sub6_6.txt
Case Name Status Exec Time Memory
example_1.txt AC 874 ms 754772 KiB
example_2.txt AC 826 ms 754484 KiB
example_3.txt AC 820 ms 754640 KiB
sub1_0.txt RE 107 ms 3328 KiB
sub1_1.txt RE 106 ms 3312 KiB
sub1_2.txt RE 106 ms 3332 KiB
sub1_3.txt RE 108 ms 3308 KiB
sub1_4.txt RE 104 ms 3304 KiB
sub1_5.txt RE 105 ms 3408 KiB
sub1_6.txt RE 105 ms 3288 KiB
sub2_0.txt AC 1389 ms 756556 KiB
sub2_1.txt AC 1380 ms 756544 KiB
sub2_2.txt AC 1379 ms 756624 KiB
sub2_3.txt AC 1378 ms 756620 KiB
sub2_4.txt AC 1383 ms 756624 KiB
sub2_5.txt AC 1376 ms 756640 KiB
sub2_6.txt AC 1378 ms 756616 KiB
sub3_0.txt AC 1415 ms 756872 KiB
sub3_1.txt AC 1409 ms 756912 KiB
sub3_2.txt AC 1406 ms 756840 KiB
sub3_3.txt AC 1417 ms 756924 KiB
sub3_4.txt AC 1415 ms 756904 KiB
sub3_5.txt AC 1407 ms 756832 KiB
sub3_6.txt AC 1405 ms 756928 KiB
sub4_0.txt AC 1587 ms 757180 KiB
sub4_1.txt AC 1583 ms 757216 KiB
sub4_2.txt AC 1591 ms 757188 KiB
sub4_3.txt AC 1581 ms 757164 KiB
sub4_4.txt AC 1585 ms 757120 KiB
sub4_5.txt AC 1586 ms 757216 KiB
sub4_6.txt AC 1591 ms 757228 KiB
sub5_0.txt RE 115 ms 3380 KiB
sub5_1.txt RE 106 ms 3400 KiB
sub5_2.txt RE 105 ms 3388 KiB
sub5_3.txt RE 105 ms 3248 KiB
sub5_4.txt RE 105 ms 3284 KiB
sub5_5.txt RE 107 ms 3296 KiB
sub5_6.txt RE 107 ms 3376 KiB
sub6_0.txt RE 107 ms 3296 KiB
sub6_1.txt RE 104 ms 3300 KiB
sub6_2.txt RE 106 ms 3344 KiB
sub6_3.txt RE 105 ms 3308 KiB
sub6_4.txt RE 111 ms 3272 KiB
sub6_5.txt RE 106 ms 3304 KiB
sub6_6.txt RE 106 ms 3272 KiB