QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#305715#8016. 不休陀螺oscaryang100 ✓791ms58240kbC++202.6kb2024-01-15 21:06:522024-01-15 21:06:52

Judging History

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

  • [2024-01-15 21:06:52]
  • 评测
  • 测评结果:100
  • 用时:791ms
  • 内存:58240kb
  • [2024-01-15 21:06:52]
  • 提交

answer

#include<bits/stdc++.h>

#define vc vector
#define pb emplace_back
#define pii pair<int, int>
#define mkp make_pair
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define lep(i, a, b) for(int i = (a); i >= (b); i--)

#define int long long

using namespace std;

inline int read() {
	int x = 0, w = 0; char ch = getchar(); while(!isdigit(ch)) w |= (ch == '-'), ch = getchar();
	while(isdigit(ch)) x = x * 10 + (ch ^ 48), ch = getchar(); return w ? -x : x;
}

const int N = 1e6 + 5;

int n, E, ans, len, a[N], b[N], s[N], num[N];
int X[N], Y[N];

namespace bit {
	int tre[N];
	#define lb(x) (x & -x)
	inline void add(int p, int v) { while(p <= len) tre[p] += v, p += lb(p); }
	inline void reset(int p) { while(p <= len) tre[p] = 0, p += lb(p); }
	inline int ask(int p) { int res = 0; while(p) res += tre[p], p -= lb(p); return res; }
}

inline void solve(int l, int r) {
	if(l == r) {
		ans += b[l] >= a[l] && a[l] <= E;
		return ;
	}
	
	int mid = l + r >> 1;
	solve(l, mid); solve(mid + 1, r);
	
	for(int i = mid + 1, x = 0, y = 0; i <= r; i++) {
		if(a[i] > b[i]) x = max(x + a[i] - b[i], y + a[i]), y += a[i] - b[i];
		else x = max(x, y + a[i]);
		X[i] = x; Y[i] = y; 
	}
	for(int i = mid, x = 0, y = 0; i >= l; i--) {
		if(a[i] > b[i]) x = max(x + a[i] - b[i], y + a[i]), y += a[i] - b[i];
		else x = max(x, y + a[i]);
		X[i] = x; Y[i] = y;
	}
	
	// max in right
	for(int i = mid + 1, p = mid, q = mid; i <= r; i++) {
		while(p >= l && X[p] - Y[p] <= X[i] - Y[i]) {
			if(q < p) bit::add(s[p - 1], 1);
			--p;
		}
		while(q >= l && Y[q] + X[i] <= E) {
			if(p < q) bit::add(s[q - 1], 1);
			--q;
		}
		while(q < mid && Y[q + 1] + X[i] > E) {
			++q;
			if(p < q) bit::add(s[q - 1], -1);
		}
		if(max(p, q) < mid) ans += bit::ask(s[i]);
	}
	rep(i, l, mid) bit::reset(s[i - 1]);
	
	// max in left
	for(int i = mid + 1, p = mid + 1, q = mid; i <= r; i++) {
		while(p > l && X[p - 1] - Y[p - 1] <= X[i] - Y[i]) {
			--p;
			if(q < p) bit::add(s[p - 1], -1);
		}
		while(q >= l && X[q] + Y[i] <= E) {
			if(q < p) bit::add(s[q - 1], 1);
			--q;
		}
		while(q < mid && X[q + 1] + Y[i] > E) {
			++q;
			if(q < p) bit::add(s[q - 1], -1);
		}
		if(q + 1 < p) ans += bit::ask(s[i]);
	}
	rep(i, l, mid) bit::reset(s[i - 1]);
}

signed main() {
	n = read(); E = read();
	rep(i, 1, n) a[i] = read();
	rep(i, 1, n) b[i] = read(), num[++len] = s[i] = s[i - 1] + b[i] - a[i];
	
	num[++len] = 0;
	sort(num + 1, num + 1 + len);
	len = unique(num + 1, num + 1 + len) - num - 1;
	rep(i, 0, n) s[i] = lower_bound(num + 1, num + 1 + len, s[i]) - num;
	
	solve(1, n);
	
	cout << ans << endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 6ms
memory: 14028kb

input:

5000 939255322
47952340 92329911 61615795 40122788 47258178 29326499 9822850 42767362 86610596 60318756 52429688 87502511 50194916 96377063 74322128 19511341 28794957 53813791 79075058 35555414 5249682 45174421 101856091 25257909 94697470 45853817 82945426 108415825 41731145 87133877 75167193 598696...

output:

1846283

result:

ok single line: '1846283'

Test #2:

score: 0
Accepted
time: 5ms
memory: 13908kb

input:

4329 694688892
165277824 152780705 114369871 103975989 100188012 147665514 101173335 39350309 37624153 95413467 157561608 10779445 35486823 19200231 55106545 50853515 35799174 92799915 152580135 158388210 132197954 75468895 66543749 104662491 59493152 108170563 22295314 152619070 77921052 105881528 ...

output:

889705

result:

ok single line: '889705'

Test #3:

score: 0
Accepted
time: 0ms
memory: 13960kb

input:

4932 10000000
879202 367773 895593 794951 253764 695611 164309 502290 638542 960084 766095 457948 783698 475707 157847 491793 196608 378324 211974 924944 42162 797172 334660 900879 522660 328814 402169 938267 498991 347773 922727 827106 16528 994043 12381 756925 642283 186848 423956 927655 344750 14...

output:

10724274

result:

ok single line: '10724274'

Test #4:

score: 0
Accepted
time: 4ms
memory: 14024kb

input:

4545 10000000
343712 838600 973396 360269 315252 660011 857231 837695 934030 232383 174532 293701 238344 367417 96713 556096 316705 468048 511763 208940 360904 853055 809137 119764 388946 415546 420603 893876 816501 899208 82913 705704 70043 223366 792251 899049 782406 849921 967761 54994 105919 384...

output:

5542899

result:

ok single line: '5542899'

Subtask #2:

score: 10
Accepted

Test #5:

score: 10
Accepted
time: 715ms
memory: 56152kb

input:

774484 763692678
47702350 34856775 28447988 4178162 45063720 8232662 36845607 27038945 44858289 5952529 39159657 21628528 60199611 5544054 59216841 39287087 43449994 20034684 56440004 11583811 44465341 32347476 49196492 22731571 9481143 11726859 35167370 23103544 23109378 38822668 29778048 58004104 ...

output:

124023429

result:

ok single line: '124023429'

Test #6:

score: 0
Accepted
time: 260ms
memory: 51524kb

input:

1000000 1145141
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 ...

output:

83332166680

result:

ok single line: '83332166680'

Test #7:

score: 0
Accepted
time: 241ms
memory: 51828kb

input:

992939 818293947
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547...

output:

123239741050

result:

ok single line: '123239741050'

Test #8:

score: 0
Accepted
time: 347ms
memory: 42348kb

input:

465467 799236161
42622638 23584326 86376977 8414976 174608385 105068259 117205376 66069589 45334186 26485488 108890505 151260957 99553266 48147603 19096977 106073793 132666378 12827223 111028784 12332572 59117775 144116684 3171518 201636142 9477942 177192562 138404709 163851435 159442454 66257627 21...

output:

108329996778

result:

ok single line: '108329996778'

Test #9:

score: 0
Accepted
time: 84ms
memory: 23384kb

input:

124843 735420077
45527629 54651467 26255396 22796354 28071835 39733708 31423086 53357589 39466167 8531404 6544248 41956875 88563476 35209787 79394835 83294869 6405566 10441298 18228569 37531546 15576446 50840676 46801479 55061678 84914786 45655480 42854190 19546400 62889154 35542879 10332890 4120718...

output:

7792949746

result:

ok single line: '7792949746'

Subtask #3:

score: 10
Accepted

Test #10:

score: 10
Accepted
time: 554ms
memory: 58240kb

input:

1000000 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

output:

99999500000

result:

ok single line: '99999500000'

Test #11:

score: 0
Accepted
time: 464ms
memory: 56952kb

input:

829382 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

68786703753

result:

ok single line: '68786703753'

Test #12:

score: 0
Accepted
time: 394ms
memory: 56196kb

input:

715382 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

51176496753

result:

ok single line: '51176496753'

Test #13:

score: 0
Accepted
time: 102ms
memory: 28144kb

input:

212234 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

4504051185

result:

ok single line: '4504051185'

Subtask #4:

score: 10
Accepted

Test #14:

score: 10
Accepted
time: 86ms
memory: 22352kb

input:

174457 888
0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 1 1 0 1 0 0 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 1 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 1 0 0 0 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1...

output:

329807918

result:

ok single line: '329807918'

Test #15:

score: 0
Accepted
time: 209ms
memory: 32912kb

input:

402729 5000
0 1 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 1 1 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 1 1 0 0 0 1 0 1 1 0 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 ...

output:

4060615624

result:

ok single line: '4060615624'

Test #16:

score: 0
Accepted
time: 518ms
memory: 51236kb

input:

942956 10000
1 0 1 1 1 0 1 0 1 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 1 0 0 1 1 1 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 1 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 0 1 1 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1...

output:

20162916507

result:

ok single line: '20162916507'

Test #17:

score: 0
Accepted
time: 408ms
memory: 49600kb

input:

802501 1000
1 1 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 1 1 0 1 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 1 0 1 1 0 0 1 0 1 0 0 1 0 1 0 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 1 0 1 0 0 0 1 0 1 1 1 0 0 0 1 0 1 0 0 1 1 0 0 1 1 0 1 1 1 1 1 0 0 0 1 0 0 ...

output:

1660083853

result:

ok single line: '1660083853'

Subtask #5:

score: 20
Accepted

Test #18:

score: 20
Accepted
time: 264ms
memory: 35328kb

input:

343922 773619774
0 8292680 5684115 0 0 170056 5385926 0 0 1588575 0 0 10947891 170867 35145 0 0 103085 7231562 0 0 0 0 11128944 0 4872226 0 2879880 7565181 0 8631665 0 5162564 9511835 514165 0 9628987 14357934 174784 0 12400154 0 0 8198218 0 8496060 0 0 0 0 10376826 3523227 0 14548249 0 6840016 0 0 ...

output:

36107528

result:

ok single line: '36107528'

Test #19:

score: 0
Accepted
time: 678ms
memory: 55964kb

input:

822037 644760584
0 2469002 0 5619339 0 0 0 41690 0 2840922 7972819 2323916 0 7218270 0 0 6647344 1095198 0 5412830 6654778 0 4588035 0 5181193 5073101 0 0 0 2371931 2740725 6756043 4534813 1080318 3180435 0 0 0 7537979 0 9432571 3034547 1737404 7266942 0 0 5894473 2658989 0 3648760 6086440 768115 16...

output:

117551199

result:

ok single line: '117551199'

Test #20:

score: 0
Accepted
time: 233ms
memory: 32016kb

input:

318889 580944500
0 53440448 62414510 4444108 16412385 37171101 0 0 65074099 0 0 0 0 0 0 1736666 40422852 25240303 0 0 48581689 0 51050599 0 25918077 0 1579933 0 0 6387116 64336506 0 0 21191911 1157620 0 63412896 28547264 15735514 28842299 56755053 1569652 18413574 0 0 38907260 13487516 3629386 0 0 3...

output:

6426676

result:

ok single line: '6426676'

Test #21:

score: 0
Accepted
time: 488ms
memory: 49520kb

input:

634480 869644773
24926780 0 0 5806548 29345967 0 0 24585164 5082228 0 36723829 0 45565685 38830813 40656683 0 43901325 0 0 24818007 0 9578233 0 29516514 0 45637396 0 17904712 3102583 29421661 0 17144626 0 26616707 20864851 30084372 0 13288472 33594305 10029647 27932498 0 37897745 5476038 0 0 0 0 0 0...

output:

24380270

result:

ok single line: '24380270'

Test #22:

score: 0
Accepted
time: 185ms
memory: 34544kb

input:

343922 773619774
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8425454 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11326 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

1735552293

result:

ok single line: '1735552293'

Test #23:

score: 0
Accepted
time: 462ms
memory: 57056kb

input:

822037 644760584
0 0 0 0 0 3279389 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3763535 0 0 0 0 0 0 0 3461349 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0...

output:

5718720820

result:

ok single line: '5718720820'

Subtask #6:

score: 30
Accepted

Test #24:

score: 30
Accepted
time: 477ms
memory: 42640kb

input:

468676 582048177
6889433 7293342 20676061 15545414 4911497 12352219 8921719 1705801 19695926 25259227 2645394 17518171 19753552 9449377 982708 22479531 1267985 15594372 20685422 9627290 2017543 6459134 18614020 16206301 14962487 12932255 7101003 29140540 6479702 20607124 2540287 15565156 20274141 11...

output:

353280708

result:

ok single line: '353280708'

Test #25:

score: 0
Accepted
time: 791ms
memory: 55772kb

input:

784267 870748450
16640230 34729067 17389326 19816959 33620307 37478599 33913657 25049965 6902010 9380232 7310329 20289065 20894948 36698878 14442257 16359540 28719955 22890081 28478376 3754189 32959471 19507131 24813668 42236708 1945451 16082602 30349832 14901697 28954054 11411772 23608962 31549506 ...

output:

480109294

result:

ok single line: '480109294'

Test #26:

score: 0
Accepted
time: 349ms
memory: 38192kb

input:

362381 806932367
1998992 1594953 1725217 2857016 1122874 2090929 2993571 191305 1573025 2672535 1939866 1432142 1806544 3370274 2180549 2081497 1432017 1957729 207320 2085266 1921419 2009336 1907065 1910662 884271 1887072 1433721 3466028 1976853 1568106 2373768 1562497 1146486 3357210 2143242 199440...

output:

320147189

result:

ok single line: '320147189'

Test #27:

score: 0
Accepted
time: 686ms
memory: 54672kb

input:

677972 743116283
14654866 19965629 33134497 22424942 33594556 8114856 25149702 29975590 31342994 58022893 40342918 20932203 15146022 8605338 55089456 49856121 2941066 53849623 19246055 48804704 3173058 41957054 29981415 16838091 44168911 44677532 53105164 48358902 34377645 4249146 29400964 7246055 5...

output:

306770227

result:

ok single line: '306770227'

Test #28:

score: 0
Accepted
time: 421ms
memory: 42400kb

input:

458893 827508762
36663011 92223323 106548542 647324 99037913 47547432 137915431 54505622 69541989 10691843 113932708 25432404 67685209 28957701 44393252 90019267 58951381 15237406 47038891 61220493 82165280 115267421 130633521 124357788 131281807 48792405 148921282 137582798 105812001 100693484 1484...

output:

125597821

result:

ok single line: '125597821'

Test #29:

score: 0
Accepted
time: 360ms
memory: 34856kb

input:

352598 552392951
477953 72537 92658 281914 179509 124319 138913 46122 123351 156330 385539 397580 280635 230382 210819 255981 389665 48159 303958 241938 337720 81718 194168 168943 464666 258109 295828 163912 385488 110795 194317 92858 212013 74761 360824 92353 234346 256945 26777 112984 145735 47253...

output:

1683912571

result:

ok single line: '1683912571'

Test #30:

score: 0
Accepted
time: 73ms
memory: 19472kb

input:

111704 628642840
13199700 32124349 14698182 24004412 9673344 30567805 9136635 28169543 23827672 33589673 46359443 23996180 43086763 28934606 24514226 35704043 6208097 39610464 20864857 506456 22132660 29798293 43883914 42208348 37316958 5780390 39348069 18672332 7872450 150416 48037426 29816781 1557...

output:

6009983638

result:

ok single line: '6009983638'

Test #31:

score: 0
Accepted
time: 254ms
memory: 34784kb

input:

354793 720027252
40983988 33401041 54567379 52134967 40923834 40282497 42994225 59831114 26162718 18905590 56961601 62454063 49009835 46558527 1159586 39236751 7335945 18017002 14316034 29374227 57791439 40017313 26036290 6883774 46146967 64103491 57564631 70954541 28828703 36466033 37835061 2107130...

output:

17435270706

result:

ok single line: '17435270706'

Test #32:

score: 0
Accepted
time: 219ms
memory: 33628kb

input:

302926 989802465
60020559 11677495 70159984 246480805 13459231 171088896 158477059 127426890 59883990 51253511 145287519 214141415 46450107 92903884 60162590 163860304 40173316 215206023 63409155 163937544 185626997 4423095 207789551 7817602 33103460 67077590 170529891 33157362 159606226 112756694 3...

output:

9322548233

result:

ok single line: '9322548233'