QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227137 | #7197. 24 Data Structures You've Ever Heard Of | PPP# | WA | 4ms | 19400kb | C++17 | 4.5kb | 2023-10-26 23:22:44 | 2023-10-26 23:22:44 |
Judging History
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;
}
详细
Test #1:
score: 100
Accepted
time: 4ms
memory: 19284kb
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: 0ms
memory: 19356kb
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: 19400kb
input:
1 1 2 3 4 1
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 19396kb
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'