QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#227990#7581. Radar ScannerGiga_Cronos#AC ✓202ms19244kbC++232.2kb2023-10-28 10:28:112023-10-28 10:28:12

Judging History

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

  • [2023-10-28 10:28:12]
  • 评测
  • 测评结果:AC
  • 用时:202ms
  • 内存:19244kb
  • [2023-10-28 10:28:11]
  • 提交

answer

/// UH Top
#include <bits/stdc++.h>
#define db(x)   cerr << #x << ':' << (x) << '\n';
#define all(v)  (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
// #define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t int128;
typedef pair<ll, ll> pii;
typedef pair<ld, ll> pdi;
typedef pair<ld, ld> pdd;
typedef pair<ld, pdd> pdp;
typedef pair<string, ll> psi;
typedef pair<ll, string> pls;
typedef pair<string, string> pss;
typedef pair<ll, pii> pip;
typedef pair<pii, pii> ppp;
typedef complex<ld> point;
typedef vector<point> polygon;
typedef vector<ll> vi;
typedef pair<point, int> ppi;
#define prec(n)                                                                \
	cout.precision(n);                                                         \
	cout << fixed
const ll mod = (1e9 + 7);
const ld eps = (1e-9);
const ll oo = (ll)(1e18 + 5);
#define pi   acos(-1)
#define MAXN (ll)(1e3 + 5)

int tot[MAXN][MAXN];
int r[MAXN][MAXN];
int d[MAXN][MAXN];
int f[MAXN][MAXN];

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		for (int i = 0; i < MAXN; i++)
			for (int j = 0; j < MAXN; j++)
				tot[i][j] = r[i][j] = d[i][j] = f[i][j] = 0;
		for (int i = 0; i < n; i++) {
			int x1, y1, x2, y2;
			cin >> x1 >> y1 >> x2 >> y2;
			f[x1][y1]++;
			r[x1][y1]++;
			r[x1][y2 + 1]--;
			d[x1][y1]++;
			d[x2 + 1][y1]--;
			tot[x1][y1]++;
			tot[x1][y2 + 1]--;
			tot[x2 + 1][y1]--;
			tot[x2 + 1][y2 + 1]++;
		}

		ll ans = 0;
		for (int i = 1; i < MAXN; i++)
			for (int j = 1; j < MAXN; j++) {
				r[i][j] += r[i][j - 1];
				d[i][j] += d[i - 1][j];
				tot[i][j] +=
				    (tot[i - 1][j] + tot[i][j - 1] - tot[i - 1][j - 1]);

				ll c3 = f[i][j];
				ll c2 = r[i][j] - f[i][j];
				ll c1 = d[i][j] - f[i][j];
				ll c0 = tot[i][j] - c1 - c2 - c3;
				ans += (c3 * (c3 - 1) * (c3 - 2)) / 6;
				ans += (c3 * (c3 - 1) * (c0 + c1 + c2)) / 2;
				ans += (c3 * (c0 + c1 + c2) * ((c0 + c1 + c2) - 1)) / 2;
				ans += (c1 * (c1 - 1) * c2) / 2;
				ans += (c1 * c2 * (c2 - 1)) / 2;
				ans += (c0 * c1 * c2);
			}

		cout << ans << "\n";
	}

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 19144kb

input:

2
3
3 1 3 1
1 1 2 3
2 1 3 2
5
1 1 4 5
2 1 3 2
2 2 3 3
4 5 4 5
1 2 2 4

output:

0
4

result:

ok 2 number(s): "0 4"

Test #2:

score: 0
Accepted
time: 202ms
memory: 19244kb

input:

10
5
2 1 3 3
1 5 1 5
1 2 2 3
4 1 5 3
1 2 4 4
10
3 3 7 5
3 4 3 4
5 4 6 6
8 1 10 6
6 1 9 8
2 6 8 10
3 2 8 7
5 1 5 8
2 2 7 7
1 1 2 3
100
1 37 28 37
1 5 6 40
9 29 47 30
12 9 12 9
40 14 45 14
13 28 16 34
44 8 46 47
23 9 40 42
13 1 35 17
9 31 46 31
1 10 34 48
5 35 46 50
16 21 28 49
3 6 3 24
5 3 39 28
30 8...

output:

1
31
16256
29932636832595
20948001862043
20395156087285
20094030388871
20143137954387
19922797032244
20114049116806

result:

ok 10 numbers