QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#416889#8712. Flooding Wallzhoukangyang#12 81ms25360kbC++143.4kb2024-05-22 10:28:312024-05-22 10:28:33

Judging History

This is the latest submission verdict.

  • [2024-05-22 10:28:33]
  • Judged
  • Verdict: 12
  • Time: 81ms
  • Memory: 25360kb
  • [2024-05-22 10:28:31]
  • Submitted

answer

#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define pb emplace_back
using namespace std;
const int N = 1 << 21, mod = 1e9 + 7;
int n;
int a[N], b[N];
int arr[N], tot;
int sum1[N], sum2[N], tag[N];
void adt(int x, int w) {
	sum1[x] = (ll)sum1[x] * w % mod;
	sum2[x] = (ll)sum2[x] * w % mod;
	tag[x] = (ll)tag[x] * w % mod;
}
void push(int x) {
	if(tag[x] != 1) adt(x * 2, tag[x]), adt(x * 2 + 1, tag[x]), tag[x] = 1;
}
void upd(int x) {
	sum1[x] = (sum1[x * 2] + sum1[x * 2 + 1]) % mod;
	sum2[x] = (sum2[x * 2] + sum2[x * 2 + 1]) % mod;
}
inline void add(int x, int L, int R, int l, int r, int w) {
	if(l <= L && R <= r) return adt(x, w), void();
	int mid = (L + R) >> 1;
	push(x);
	if(l <= mid) add(x * 2, L, mid, l, r, w);
	if(r > mid) add(x * 2 + 1, mid + 1, R, l, r, w);
	upd(x);
}
inline int query(int x, int L, int R, int l, int r) {
	if(l <= L && R <= r) return sum1[x];
	push(x);
	int mid = (L + R) >> 1, ret = 0;
	if(l <= mid) ret += query(x * 2, L, mid, l, r);
	if(r > mid) ret += query(x * 2 + 1, mid + 1, R, l, r);
	return ret % mod;
}
void inc(int x, int L, int R, int p, int w) {
	if(L == R) return (sum1[x] += w) %= mod, (sum2[x] += (ll)w * arr[p] % mod) %= mod, void();
	push(x); int mid = (L + R) >> 1; p <= mid ? inc(x * 2, L, mid, p, w) : inc(x * 2 + 1, mid + 1, R, p, w); upd(x);
}
void build(int x, int L, int R) {
	tag[x] = 1;
	if(L == R) return sum1[x] = sum2[x] = (L == 1), void(); 
	int mid = (L + R) >> 1;
	build(x * 2, L, mid), build(x * 2 + 1, mid + 1, R), upd(x);
}
int pw[N];
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	L(i, 1, n) {
		cin >> a[i];
	}
	L(i, 1, n) {
		cin >> b[i];
	}
	L(i, 1, n) {
		arr[++tot] = a[i];
		arr[++tot] = b[i];
	}
	sort(arr + 1, arr + tot + 1);
	tot = unique(arr + 1, arr + tot + 1) - arr - 1;
	L(i, 1, n) {
		a[i] = lower_bound(arr + 1, arr + tot + 1, a[i]) - arr;
		b[i] = lower_bound(arr + 1, arr + tot + 1, b[i]) - arr;
		assert(1 <= a[i] && a[i] <= tot);
		assert(1 <= b[i] && b[i] <= tot);
	}
	pw[0] = 1;
	L(i, 1, n) {
		pw[i] = (ll)pw[i - 1] * 2 % mod;
	}
	L(i, 1, n) if(a[i] > b[i])swap(a[i], b[i]);
	int ans = 0;
	L(tst, 0, 1) {
		build(1, 1, tot);
		int mn = 1;
		L(i, 1, n) {
			if(a[i] > 1) {
			int d = query(1, 1, tot, 1, a[i]);
			add(1, 1, tot, 1, a[i], 0);
			inc(1, 1, tot, a[i], d);
			}

			// // if(mn < a[i]) {
			// // 	int s = 0;
			// // 	L(j, mn, a[i] - 1) {
			// // 		int w = query(1, 1, tot, j, j);
			// // 		(s += w) %= mod;
			// // 		inc(1, 1, tot, j, (mod - w) % mod);
			// // 	}
			// // 	inc(1, 1, tot, a[i], s);
			// // 	mn = a[i];
			// // } 
			
			// if(a[i] > 1) {
			// 	int r = query(1, 1, tot, 1, a[i] - 1);
			// 	assert(r == 0);
			// }
			int s = query(1, 1, tot, 1, b[i]);
			inc(1, 1, tot, b[i], s);
			if(b[i] < tot) add(1, 1, tot, b[i] + 1, tot, 2);
			(ans += (ll) sum2[1] * pw[n - i] % mod) %= mod;
		}
		if(tst == 1) {
			(ans += mod - (ll) n * sum2[1] % mod) %= mod;
		}
		reverse(a + 1, a + n + 1);
		reverse(b + 1, b + n + 1);
	}
	L(i, 1, n) {
		(ans += mod - (ll) (arr[a[i]] + arr[b[i]]) * pw[n - 1] % mod) %= mod;
	}
	cout << ans << '\n';
	return 0;
} 

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 8
Accepted
time: 2ms
memory: 13784kb

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

score: 8
Accepted
time: 0ms
memory: 13764kb

input:

10
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1

output:

21116

result:

ok single line: '21116'

Test #3:

score: 8
Accepted
time: 2ms
memory: 13824kb

input:

1
1
2

output:

0

result:

ok single line: '0'

Test #4:

score: 8
Accepted
time: 0ms
memory: 13760kb

input:

2
1 1
2 2

output:

0

result:

ok single line: '0'

Test #5:

score: 8
Accepted
time: 2ms
memory: 13732kb

input:

3
1 1 1
2 2 2

output:

1

result:

ok single line: '1'

Test #6:

score: 8
Accepted
time: 0ms
memory: 13884kb

input:

3
1 1 1
3 2 3

output:

3

result:

ok single line: '3'

Test #7:

score: 8
Accepted
time: 2ms
memory: 13740kb

input:

3
2 1 1
3 2 3

output:

4

result:

ok single line: '4'

Test #8:

score: 8
Accepted
time: 0ms
memory: 13884kb

input:

3
1 1 2
3 2 3

output:

4

result:

ok single line: '4'

Test #9:

score: 8
Accepted
time: 0ms
memory: 13852kb

input:

4
1 1 2 2
2 2 1 1

output:

6

result:

ok single line: '6'

Test #10:

score: 8
Accepted
time: 0ms
memory: 13848kb

input:

3
1 4 4
3 1 1

output:

2

result:

ok single line: '2'

Test #11:

score: 8
Accepted
time: 0ms
memory: 13880kb

input:

20
801072306 297281669 94099424 745640358 822582129 579751930 776707816 425952653 529794053 256263083 615445445 401366545 990263003 967996508 788867983 916880116 837997768 346996508 623409388 122077161
141734988 448434751 822901346 825591177 388082644 468025968 260356829 1164654 537396602 730502935 ...

output:

840988190

result:

ok single line: '840988190'

Test #12:

score: 8
Accepted
time: 2ms
memory: 13820kb

input:

15
792312195 195812430 401437979 703756992 502275277 612055402 556065888 470806179 556125857 640437896 240743729 861383776 500299988 911972088 161499505
167335533 694282920 379241393 144223073 973249939 83979787 962250505 359871412 130233016 655843497 928153117 542969567 974346871 369758881 962874102

output:

617169726

result:

ok single line: '617169726'

Test #13:

score: 8
Accepted
time: 0ms
memory: 13780kb

input:

20
1 1 2 1 1 1 2 2 2 2 2 1 1 1 1 2 2 1 2 1
2 2 1 2 2 2 1 1 1 1 1 2 2 2 2 1 1 2 1 2

output:

8388630

result:

ok single line: '8388630'

Test #14:

score: 8
Accepted
time: 2ms
memory: 13764kb

input:

15
2 1 1 2 1 2 2 1 2 1 2 1 2 2 1
1 2 2 1 2 1 1 2 1 2 1 2 1 1 2

output:

180241

result:

ok single line: '180241'

Test #15:

score: 8
Accepted
time: 0ms
memory: 13852kb

input:

20
10 3 8 2 5 7 8 3 3 10 5 6 1 2 1 9 10 2 7 10
6 6 2 3 6 10 4 6 7 2 3 3 5 7 2 8 2 1 5 1

output:

78020608

result:

ok single line: '78020608'

Test #16:

score: 8
Accepted
time: 2ms
memory: 13892kb

input:

20
999999992 999999995 999999995 999999998 999999994 999999996 999999992 1000000000 1000000000 999999997 999999999 999999994 999999998 999999992 999999999 1000000000 999999993 999999999 999999996 999999998
999999998 999999998 999999996 999999993 999999996 999999997 1000000000 999999995 999999994 999...

output:

44474368

result:

ok single line: '44474368'

Test #17:

score: 8
Accepted
time: 0ms
memory: 13768kb

input:

20
999999996 10 6 5 4 1 7 9 5 10 1 4 6 3 10 5 3 10 4 999999997
999999997 4 10 7 5 6 2 2 2 7 2 7 3 5 7 1 8 9 2 1000000000

output:

701155847

result:

ok single line: '701155847'

Test #18:

score: 8
Accepted
time: 2ms
memory: 13748kb

input:

11
1 4 2 1 10 6 3 10 1 10 10
6 8 8 7 1 1 1 9 7 9 3

output:

56064

result:

ok single line: '56064'

Test #19:

score: 0
Wrong Answer
time: 0ms
memory: 13776kb

input:

13
999999992 999999993 999999999 999999998 999999994 999999998 999999991 999999991 999999999 999999996 999999994 999999991 999999994
999999994 999999991 999999994 999999997 999999997 1000000000 999999996 999999993 999999992 999999992 999999992 999999998 999999991

output:

288704

result:

wrong answer 1st lines differ - expected: '184256', found: '288704'

Subtask #2:

score: 0
Wrong Answer

Test #23:

score: 17
Accepted
time: 0ms
memory: 13880kb

input:

100
948 425 211 688 416 81 356 602 712 954 117 522 797 75 281 491 662 669 78 156 939 526 929 937 916 619 166 777 48 898 449 278 298 714 668 755 679 38 389 602 195 135 672 833 655 541 473 27 596 274 351 353 598 993 837 246 950 99 179 751 481 843 550 195 964 279 806 82 330 599 124 756 649 838 513 625 ...

output:

164439470

result:

ok single line: '164439470'

Test #24:

score: 17
Accepted
time: 2ms
memory: 13776kb

input:

99
426 562 392 187 480 118 86 459 941 159 104 108 323 616 104 679 464 929 60 387 335 298 540 352 520 152 76 233 69 50 422 839 236 113 79 782 44 253 791 857 393 767 297 267 23 523 274 514 489 58 217 361 408 753 990 491 787 529 759 351 668 348 811 737 764 672 471 115 815 701 604 348 708 512 227 707 20...

output:

295469554

result:

ok single line: '295469554'

Test #25:

score: 17
Accepted
time: 0ms
memory: 13780kb

input:

100
2 1 1 2 2 2 2 1 2 2 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 1 2 1 2 2 1 2 2 2 1 1 1 1 2 2 2 2 2 2 2 1 2 1 1 1 1 2 2 2 2 2 2 1 2 1 2 1 2 2 1 1 2 2 1 1 2 1 2 2 2 1 1 1 1 1 1 2 2 1 2 1 1 2 1 1 1 2 1 1 2 2 1
1 2 2 1 1 1 1 2 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 1 1 1 1 ...

output:

865821460

result:

ok single line: '865821460'

Test #26:

score: 17
Accepted
time: 2ms
memory: 13788kb

input:

97
2 1 2 1 1 1 2 2 2 1 2 1 2 1 2 2 1 1 2 1 1 1 1 2 2 2 1 1 1 2 1 2 2 2 1 1 1 1 2 2 1 1 1 1 1 1 1 1 2 2 1 2 2 1 1 1 2 1 2 2 2 2 2 1 2 1 1 2 1 1 2 2 2 2 1 2 2 1 1 1 1 2 1 2 2 2 1 1 2 2 1 1 2 2 1 2 2
1 2 1 2 2 2 1 1 1 2 1 2 1 2 1 1 2 2 1 2 2 2 2 1 1 1 2 2 2 1 2 1 1 1 2 2 2 2 1 1 2 2 2 2 2 2 2 2 1 1 2 1...

output:

237658155

result:

ok single line: '237658155'

Test #27:

score: 17
Accepted
time: 0ms
memory: 13816kb

input:

100
2 7 7 7 10 10 5 3 8 7 4 4 3 3 9 9 3 4 10 10 2 2 8 6 8 5 8 5 6 5 9 7 9 4 9 4 2 6 4 7 8 8 1 4 2 4 5 3 6 8 2 5 6 1 4 10 10 1 8 7 4 9 2 8 9 5 7 8 9 8 3 5 4 7 6 3 3 1 9 4 1 4 9 1 10 3 3 9 10 7 7 8 5 8 4 10 8 4 1 4
6 8 5 8 9 2 9 9 7 3 10 1 4 10 7 1 4 1 6 8 5 7 7 7 9 3 2 3 1 9 7 2 6 5 7 9 10 1 8 1 2 6 ...

output:

12245240

result:

ok single line: '12245240'

Test #28:

score: 0
Wrong Answer
time: 2ms
memory: 13748kb

input:

100
996 996 998 996 997 996 995 998 991 996 997 1000 992 1000 995 999 1000 999 998 992 995 998 994 996 994 994 995 1000 992 992 1000 994 993 999 997 997 997 1000 991 994 995 999 1000 999 994 992 997 992 999 992 992 1000 999 996 995 992 999 993 997 993 992 997 991 992 992 995 992 994 998 1000 998 100...

output:

396173233

result:

wrong answer 1st lines differ - expected: '699955927', found: '396173233'

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 12
Accepted

Test #57:

score: 12
Accepted
time: 78ms
memory: 19780kb

input:

500000
1 1 1 1 2 2 2 1 1 1 1 1 2 2 1 1 2 2 2 2 1 2 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 2 1 1 2 2 2 2 1 2 2 2 2 1 2 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 2 1 2 1 2 2 1 2 2 2 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 2 2 2 1 2 2 2 2 2 2 2 2 1 1 1 2 1 2 1 1 2 1 2 1 2 2 1 1 2 1 1 1 1 1 2 2 2 2 2 2 1 2 2 1 1 2 1 2 1...

output:

869044223

result:

ok single line: '869044223'

Test #58:

score: 12
Accepted
time: 81ms
memory: 25360kb

input:

499993
1 1 2 1 1 2 1 1 2 1 1 1 2 2 2 2 1 1 1 2 1 1 1 2 2 2 1 1 2 2 1 2 1 2 1 2 1 2 2 2 2 1 1 2 1 2 1 2 2 1 1 2 2 2 2 2 1 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 1 1 2 1 1 2 1 1 1 1 2 1 1 1 2 2 1 1 2 1 1 1 2 2 2 2 1 1 2 1 2 1 2 2 1 2 1 1 1 1 2 1 1 2 1 2 2 1 2 2 2 2 2 1 2 2 1 1 1 2 1 1 1 1 2 1 1 1 2 1 1 2 1 1 1...

output:

480826834

result:

ok single line: '480826834'

Test #59:

score: 12
Accepted
time: 70ms
memory: 24348kb

input:

500000
2 2 1 1 2 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 1 2 1 2 1 2 2 1 1 1 2 1 1 1 1 1 1 2 2 2 2 2 2 2 2 1 2 1 2 1 2 1 1 2 1 1 2 2 2 1 2 2 1 2 2 1 2 2 1 1 1 2 1 1 1 2 2 2 1 1 1 1 1 1 1 2 1 1 1 1 1 2 2 1 2 1 2 2 2 1 2 1 1 2 1 2 1 1 2 2 2 1 2 1 2 2 2 2 2 2 1 1 2 2 2 2 1 1 1 1 1 1 2 2 1 1 1 2 1 2 2 2 1 1 1 2 2...

output:

869044223

result:

ok single line: '869044223'

Test #60:

score: 12
Accepted
time: 70ms
memory: 24292kb

input:

499999
2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 1 1 2 2 2 1 1 1 2 2 2 2 2 1 2 2 1 1 2 2 2 2 1 1 2 1 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1 2 2 2 2 2 1 2 1 2 1 2 1 2 1 1 1 1 1 1 2 1 1 1 1 2 1 2 2 1 1 2 2 1 2 1 1 2 1 2 1 1 2 1 1 1 2 2 1 1 2 2 2 2 2 1 2 1 2 2 1 1 1 2 2 1 1 2 1 1 2 1 1 1 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1...

output:

192864306

result:

ok single line: '192864306'

Subtask #6:

score: 0
Skipped

Dependency #1:

0%