比赛 期末考试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;
}