Run ID | 作者 | 问题 | 语言 | 测评结果 | 分数 | 时间 | 内存 | 代码长度 | 提交时间 |
---|---|---|---|---|---|---|---|---|---|
27842 | 沈仲恩 | 【S】T2 区间 | C++ | 解答错误 | 50 | 159 MS | 31404 KB | 1365 | 2024-03-31 10:42:19 |
#include <bits/stdc++.h> #define int long long using namespace std; int n, x, a[1000005], sn[15][1000005], sx[15][1000005], lg[1000005]; inline int mx(int l, int r) { return max(sx[lg[r - l + 1]][l], sx[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]); } inline int mn(int l, int r) { return min(sn[lg[r - l + 1]][l], sn[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]); } signed main() { lg[0] = -1; for (int i = 1; i <= 1000000; i++) lg[i] = lg[i >> 1] + 1; scanf("%lld %lld", &n, &x); int res = 0; for (int i = 1; i <= n; i++) { scanf("%lld", &a[i]); if (2 * a[i] == x) res++; sx[0][i] = sn[0][i] = a[i]; } if (n > 5000) { printf("%lld", res); return 0; } for (int i = 1; i <= 14; i++) for (int j = 1; j <= n - (1 << i) + 1; j++) sn[i][j] = min(sn[i - 1][j], sn[i - 1][j + (1 << (i - 1))]), sx[i][j] = max(sx[i - 1][j], sx[i - 1][j + (1 << (i - 1))]); long long ans = 0; for (int l = 1; l <= n; l++) for (int r = l; r <= n; r++) if (max(sx[lg[r - l + 1]][l], sx[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]) + min(sn[lg[r - l + 1]][l], sn[lg[r - l + 1]][r - (1 << lg[r - l + 1]) + 1]) == x) ans++; printf("%lld", ans); return 0; }