QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227136#7197. 24 Data Structures You've Ever Heard OfPPP#WA 3ms19428kbC++174.5kb2023-10-26 23:22:262023-10-26 23:22:26

Judging History

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

  • [2023-10-26 23:22:26]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:19428kb
  • [2023-10-26 23:22:26]
  • 提交

answer

#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

typedef long long ll;
typedef long double ld;
const int maxN = 2005;
int n;
int p[5];
int a[maxN];
int pref[maxN][maxN];
ll solve() {

    memset(pref, 0, sizeof pref);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pref[i][j] = pref[i - 1][j];
        }
        for (int j = a[i]; j <= n; j++) pref[i][j]++;
    }

    if (abs(p[1] - p[3]) != 1) {
        //fix 2, 3
        ll ans = 0;
        for (int x = 1; x <= n; x++) {
            for (int y = x + 1; y <= n; y++) {
                if ((p[1] < p[3]) == (a[x] < a[y])) {
                    int at_least = 1;
                    int at_most = n;
                    int coef = 1;
                    if (p[1] > p[2]) at_most = min(at_most, a[x]);
                    else at_least = max(at_least, a[x]);


                    if (p[3] > p[2]) at_most = min(at_most, a[y]);
                    else at_least = max(at_least, a[y]);



                    coef = (pref[y - 1][at_most] - pref[y - 1][at_least - 1]) - pref[x][at_most] - pref[x][at_least - 1];

                    at_least = 1;
                    at_most = n;

                    if (p[1] > p[4]) at_most = min(at_most, a[x]);
                    else at_least = max(at_least, a[x]);

                    if (p[3] > p[4]) at_most = min(at_most, a[y]);
                    else at_least = max(at_least, a[y]);
                    coef *= (pref[n][at_most] - pref[y][at_most]) - (pref[n][at_least - 1] - pref[y][at_least - 1]);
                    ans += coef;
                }
            }
        }
        return ans;
    }


    if (abs(p[1] - p[4]) != 1) {
        //fix 2, 3
        ll ans = 0;
        for (int x = 1; x <= n; x++) {
            for (int y = x + 1; y <= n; y++) {
                if ((p[2] < p[3]) == (a[x] < a[y])) {
                    int at_least = 1;
                    int at_most = n;
                    int coef = 1;
                    if (p[2] > p[1]) at_most = min(at_most, a[x]);
                    else at_least = max(at_least, a[x]);


                    if (p[3] > p[1]) at_most = min(at_most, a[y]);
                    else at_least = max(at_least, a[y]);



                    coef = pref[x - 1][at_most] - pref[x - 1][at_least - 1];
//                    if (x == 2 && y == 3) {
//                        cout << at_most << " " << at_least << " " << coef << " ?? " << endl;
//                    }
                    at_least = 1;
                    at_most = n;

                    if (p[2] > p[4]) at_most = min(at_most, a[x]);
                    else at_least = max(at_least, a[x]);


                    if (p[3] > p[4]) at_most = min(at_most, a[y]);
                    else at_least = max(at_least, a[y]);
                    coef *= (pref[n][at_most] - pref[y][at_most]) - (pref[n][at_least - 1] - pref[y][at_least - 1]);
                    ans += coef;
                }
            }
        }
        return ans;
    }
    assert(false);
    return -228;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    cin >> n;
    for (int i = 1; i <= 4; i++) {
        cin >> p[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    if (abs(p[2] - p[4]) != 1) {
        reverse(p + 1, p + 5);
        reverse(a + 1, a + n + 1);
    }

    if (abs(p[1] - p[3]) != 1) {
        cout << solve();
        return 0;
    }

    if (abs(p[1] - p[4]) != 1) {
        cout << solve();
        return 0;
    }

    if (p[1] > p[4]) reverse(p + 1, p + 5);
    assert(p[1] == 2 && p[2] == 4 && p[3] == 1 && p[4] == 3);
    ll ALL = 0;


    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            pref[i][j] = pref[i - 1][j];
        }
        for (int j = a[i]; j <= n; j++) pref[i][j]++;
    }

//    cout << " HI " << endl;

    for (int x = 1; x <= n; x++) {
        for (int y = x + 1; y <= n; y++) {
            if (a[x] < a[y]) continue;
            ll coef = (pref[y - 1][n] - pref[y - 1][a[x]]) - (pref[x][n] - pref[x][a[x]]);
            coef *= (pref[n][n] - pref[n][a[x]]) - (pref[y][n] - pref[y][a[x]]);
            ALL += coef;
        }
    }
//    cout << ALL << " ?? " << endl;
    swap(p[2], p[4]);
    ALL -= solve();
//    cout << ALL << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 3ms
memory: 19296kb

input:

5
1 2 3 4
1 2 3 4 5

output:

5

result:

ok 1 number(s): "5"

Test #2:

score: 0
Accepted
time: 3ms
memory: 19272kb

input:

8
1 3 2 4
1 2 5 6 3 4 7 8

output:

16

result:

ok 1 number(s): "16"

Test #3:

score: 0
Accepted
time: 0ms
memory: 19428kb

input:

1
1 2 3 4
1

output:

0

result:

ok 1 number(s): "0"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 19272kb

input:

10
1 2 3 4
1 4 6 9 8 5 3 7 10 2

output:

-68

result:

wrong answer 1st numbers differ - expected: '18', found: '-68'