QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#19815#1809. Find the MST for Gridconqueror_of_zky#WA 6ms5628kbC++142.2kb2022-02-11 15:57:032022-05-06 07:13:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-06 07:13:29]
  • 评测
  • 测评结果:WA
  • 用时:6ms
  • 内存:5628kb
  • [2022-02-11 15:57:03]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l); i <= (r); i ++)
#define per(i, r, l) for(int i = (r); i >= (l); i --)
#define trv(i, u, v) for(int i = head[u], v = e[i].to; i; v = e[i = e[i].nxt].to)
#define fi first
#define se second
#define all(s) s.begin(), s.end()
#define sz(s) (int)(s.size())
#define lb(s) ((s) & -(s))
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
mt19937_64 hua(time(0));
template<typename T> inline bool chkmx(T &x, T y) {return x < y ? x = y, 1 : 0;}
template<typename T> inline bool chkmn(T &x, T y) {return y < x ? x = y, 1 : 0;}
template<int T> using A = array<int, T>;

inline int read() {
	int x = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar()) if(c == '-')  f = 0;
	for(; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	return f ? x : -x;
}
const int maxn = 1e5;
const int inf = 1e9;
int n, m, a[maxn + 5], b[maxn + 5], c[maxn + 5], d[maxn + 5];
int x[maxn + 5], y[maxn + 5];
ll ans;
void solve() {
	rep(i, 1, n) x[i] = a[i] - c[i];
	rep(i, 1, m) y[i] = d[i] - b[i];
	sort(y + 1, y + m + 1);
	rep(i, 1, n) {
		int cnt = y + m + 1 - lower_bound(y + 1, y + m + 1, x[i]);
		ans += 1ll * a[i] * cnt;
	}
	
	
	rep(i, 1, m) x[i] = b[i] - d[i];
	rep(i, 1, n) y[i] = c[i] - a[i];
	sort(y + 1, y + n + 1);
	rep(i, 1, m) {
		int cnt = y + n + 1 - lower_bound(y + 1, y + n + 1, x[i]);
		ans += b[i] * cnt;
	}
	
	rep(i, 1, n) swap(a[i], c[i]);
	rep(i, 1, m) swap(b[i], d[i]);
	rep(i, 1, n) x[i] = a[i] - c[i];
	rep(i, 1, m) y[i] = d[i] - b[i];
	sort(y + 1, y + m + 1);
	rep(i, 1, n) {
		int cnt = y + m + 1 - upper_bound(y + 1, y + m + 1, x[i]);
		ans += 1ll * a[i] * cnt;
	}
	
	rep(i, 1, m) x[i] = b[i] - d[i];
	rep(i, 1, n) y[i] = c[i] - a[i];
	sort(y + 1, y + n + 1);
	rep(i, 1, m) {
		int cnt = y + n + 1 - upper_bound(y + 1, y + n + 1, x[i]);
		ans += b[i] * cnt;
	}
}
int main() {
	//freopen("in.txt", "r", stdin);
	n = read(), m = read();
	rep(i, 2, n) a[i] = read(); a[1] = inf;
	rep(i, 1, m) b[i] = read();
	rep(i, 1, n) c[i] = read();
	rep(i, 2, m) d[i] = read(); d[1] = inf;
	solve();
	cout << ans - min(a[1] + b[1], c[1] + d[1]) << '\n'; 
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3680kb

input:

2 3
1
1 3 6
1 4
1 2

output:

17

result:

ok answer is '17'

Test #2:

score: 0
Accepted
time: 1ms
memory: 3620kb

input:

4 3
1 13 15
3 6 11
3 6 6 11
9 17

output:

173

result:

ok answer is '173'

Test #3:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

2 3
968418
431416 672770 680574
552160 624114
892963 920468

output:

7379244

result:

ok answer is '7379244'

Test #4:

score: 0
Accepted
time: 3ms
memory: 3688kb

input:

3 2
118689 499942
45109 920606
327638 468788 633079
149844

output:

2587886

result:

ok answer is '2587886'

Test #5:

score: 0
Accepted
time: 2ms
memory: 5628kb

input:

3 3
171815 356177
228641 395286 978617
702666 792511 913883
169671 180825

output:

6127710

result:

ok answer is '6127710'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3596kb

input:

3 4
7184 620183
79780 130738 487556 848611
232818 371375 944380
216990 936022 983989

output:

8438293

result:

ok answer is '8438293'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

4 3
51985 136713 427919
188504 312899 371141
145631 227550 731171 833357
160747 573726

output:

5493218

result:

ok answer is '5493218'

Test #8:

score: 0
Accepted
time: 3ms
memory: 3616kb

input:

7 5
175926 428984 582661 582839 820907 920776
322080 633264 798688 811692 823441
54339 220390 250291 330054 371881 842806 885846
441838 703407 941999 978043

output:

37806417

result:

ok answer is '37806417'

Test #9:

score: 0
Accepted
time: 3ms
memory: 3552kb

input:

9 8
128346 182079 277192 434166 657634 823595 853129 940474
707 292710 363361 404369 494504 600358 796392 872568
95548 456201 544335 582372 695261 827770 860026 928632 994917
160921 262851 319385 402844 959489 982420 982699

output:

69150796

result:

ok answer is '69150796'

Test #10:

score: 0
Accepted
time: 3ms
memory: 3748kb

input:

7 7
390088 456793 662796 811369 863901 997123
174627 272343 294065 376553 692154 797046 972456
76702 401950 405513 470226 553463 682122 826908
106803 293625 306370 544706 575270 828264

output:

44304980

result:

ok answer is '44304980'

Test #11:

score: 0
Accepted
time: 3ms
memory: 3684kb

input:

7 7
270291 358878 423424 570235 772251 986431
45308 139839 229024 246723 264432 343181 778141
74325 203070 240656 330399 549696 621374 856760
57300 464802 541216 680595 915767 928652

output:

38909585

result:

ok answer is '38909585'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3548kb

input:

9 8
255312 314659 435326 436128 464484 507292 727368 807464
103501 293849 414270 474996 838635 874511 965537 971583
204709 230699 251434 494013 570649 664454 741866 906547 910970
419608 622510 678766 703125 809137 903338 923781

output:

76479411

result:

ok answer is '76479411'

Test #13:

score: 0
Accepted
time: 3ms
memory: 3612kb

input:

90 15
1569 7812 15560 17225 19225 21440 63872 67763 73422 92647 98398 106522 110109 112693 114487 122224 154052 155699 158235 174012 175798 176730 177959 187239 190924 206750 217783 229076 247986 249130 260497 265264 269052 285315 291931 327499 331976 337424 338165 352012 363333 370568 370943 373038...

output:

1149258768

result:

ok answer is '1149258768'

Test #14:

score: 0
Accepted
time: 2ms
memory: 3564kb

input:

573 762
3338 5419 5645 6157 7116 8262 8393 8399 8717 13114 13179 15879 16350 18675 18777 20835 21329 23456 25635 25875 26218 27153 27503 27953 28438 30788 32050 35179 35273 35416 44186 47640 48200 49720 51545 51756 52851 52886 53427 56462 56541 57087 58701 61500 63233 63449 63650 64330 71582 72299 7...

output:

425651347739

result:

ok answer is '425651347739'

Test #15:

score: -100
Wrong Answer
time: 6ms
memory: 3828kb

input:

5523 5571
187 355 377 524 572 593 624 947 957 973 1147 1287 1861 1911 2165 2436 2560 2806 2875 2924 3028 3035 3090 3210 4339 4372 4520 4531 4580 5137 5395 5686 5710 5802 5994 6494 6816 6919 7012 7349 7609 7783 7833 7943 8016 8242 8327 8422 8475 8489 8608 8619 8659 8686 8709 8738 9353 9423 9651 9692 ...

output:

17959925408192

result:

wrong answer expected '30844827296192', found '17959925408192'