QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#319254#6673. Be Careful 2IshyTL 11742ms728340kbC++148.2kb2024-02-02 11:07:102024-02-02 11:07:10

Judging History

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

  • [2024-02-02 11:07:10]
  • 评测
  • 测评结果:TL
  • 用时:11742ms
  • 内存:728340kb
  • [2024-02-02 11:07:10]
  • 提交

answer

// Sea, You & Me
#include<bits/stdc++.h>
#define LL long long
#define DB double
#define MOD 998244353
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
#define lowbit(x) ((-x) & x)
#define MP make_pair
#define MT make_tuple
#define VI vector<int>
#define VL vector<LL>
#define VII VI::iterator
#define VLI VL::iterator
#define all(x) x.begin(), x.end()
#define EB emplace_back
#define PII pair<int, int>
#define SI set<int>
#define SII SI::iterator
#define fi first
#define se second
using namespace std;
template<typename T> void chkmn(T &a, const T b) { if(a > b) a = b; }
template<typename T> void chkmx(T &a, const T b) { if(a < b) a = b; }
void Inc(int &a, const int &b) { ((a += b) >= MOD) && (a -= MOD); }
void Dec(int &a, const int &b) { ((a -= b) < 0) && (a += MOD); }
void Mul(int &a, const int &b) { a = 1LL * a * b % MOD; }
void Sqr(int &a) { a = 1LL * a * a % MOD; }
int inc(const int &a, const int &b) { return (a + b >= MOD) ? a + b - MOD : a + b; }
int dec(const int &a, const int &b) { return (a - b < 0) ? a - b + MOD : a - b; }
int mul(const int &a, const int &b) { return 1LL * a * b % MOD; }
int sqr(const int &a) { return 1LL * a * a % MOD; }
int qwqmi(int x, int k = MOD - 2)
{
	int res = 1;
	while(k)
	{
		if(k & 1) Mul(res, x);
		k >>= 1, Sqr(x);
	}
	return res;
}
template<typename T> void read(T &x)
{
	x = 0;
	int f = 1;
	char ch = getchar();
	while(!isdigit(ch))
	{
		if(ch == '-')
			f = -1;
		ch = getchar();
	}
	while(isdigit(ch))
	{
		x = (x << 1) + (x << 3) + (ch ^ 48);
		ch = getchar();
	}
	x = x * f;
}
const int N = 5e3 + 5;
const int INF = 1e9 + 7;
int n, m, K;
PII p[N];
struct Rec
{
	int l, r, u, d;
	Rec(const int L = 0, const int R = 0, const int U = 0, const int D = 0){
		l = L, r = R, u = U, d = D;
	}
	friend bool operator < (Rec A, Rec B)
	{
		if(A.l != B.l) return A.l < B.l;
		if(A.r != B.r) return A.r < B.r;
		if(A.u != B.u) return A.u < B.u;
		return A.d < B.d;
	}
	friend bool operator == (Rec A, Rec B)
	{
		return (A.l == B.l && A.r == B.r && A.u == B.u && A.d == B.d);
	}
	friend bool operator != (Rec A, Rec B)
	{
		return (A.l != B.l || A.r != B.r || A.u != B.u || A.d != B.d);
	}
}a[N * N]; int cnt;
map<PII, int> mp;
map<int, int> mpx;
map<int, int> mpy;
int X[N], xcnt;
int Y[N], ycnt;
set<int> Sx[N];
set<int> Sy[N];
int calc_coef(int l, int r, int u, int d)
{
	PII w = MP(l, d), x = MP(l, u), y = MP(r, u), z = MP(r, d);
	int vw = mp[w], vx = mp[x], vy = mp[y], vz = mp[z];
	int v1 = 0, v2 = 0, v3 = 0, v4 = 0;
	SII it1 = Sx[mpx[l]].upper_bound(d); if(it1 != Sx[mpx[l]].end() && *it1 < u) v1 = 1;
	SII it2 = Sy[mpy[u]].upper_bound(l); if(it2 != Sy[mpy[u]].end() && *it2 < r) v2 = 1;
	SII it3 = Sx[mpx[r]].upper_bound(d); if(it3 != Sx[mpx[r]].end() && *it3 < u) v3 = 1;
	SII it4 = Sy[mpy[d]].upper_bound(l); if(it4 != Sy[mpy[d]].end() && *it4 < r) v4 = 1;
//	for(int i = l + 1; i < r; ++i)
//		if(mpx.count(i))
//		{
//			SII it = Sx[mpx[i]].upper_bound(d);
//			if(it != Sx[mpx[i]].end() && *it < u)
//				assert(0);
//		}
	if(l == r && u == d) return -1;
	if(l == r) return (v1 == 0 ? 1 : 0);
	if(u == d) return (v2 == 0 ? 1 : 0);
	int cnt = vw + vx + vy + vz;
	int emp = (v1 == 0 && v2 == 0 && v3 == 0 && v4 == 0);
	// choose 0
	int res = (v1 == 1 && v2 == 1 && v3 == 1 && v4 == 1); 
	if(cnt == 0) return res;
	// choose 1
	if(vw == 1) res -= (v1 == 0 && v4 == 0 && v2 == 1 && v3 == 1);
	if(vx == 1) res -= (v1 == 0 && v2 == 0 && v3 == 1 && v4 == 1);
	if(vy == 1) res -= (v2 == 0 && v3 == 0 && v1 == 1 && v4 == 1);
	if(vz == 1) res -= (v3 == 0 && v4 == 0 && v1 == 1 && v2 == 1);
//	if(l == 1 && r == 4 && u == 3 && d == 2) cerr << "!!! " << res << '\n';
	if(cnt == 1) return res;
	// choose 2
	if(vw == 1 && vx == 1) res -= (v1 == 0 && v2 == 0 && v4 == 0 && v3 == 1);
	if(vx == 1 && vy == 1) res -= (v1 == 0 && v2 == 0 && v3 == 0 && v4 == 1);
	if(vy == 1 && vz == 1) res -= (v2 == 0 && v3 == 0 && v4 == 0 && v1 == 1);
	if(vz == 1 && vw == 1) res -= (v1 == 0 && v3 == 0 && v4 == 0 && v2 == 1);
	if(vw == 1 && vy == 1) res += emp;
	if(vx == 1 && vz == 1) res += emp;
	if(cnt == 2) return res;
	// choose 3
	if(vw == 1 && vx == 1 && vy == 1) res -= emp;
	if(vx == 1 && vy == 1 && vz == 1) res -= emp;
	if(vy == 1 && vz == 1 && vw == 1) res -= emp;
	if(vz == 1 && vw == 1 && vx == 1) res -= emp;
	if(cnt == 3) return res;
	if(vw == 1 && vx == 1 && vy == 1 && vz == 1) res += emp;
	return res;
}
const int inv6 = qwqmi(6);
const int inv4 = qwqmi(4);
const int inv30 = qwqmi(30);
int sum2(int x) { return mul(inv6, mul(x, mul(x + 1, 2 * x + 1))); } 
int sum3(int x) { return mul(inv4, mul(sqr(x), sqr(x + 1))); } 
int sum4(int x) { return mul(inv30, mul(x, mul(x + 1, mul(2 * x + 1, dec(mul(3, mul(x, x + 1)), 1))))); }
int cx[2], cy[2]; // w(len) = c[0] + c[1] * len
int func(int l, int r)
{
	assert(l <= r);
	l = max(0, l - 1);
	int c2 = mul(cx[0], cy[0]);
	int c3 = inc(mul(cx[0], cy[1]), mul(cx[1], cy[0]));
	int c4 = mul(cx[1], cy[1]);
	int res = 0;
	Inc(res, mul(c2, dec(sum2(r), sum2(l))));
	Inc(res, mul(c3, dec(sum3(r), sum3(l))));
	Inc(res, mul(c4, dec(sum4(r), sum4(l))));
	return res;
};
int calc_val(int l, int r, int u, int d)
{
	assert(l <= r);
	assert(d <= u);
	--l, ++r, --d, ++u;
	if(l < 0 || d < 0 || r > n || u > m) return 0;
	int mn = max(r - l, u - d), mx = min(n, m);
	vector<int> vec = {mn, mx + 1, r + 1, u + 1, n - l + 1, m - d + 1};
	sort(vec.begin(), vec.end());
	auto coef = [&](int len, int l, int r, int lim, int *c)
	{
		if(len <= lim - l && len <= r) c[0] = l - r + 1, c[1] = 1;
		else if(len <= lim - l && len > r) c[0] = l + 1, c[1] = 0;
		else if(len > lim - l && len <= r) c[0] = lim - r + 1, c[1] = 0;
		else c[0] = lim + 1, c[1] = -1;
		if(c[0] < 0) c[0] += MOD;
		if(c[1] < 0) c[1] += MOD;
	};
	int res = 0;
	for(int i = 0; i + 1 < (int)vec.size(); ++i)
	{
		if(vec[i] < mn) continue;
		if(vec[i] > mx) break;
		if(vec[i] == vec[i + 1]) continue;
		coef(vec[i], l, r, n, cx);
		coef(vec[i], d, u, m, cy);
		Inc(res, func(vec[i], vec[i + 1] - 1));
	}
	return res;
}
int main()
{
	read(n), read(m), read(K);
	for(int i = 1; i <= K; ++i)
	{
		read(p[i].fi), read(p[i].se);
		X[++xcnt] = p[i].fi;
		Y[++ycnt] = p[i].se;
		mp[p[i]] = 1;
	}
	sort(p + 1, p + K + 1);
	sort(X + 1, X + K + 1);
	sort(Y + 1, Y + K + 1);
	xcnt = unique(X + 1, X + K + 1) - (X + 1);
	ycnt = unique(Y + 1, Y + K + 1) - (Y + 1);
	for(int i = 1; i <= xcnt; ++i) mpx[X[i]] = i;
	for(int i = 1; i <= ycnt; ++i) mpy[Y[i]] = i;
	for(int i = 1; i <= K; ++i)
	{
		Sx[mpx[p[i].fi]].insert(p[i].se);
		Sy[mpy[p[i].se]].insert(p[i].fi);
	}
	for(int i = 1; i <= K; ++i)
	{
		int U = INF, D = -INF;
		a[++cnt] = Rec(p[i].fi, p[i].fi, p[i].se, p[i].se);
		for(int j = i + 1; j <= K; ++j)
		{
			if(p[j].se >= U || p[j].se <= D) continue;
			int mn = min(p[i].se, p[j].se);
			int mx = max(p[i].se, p[j].se);
			a[++cnt] = Rec(p[i].fi, p[j].fi, mx, mn);
			a[++cnt] = Rec(p[i].fi, p[j].fi, mx, D);
			a[++cnt] = Rec(p[i].fi, p[j].fi, U, mn);
			a[++cnt] = Rec(p[i].fi, p[j].fi, U, D);
			if(p[j].se >= p[i].se) U = p[j].se;
			if(p[j].se <= p[i].se) D = p[j].se;
		}
	}
	sort(a + 1, a + cnt + 1);
	cnt = unique(a + 1, a + cnt + 1) - (a + 1);
	cx[0] = n + 1, cx[1] = -1, cy[0] = m + 1, cy[1] = -1;
	int ans = func(1, min(n, m));
	for(int i = 1; i <= cnt; ++i)
	{
		if(a[i].u == INF) continue;
		if(a[i].d == -INF) continue;
//		cerr << a[i].l << ' ' << a[i].r << ' ' << a[i].u << ' ' << a[i].d << '\n';
		int c = calc_coef(a[i].l, a[i].r, a[i].u, a[i].d);
		int f = calc_val(a[i].l, a[i].r, a[i].u, a[i].d);
		if(c < 0) c += MOD;
		Inc(ans, mul(c, f));
		
//		cerr << c << ' ' << f << '\n';
	}
	printf("%d", ans);
	return 0;
}

/* 
5 5 4
1 1
2 3
4 2
1 2
*/

/*
10 10 12
1 4
2 4
5 2
2 2
3 3
2 8
3 9
1 2
1 8
1 9
7 6
2 5
ans : 1115
*/

/*
9145 9419 12
123 456
223 456
547 285
294 284
375 385
217 857
348 925
14 274
1104 853
184 953
794 603
2234 5678
ans : 921360185
*/

/*
100 100 40
13 77
15 17
74 83
25 51
49 65
60 19
83 86
71 87
47 2
7 31
34 65
84 32
58 69
89 92
67 61
49 79
92 74
76 87
96 37
45 21
56 84
53 72
16 30
59 41
55 9
31 72
86 53
95 53
80 87
51 99
55 83
13 93
3 90
61 83
65 27
66 57
52 34
3 46
6 30
92 80
ans : 12252760
*/


詳細信息

Test #1:

score: 100
Accepted
time: 19ms
memory: 395748kb

input:

3 3 1
2 2

output:

21

result:

ok 1 number(s): "21"

Test #2:

score: 0
Accepted
time: 20ms
memory: 395792kb

input:

5 5 2
2 1
2 4

output:

126

result:

ok 1 number(s): "126"

Test #3:

score: 0
Accepted
time: 24ms
memory: 395768kb

input:

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

output:

161

result:

ok 1 number(s): "161"

Test #4:

score: 0
Accepted
time: 11ms
memory: 395748kb

input:

15 38 6
12 6
7 15
2 18
3 19
4 2
14 29

output:

80066

result:

ok 1 number(s): "80066"

Test #5:

score: 0
Accepted
time: 11ms
memory: 395724kb

input:

5145 5419 9
547 285
294 284
375 385
217 857
348 925
14 274
3104 853
184 953
794 603

output:

334363567

result:

ok 1 number(s): "334363567"

Test #6:

score: 0
Accepted
time: 23ms
memory: 395772kb

input:

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

output:

25

result:

ok 1 number(s): "25"

Test #7:

score: 0
Accepted
time: 32ms
memory: 395744kb

input:

9145 9419 12
123 456
223 456
547 285
294 284
375 385
217 857
348 925
14 274
1104 853
184 953
794 603
2234 5678

output:

921360185

result:

ok 1 number(s): "921360185"

Test #8:

score: 0
Accepted
time: 27ms
memory: 395740kb

input:

6 8 4
2 3
3 3
4 2
1 1

output:

444

result:

ok 1 number(s): "444"

Test #9:

score: 0
Accepted
time: 40ms
memory: 396852kb

input:

1000000000 1000000000 5000
1657 1
1644 1
1000000 116362
1186 1
2392 1
1560 1
995 1
2340 1
1916 1
2143 1
1762 1
1000000 116109
1651 1
1000000 116059
2289 1
1000000 115730
1000000 115896
1000000 116499
1608 1
342 1
1000000 116949
1965 1
1000000 114571
1000000 116602
2171 1
1000000 114848
1000000 11627...

output:

80025633

result:

ok 1 number(s): "80025633"

Test #10:

score: 0
Accepted
time: 47ms
memory: 396776kb

input:

1000000000 1000000000 5000
1 2581
1 2273
115983 1000000
116105 1000000
114552 1000000
1 1955
1 2254
116061 1000000
116182 1000000
115783 1000000
114564 1000000
116614 1000000
116229 1000000
116087 1000000
114956 1000000
1 2453
114766 1000000
115750 1000000
115448 1000000
1 1748
116665 1000000
1 2237...

output:

80025633

result:

ok 1 number(s): "80025633"

Test #11:

score: 0
Accepted
time: 1368ms
memory: 396756kb

input:

1000000000 1000000000 5000
824 1
811 1
2300000 114696
353 1
1559 1
727 1
162 1
1507 1
1083 1
1310 1
929 1
1000000 116109
818 1
1000000 116059
1456 1
1000000 115730
1000000 115896
2300000 114833
775 1
2300000 115576
2300000 115283
1132 1
1000000 114571
2300000 114936
1338 1
1000000 114848
2300000 114...

output:

537083161

result:

ok 1 number(s): "537083161"

Test #12:

score: 0
Accepted
time: 43ms
memory: 396692kb

input:

1000000000 1000000000 5000
1 1748
1 1440
115983 1000000
116105 1000000
114552 1000000
1 1122
1 1421
116061 1000000
114516 2300000
115783 1000000
114564 1000000
114948 2300000
114563 2300000
116087 1000000
114956 1000000
1 1620
114766 1000000
115750 1000000
115448 1000000
1 915
114999 2300000
1 1404
...

output:

537083161

result:

ok 1 number(s): "537083161"

Test #13:

score: 0
Accepted
time: 2752ms
memory: 396832kb

input:

1000000000 1000000000 5000
2300000 115622
1000000 116216
1000000 116852
2300000 115827
2300000 116715
1000000 116212
2300000 116390
2300000 114646
1000000 114857
2300000 116404
1000000 116398
1000000 115409
2300000 115721
1000000 116136
2300000 114925
2300000 114869
2300000 116176
1000000 115774
100...

output:

129612365

result:

ok 1 number(s): "129612365"

Test #14:

score: 0
Accepted
time: 36ms
memory: 396644kb

input:

1000000000 1000000000 5000
116495 1000000
116269 1000000
115204 2300000
115724 1000000
116508 1000000
115095 2300000
116712 1000000
114789 2300000
115009 2300000
114795 1000000
115093 2300000
115612 1000000
116183 2300000
116140 2300000
116148 2300000
115608 2300000
115111 1000000
115058 1000000
115...

output:

129612365

result:

ok 1 number(s): "129612365"

Test #15:

score: 0
Accepted
time: 179ms
memory: 396624kb

input:

999999992 999999990 5000
1035170 5702575
3959104 3959104
3887901 7432303
11377527 9794948
6282049 47695
11781994 2037659
11292228 47695
6787467 878630
10441683 5492431
1240650 1129736
5631557 11377527
4863442 5631557
6662382 4863442
8837935 7070049
8837935 10441683
4878561 5702575
5610718 2664505
58...

output:

892807048

result:

ok 1 number(s): "892807048"

Test #16:

score: 0
Accepted
time: 11742ms
memory: 728340kb

input:

999999948 999999898 5000
6033860 10854965
57219333 28077882
18498300 33290576
34559919 16960059
40765867 73389700
9985342 17984966
54717579 26853732
13059544 23513592
56562634 27758141
19776481 35613289
6632028 11929378
14942564 7329745
7337824 13208993
33584464 60460021
13330979 6539654
32561958 58...

output:

461431823

result:

ok 1 number(s): "461431823"

Test #17:

score: -100
Time Limit Exceeded

input:

999999524 999999758 5000
28630401 15905366
49821653 27672863
52823763 29343863
14406464 29362320
3914600 2178863
15379626 31340404
2382937 4856861
26445243 14692595
15255307 8475517
23233725 12911959
8922530 4954657
80413834 44658470
59845170 33233185
38234833 21236207
48814787 27111180
7919671 4397...

output:


result: