QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#276369 | #7189. All Pair Shortest Path | PetroTarnavskyi# | RE | 0ms | 0kb | C++20 | 3.1kb | 2023-12-05 20:26:24 | 2023-12-05 20:26:25 |
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int N = 1 << 11;
int n;
int p[4], q[4];
int a[N];
LL prefSum[N][N];
LL ans = 0;
bool intersect(int l1, int r1, int l2, int r2)
{
return l2 < r1 && l1 < r2;
}
LL getSum(int i1, int j1, int i2, int j2)
{
return prefSum[i2][j2] - prefSum[i2][j1]
- prefSum[i1][j2] + prefSum[i1][j1];
}
bool solve(int u1, int u2, int v1, int v2)
{
assert(u1 < u2);
assert(v1 < v2);
FOR(i, 0, n)
{
FOR(j, i + 1, n)
{
if ((q[u1] - q[u2]) * (a[i] - a[j]) < 0)
continue;
VI l(4), r(4);
VI minValue(4), maxValue(4);
for (int v : {v1, v2})
{
if (q[v] < min(q[u1], q[u2]))
{
l[v] = 0;
r[v] = i;
}
else if (q[v] < max(q[u1], q[u2]))
{
l[v] = i + 1;
r[v] = j;
}
else
{
l[v] = j + 1;
r[v] = n;
}
if (v < u1)
{
minValue[v] = 0;
maxValue[v] = min(a[i], a[j]);
}
else if (v < u2)
{
minValue[v] = min(a[i], a[j]) + 1;
maxValue[v] = max(a[i], a[j]);
}
else
{
minValue[v] = max(a[i], a[j]) + 1;
maxValue[v] = n;
}
}
if (intersect(l[v1], r[v1], l[v2], r[v2]))
return false;
if (intersect(minValue[v1], maxValue[v1], minValue[v2], maxValue[v2]))
return false;
ans += getSum(l[v1], minValue[v1], r[v1], maxValue[v1]) * getSum(l[v2], minValue[v2], r[v2], maxValue[v2]);
}
}
cout << ans << "\n";
return true;
}
struct Fenwick
{
int n;
vector<LL> v;
void init(int _n)
{
n = _n;
v.assign(n, 0);
}
void upd(int i, int x)
{
for (; i < n; i |= (i + 1))
v[i] += x;
}
LL query(int i)
{
LL ans = 0;
for (; i >= 0; i = (i & (i + 1)) - 1)
ans += v[i];
return ans;
}
};
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n;
FOR(i, 0, 4)
{
cin >> p[i];
p[i]--;
}
FOR(i, 0, n)
{
cin >> a[i];
a[i]--;
}
if (p[0] > 1)
{
FOR(i, 0, 4)
p[i] = 3 - p[i];
FOR(i, 0, n)
a[i] = n - 1 - a[i];
}
FOR(i, 0, n)
prefSum[i + 1][a[i] + 1] = 1;
FOR(i, 1, n + 1)
FOR(j, 1, n + 1)
prefSum[i][j] += prefSum[i][j - 1];
FOR(j, 1, n + 1)
FOR(i, 1, n + 1)
prefSum[i][j] += prefSum[i - 1][j];
FOR(i, 0, 4)
q[p[i]] = i;
if (solve(1, 2, 0, 3))
return 0;
if (solve(1, 3, 0, 2))
return 0;
if (solve(0, 2, 1, 3))
return 0;
assert(p[0] == 1 && p[1] == 3 && p[2] == 0 && p[3] == 3);
VI indices(n);
iota(ALL(indices), 0);
sort(ALL(indices), [&](int i, int j) {return a[i] > a[j];});
Fenwick fw;
FOR(i, 0, n)
{
VI cnt(n);
FOR(j, i + 1, n)
{
if (a[j] < a[i])
{
cnt[i + 1]++;
cnt[j]--;
}
}
FOR(i, 1, n)
cnt[i] += cnt[i - 1];
fw.init(n);
for (int j : indices)
{
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 010 001 100