Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
27841 沈仲恩 【S】T2 区间 C++ 解答错误 50 38 MS 4732 KB 1325 2024-03-31 10:36:26

Tests(5/10):


#include <bits/stdc++.h> 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]); } int main() { lg[0] = -1; for (int i = 1; i <= 1000000; i++) lg[i] = lg[i >> 1] + 1; scanf("%d %d", &n, &x); if (n > 5000) { printf("0"); return 0; } for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); sx[0][i] = sn[0][i] = a[i]; } 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; }


测评信息: