| 比赛 |
期末考试1 |
评测结果 |
AATWWWWWWW |
| 题目名称 |
Interactive |
最终得分 |
20 |
| 用户昵称 |
LikableP |
运行时间 |
2.640 s |
| 代码语言 |
C++ |
内存使用 |
27.92 MiB |
| 提交时间 |
2026-02-08 11:34:29 |
显示代码纯文本
#include <cstdio>
#include <cctype>
namespace IO {
const int BUFSIZE = 1 << 20;
char buf[BUFSIZE], *p1, *p2;
char gc() {
if (p1 == p2) {
p2 = (p1 = buf) + fread(buf, 1, BUFSIZE, stdin);
if (p1 == p2) return EOF;
}
return *p1++;
}
template <typename T> T read() {
T res = 0, f = 1;
char ch = gc();
for (; !isdigit(ch); ch = gc()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = gc()) res = (res << 3) + (res << 1) + (ch ^ 48);
return res * f;
}
template <typename T> void write(T x, char ed = '\n') {
if (x < 0) x = -x, putchar('-');
static int sta[sizeof(T) << 2], top = 0;
do {
sta[++top] = x % 10;
x /= 10;
} while (x);
while (top) {
putchar(sta[top--] ^ 48);
}
putchar(ed);
}
};
#include <algorithm>
#include <numeric>
#include <ctime>
#define ls(root) root << 1
#define rs(root) root << 1 | 1
typedef long long ll;
const int MAXN = 2e5 + 10;
int n;
ll k, a[MAXN];
int q;
namespace Sub1 {
struct NODE {
ll sum;
ll prefix;
ll suffix;
ll maxsub;
NODE() { sum = prefix = suffix = maxsub = 0; }
} node[MAXN << 2];
void PushUp(int root) {
node[root].sum = node[ls(root)].sum + node[rs(root)].sum;
node[root].prefix = std::max(node[ls(root)].prefix, node[ls(root)].sum + node[rs(root)].prefix);
node[root].suffix = std::max(node[rs(root)].suffix, node[rs(root)].sum + node[ls(root)].suffix);
node[root].maxsub = std::max({node[ls(root)].maxsub, node[rs(root)].maxsub, node[ls(root)].suffix + node[rs(root)].prefix});
}
void Build(int root, int lt, int rt) {
if (lt == rt) {
node[root].sum = node[root].prefix = node[root].suffix = node[root].maxsub = a[lt];
return ;
}
int mid = lt + ((rt - lt) >> 1);
Build(ls(root), lt, mid);
Build(rs(root), mid + 1, rt);
PushUp(root);
}
NODE Query(int root, int lt, int rt, int lq, int rq) {
if (lt == lq && rt == rq) {
return node[root];
}
int mid = lt + ((rt - lt) >> 1);
if (rq <= mid) {
return Query(ls(root), lt, mid, lq, rq);
} else if (lq > mid) {
return Query(rs(root), mid + 1, rt, lq, rq);
} else {
NODE a = Query(ls(root), lt, mid, lq, mid), b = Query(rs(root), mid + 1, rt, mid + 1, rq), ans;
ans.sum = a.sum + b.sum;
ans.prefix = std::max(a.prefix, a.sum + b.prefix);
ans.suffix = std::max(b.suffix, b.sum + a.suffix);
ans.maxsub = std::max({a.maxsub, b.maxsub, a.suffix + b.prefix});
return ans;
}
}
void Print(int root, int lt, int rt) {
printf("[%d, %d]: %lld\n", lt, rt, node[root].maxsub);
if (lt == rt) return ;
int mid = lt + ((rt - lt) >> 1);
Print(ls(root), lt, mid);
Print(rs(root), mid + 1, rt);
}
int Work() {
Build(1, 1, n);
while (q--) {
int x = IO::read<int>();
ll cnt = 0;
for (int left = 1; left <= n; ++left) {
int l = left, r = std::min(n, left + x - 1), ans = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (Query(1, 1, n, left, mid).maxsub >= k) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -1) continue;
cnt += std::min(n, left + x - 1) - ans + 1;
}
IO::write(cnt);
}
return 0;
}
};
namespace Sub2 {
ll partial[MAXN];
int Work() {
std::partial_sum(a + 1, a + n + 1, partial + 1, [](ll x, ll y) -> ll { return x + y; });
auto GetSum = [&](int l, int r) -> ll { return partial[r] - partial[l - 1]; };
while (q--) {
int x = IO::read<int>();
ll cnt = 0;
for (int left = 1; left <= n; ++left) {
int l = left, r = std::min(n, left + x - 1), ans = -1;
while (l <= r) {
int mid = l + ((r - l) >> 1);
if (GetSum(left, mid) >= k) {
ans = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
if (ans == -1) continue;
cnt += std::min(n, left + x - 1) - ans + 1;
}
IO::write(cnt);
}
return 0;
}
};
bool special = true;
int main() {
#ifdef LOCAL
freopen("!input.in", "r", stdin);
freopen("!output.out", "w", stdout);
#else
freopen("tioj_interactive.in", "r", stdin);
freopen("tioj_interactive.out", "w", stdout);
#endif
n = IO::read<int>(), k = IO::read<ll>();
for (int i = 1; i <= n; ++i) {
a[i] = IO::read<ll>();
special &= (a[i] >= 0);
}
q = IO::read<int>();
if (n <= 1000 && q <= 1000) return Sub1::Work();
if (special) return Sub2::Work();
while (q--) {
putchar('0');
putchar('\n');
}
return 0;
}