比赛 EYOI暨SBOI暑假快乐赛5th 评测结果 AAAAAAAAAA
题目名称 回转寿司 最终得分 100
用户昵称 lihaoze 运行时间 0.582 s
代码语言 C++ 内存使用 4.55 MiB
提交时间 2022-06-29 11:48:00
显示代码纯文本
#include <bits/stdc++.h> 

using i64 = long long;

const int N = 1e5+10;
int n, L, R;
i64 s[N], ans;

void cdqdiv(int l, int r) {
    if (l == r) return;
    int mid = l + r >> 1;
    cdqdiv(l, mid), cdqdiv(mid + 1, r);
    std::sort(s + l, s + mid + 1), std::sort(s + mid + 1, s + r + 1);
    int h = l, t = l - 1;
    for (int i = mid + 1; i <= r; ++ i) {
        while (t + 1 <= mid && s[i] - s[t + 1] >= L) ++ t;
        while (h <= mid && s[i] - s[h] > R) ++ h;
        ans += t - h + 1;
    }
    std::sort(s + l, s + r + 1);
}

int main() {
    freopen("bjoi2016_hzss.in", "r", stdin); 
    freopen("bjoi2016_hzss.out", "w", stdout);
    std::cin >> n >> L >> R;
    int x;
    for (int i = 1; i <= n; ++ i) std::cin >> x, s[i] = x + s[i - 1];
    cdqdiv(0, n);
    std::cout << ans << '\n';
    return 0;
}