飞步A轮笔试题3 子数组的和

数组的和"/>

飞步A轮笔试题3 子数组的和

题目3 : 子数组的和

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个包含N个整数的数组A = [A1, A2, ... AN]，请你计算有多少个子数组B = [Ai, Ai+1, ... Aj] (i ≤ j) 满足B中所有整数的和小于K。

输入

第一行包含两个整数N和K。  

第二行包含N个整数A1, A2, ... AN。  

对于30%的数据，1 ≤ N ≤ 1000  

对于另外30%的数据，0 < Ai ≤ 100000    

对于100%的数据，1 ≤ N ≤ 100000 -100000 ≤ Ai ≤ 100000

输出

一个整数，代表答案。

样例输入

4 -1
-2 1 -2 3

样例输出

3

// 后来才知道是树状数组的模版题

#include <iostream>

#include<stdio.h>

#include<algorithm>

#include<string.h>

#include<vector>

#include<queue>

#