提出 #39682004

ソースコード 拡げる

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
typedef long long ll;
using namespace std;
const int mod = 998244353;
void amod(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}
const int maxn = 2e5 + 5;
const ll inf = 1e18;
int n, ans, sum[maxn * 2], tot, cnt[maxn * 2];
ll a[maxn][2], f[maxn][2][2], g[maxn][2][2], lsh[maxn * 2];
void ckmin(ll &x, ll y) {
	x = y < x ? y : x;
}
void solve(int l, int r) {
	if(l == r) {
		return;
	}
	int mid = (l + r) >> 1;
	solve(l, mid);
	solve(mid + 1, r);
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < 2; j++) {
			f[mid + 1][i][j] = a[mid + 1][i] + a[mid + 1][j] * (i != j);
			g[mid][i][j] = a[mid][i] + a[mid][j] * (i != j);
		}
	}
	for(int o = 0; o < 2; o++) {
		for(int i = mid + 2; i <= r; i++) {
			f[i][o][0] = f[i][o][1] = inf;
			for(int x = 0; x < 2; x++) {
				for(int y = 0; y < 2; y++) {
					if(x == y) {
						ckmin(f[i][o][y], f[i - 1][o][x] + a[i][y]);
					}
					else {
						ckmin(f[i][o][y], f[i - 1][o][x] + a[i][x] + a[i][y]);
						ckmin(f[i][o][y], f[i - 1][o][x] + a[i - 1][y] + a[i][y]);
					}
				}
			}
		}
		for(int i = mid - 1; i >= l; i--) {
			g[i][o][0] = g[i][o][1] = inf;
			for(int x = 0; x < 2; x++) {
				for(int y = 0; y < 2; y++) {
					if(x == y) {
						ckmin(g[i][o][y], g[i + 1][o][x] + a[i][y]);
					}
					else {
						ckmin(g[i][o][y], g[i + 1][o][x] + a[i][x] + a[i][y]);
						ckmin(g[i][o][y], g[i + 1][o][x] + a[i + 1][y] + a[i][y]);
					}
				}
			}
		}
	}
	// for(int i = l; i <= mid; i++) {
	// 	for(int x = 0; x < 2; x++) {
	// 		for(int j = mid + 1; j <= r; j++) {
	// 			for(int y = 0; y < 2; y++) {
	// 				amod(ans, min(g[i][0][x] + f[j][0][y], g[i][1][x] + f[j][1][y]) % mod);
	// 			}
	// 		}
	// 	}
	// }
	// return;
	tot = 0;
	for(int i = l; i <= mid; i++) {
		for(int j = 0; j < 2; j++) {
			lsh[++tot] = g[i][0][j] - g[i][1][j];
		}
	}
	for(int i = mid + 1; i <= r; i++) {
		for(int j = 0; j < 2; j++) {
			lsh[++tot] = f[i][1][j] - f[i][0][j];
		}
	}
	sort(lsh + 1, lsh + 1 + tot);
	tot = unique(lsh + 1, lsh + 1 + tot) - lsh - 1;
	for(int i = 1; i <= tot + 1; i++) {
		sum[i] = cnt[i] = 0;
	}
	for(int i = mid + 1; i <= r; i++) {
		for(int j = 0; j < 2; j++) {
			int p = lower_bound(lsh + 1, lsh + 1 + tot, f[i][1][j] - f[i][0][j]) - lsh;
			amod(sum[p], f[i][0][j] % mod);
			amod(cnt[p], 1);
		}
	}
	for(int i = tot; i >= 1; i--) {
		amod(sum[i], sum[i + 1]);
		amod(cnt[i], cnt[i + 1]);
	}
	for(int i = l; i <= mid; i++) {
		for(int j = 0; j < 2; j++) {
			int p = lower_bound(lsh + 1, lsh + 1 + tot, g[i][0][j] - g[i][1][j]) - lsh;
			amod(ans, 1ll * g[i][0][j] % mod * cnt[p] % mod);
			amod(ans, sum[p]);
		}
	}
	
	tot = 0;
	for(int i = l; i <= mid; i++) {
		for(int j = 0; j < 2; j++) {
			lsh[++tot] = g[i][1][j] - g[i][0][j];
		}
	}
	for(int i = mid + 1; i <= r; i++) {
		for(int j = 0; j < 2; j++) {
			lsh[++tot] = f[i][0][j] - f[i][1][j];
		}
	}
	sort(lsh + 1, lsh + 1 + tot);
	tot = unique(lsh + 1, lsh + 1 + tot) - lsh - 1;
	for(int i = 1; i <= tot + 1; i++) {
		sum[i] = cnt[i] = 0;
	}
	for(int i = mid + 1; i <= r; i++) {
		for(int j = 0; j < 2; j++) {
			int p = lower_bound(lsh + 1, lsh + 1 + tot, f[i][0][j] - f[i][1][j]) - lsh;
			amod(sum[p], f[i][1][j] % mod);
			amod(cnt[p], 1);
		}
	}
	for(int i = tot; i >= 1; i--) {
		amod(sum[i], sum[i + 1]);
		amod(cnt[i], cnt[i + 1]);
	}
	for(int i = l; i <= mid; i++) {
		for(int j = 0; j < 2; j++) {
			int p = lower_bound(lsh + 1, lsh + 1 + tot, g[i][1][j] - g[i][0][j]) - lsh;
			amod(ans, 1ll * g[i][1][j] % mod * cnt[p + 1] % mod);
			amod(ans, sum[p + 1]);
		}
	}
}
int main() {
#ifdef DEBUG
	freopen("1.in", "r", stdin);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 0; i < 2; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> a[j][i];
		}
	}
	solve(1, n);
	ans = 2ll * ans % mod;
	for(int i = 1; i <= n; i++) {
		amod(ans, (a[i][0] + a[i][1]) * 3 % mod);
	}
	cout << ans << '\n';
	return 0;
}

提出情報

提出日時
問題 E - All Pair Shortest Paths
ユーザ yanchengzhi
言語 C++ (GCC 9.2.1)
得点 800
コード長 4154 Byte
結果 AC
実行時間 694 ms
メモリ 25408 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 800 / 800
結果
AC × 3
AC × 74
セット名 テストケース
Sample 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt
All 01_sample_01.txt, 01_sample_02.txt, 01_sample_03.txt, 02_small_01.txt, 02_small_02.txt, 02_small_03.txt, 02_small_04.txt, 02_small_05.txt, 02_small_06.txt, 02_small_07.txt, 02_small_08.txt, 02_small_09.txt, 02_small_10.txt, 03_rand_1_01.txt, 03_rand_1_02.txt, 03_rand_1_03.txt, 03_rand_1_04.txt, 03_rand_1_05.txt, 03_rand_1_06.txt, 03_rand_1_07.txt, 03_rand_1_08.txt, 03_rand_1_09.txt, 03_rand_1_10.txt, 04_rand_2_01.txt, 04_rand_2_02.txt, 04_rand_2_03.txt, 04_rand_2_04.txt, 04_rand_2_05.txt, 04_rand_2_06.txt, 04_rand_2_07.txt, 04_rand_2_08.txt, 04_rand_2_09.txt, 04_rand_2_10.txt, 05_max_ans_01.txt, 06_rand_3_01.txt, 06_rand_3_02.txt, 06_rand_3_03.txt, 06_rand_3_04.txt, 06_rand_3_05.txt, 06_rand_3_06.txt, 06_rand_3_07.txt, 06_rand_3_08.txt, 06_rand_3_09.txt, 06_rand_3_10.txt, 07_rand_4_01.txt, 07_rand_4_02.txt, 07_rand_4_03.txt, 07_rand_4_04.txt, 07_rand_4_05.txt, 07_rand_4_06.txt, 07_rand_4_07.txt, 07_rand_4_08.txt, 07_rand_4_09.txt, 07_rand_4_10.txt, 08_rand_5_01.txt, 08_rand_5_02.txt, 08_rand_5_03.txt, 08_rand_5_04.txt, 08_rand_5_05.txt, 08_rand_5_06.txt, 08_rand_5_07.txt, 08_rand_5_08.txt, 08_rand_5_09.txt, 08_rand_5_10.txt, 09_rand_6_01.txt, 09_rand_6_02.txt, 09_rand_6_03.txt, 09_rand_6_04.txt, 09_rand_6_05.txt, 09_rand_6_06.txt, 09_rand_6_07.txt, 09_rand_6_08.txt, 09_rand_6_09.txt, 09_rand_6_10.txt
ケース名 結果 実行時間 メモリ
01_sample_01.txt AC 15 ms 3488 KiB
01_sample_02.txt AC 2 ms 3524 KiB
01_sample_03.txt AC 2 ms 3508 KiB
02_small_01.txt AC 2 ms 3424 KiB
02_small_02.txt AC 2 ms 3456 KiB
02_small_03.txt AC 2 ms 3440 KiB
02_small_04.txt AC 2 ms 3504 KiB
02_small_05.txt AC 2 ms 3536 KiB
02_small_06.txt AC 2 ms 3484 KiB
02_small_07.txt AC 8 ms 3544 KiB
02_small_08.txt AC 3 ms 3444 KiB
02_small_09.txt AC 2 ms 3564 KiB
02_small_10.txt AC 2 ms 3516 KiB
03_rand_1_01.txt AC 383 ms 22236 KiB
03_rand_1_02.txt AC 398 ms 22252 KiB
03_rand_1_03.txt AC 383 ms 22292 KiB
03_rand_1_04.txt AC 383 ms 22240 KiB
03_rand_1_05.txt AC 383 ms 22268 KiB
03_rand_1_06.txt AC 383 ms 22240 KiB
03_rand_1_07.txt AC 382 ms 22268 KiB
03_rand_1_08.txt AC 385 ms 22240 KiB
03_rand_1_09.txt AC 384 ms 22268 KiB
03_rand_1_10.txt AC 382 ms 22272 KiB
04_rand_2_01.txt AC 342 ms 22228 KiB
04_rand_2_02.txt AC 343 ms 22236 KiB
04_rand_2_03.txt AC 349 ms 22240 KiB
04_rand_2_04.txt AC 344 ms 22176 KiB
04_rand_2_05.txt AC 343 ms 22228 KiB
04_rand_2_06.txt AC 342 ms 22292 KiB
04_rand_2_07.txt AC 342 ms 22240 KiB
04_rand_2_08.txt AC 343 ms 22260 KiB
04_rand_2_09.txt AC 344 ms 22256 KiB
04_rand_2_10.txt AC 343 ms 22200 KiB
05_max_ans_01.txt AC 280 ms 22260 KiB
06_rand_3_01.txt AC 674 ms 23800 KiB
06_rand_3_02.txt AC 674 ms 23792 KiB
06_rand_3_03.txt AC 675 ms 23880 KiB
06_rand_3_04.txt AC 673 ms 23792 KiB
06_rand_3_05.txt AC 673 ms 23812 KiB
06_rand_3_06.txt AC 672 ms 23796 KiB
06_rand_3_07.txt AC 674 ms 23728 KiB
06_rand_3_08.txt AC 677 ms 23780 KiB
06_rand_3_09.txt AC 677 ms 23732 KiB
06_rand_3_10.txt AC 672 ms 23816 KiB
07_rand_4_01.txt AC 688 ms 25404 KiB
07_rand_4_02.txt AC 689 ms 25384 KiB
07_rand_4_03.txt AC 690 ms 25364 KiB
07_rand_4_04.txt AC 692 ms 25392 KiB
07_rand_4_05.txt AC 689 ms 25352 KiB
07_rand_4_06.txt AC 689 ms 25316 KiB
07_rand_4_07.txt AC 691 ms 25372 KiB
07_rand_4_08.txt AC 689 ms 25380 KiB
07_rand_4_09.txt AC 694 ms 25352 KiB
07_rand_4_10.txt AC 689 ms 25408 KiB
08_rand_5_01.txt AC 645 ms 23028 KiB
08_rand_5_02.txt AC 664 ms 23732 KiB
08_rand_5_03.txt AC 656 ms 23796 KiB
08_rand_5_04.txt AC 636 ms 23036 KiB
08_rand_5_05.txt AC 633 ms 23024 KiB
08_rand_5_06.txt AC 655 ms 23672 KiB
08_rand_5_07.txt AC 616 ms 22660 KiB
08_rand_5_08.txt AC 627 ms 23212 KiB
08_rand_5_09.txt AC 615 ms 22620 KiB
08_rand_5_10.txt AC 615 ms 22568 KiB
09_rand_6_01.txt AC 676 ms 25060 KiB
09_rand_6_02.txt AC 671 ms 24832 KiB
09_rand_6_03.txt AC 654 ms 24000 KiB
09_rand_6_04.txt AC 636 ms 23136 KiB
09_rand_6_05.txt AC 637 ms 23324 KiB
09_rand_6_06.txt AC 632 ms 23520 KiB
09_rand_6_07.txt AC 617 ms 23108 KiB
09_rand_6_08.txt AC 621 ms 22956 KiB
09_rand_6_09.txt AC 613 ms 22852 KiB
09_rand_6_10.txt AC 620 ms 22900 KiB