QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#227990 | #7581. Radar Scanner | Giga_Cronos# | AC ✓ | 202ms | 19244kb | C++23 | 2.2kb | 2023-10-28 10:28:11 | 2023-10-28 10:28:12 |
Judging History
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;
}
詳細信息
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