QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#416850#8712. Flooding Wallzhoukangyang#12 117ms26892kbC++142.9kb2024-05-22 09:48:062024-05-22 09:48:06

Judging History

This is the latest submission verdict.

  • [2024-05-22 09:48:06]
  • Judged
  • Verdict: 12
  • Time: 117ms
  • Memory: 26892kb
  • [2024-05-22 09:48:06]
  • 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;
	}
	pw[0] = 1;
	L(i, 1, n) {
		pw[i] = (ll)pw[i - 1] * 2 % mod;
	}
	int ans = 0;
	L(tst, 0, 1) {
		build(1, 1, tot);
		L(i, 1, n) {
			if(a[i] > b[i])swap(a[i], b[i]);
			int d = query(1, 1, tot, 1, a[i]);
			add(1, 1, tot, 1, a[i], 0);
			inc(1, 1, tot, a[i], d);
			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(b + 1, b + tot + 1);
		reverse(a + 1, a + tot + 1);
	}
	L(i, 1, n) {
		(ans += mod - (ll) (arr[a[i]] + arr[b[i]]) * pw[n - 1] % mod) %= mod;
	}
	cout << ans << '\n';
	return 0;
} 

详细

Subtask #1:

score: 0
Runtime Error

Test #1:

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

input:

4
1 1 1 1
2 2 2 2

output:

6

result:

ok single line: '6'

Test #2:

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

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: 0
Runtime Error

input:

1
1
2

output:


result:


Subtask #2:

score: 0
Runtime Error

Test #23:

score: 0
Runtime Error

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:


result:


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: 117ms
memory: 24596kb

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: 117ms
memory: 25272kb

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: 113ms
memory: 24284kb

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: 112ms
memory: 26892kb

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%