QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#276369#7189. All Pair Shortest PathPetroTarnavskyi#RE 0ms0kbC++203.1kb2023-12-05 20:26:242023-12-05 20:26:25

Judging History

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

  • [2023-12-05 20:26:25]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-05 20:26:24]
  • 提交

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

output:


result: