Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define INFLL 1223372036854775808
- #define INF 1000000009
- #define MAX_N 500005
- using namespace std;
- typedef long long int lld;
- int t, n, x, a[MAX_N], ans;
- lld s[MAX_N], st[4*MAX_N];
- void insert(int node, int b, int e, int pos, lld v){
- if(b == e) st[node] = v;
- else{
- int med = (b + e) / 2;
- if(pos <= med) insert(2 * node, b, med, pos, v);
- else insert(2 * node + 1, med + 1, e, pos, v);
- st[node] = min(st[2 * node], st[2 * node + 1]);
- }
- }
- int query(int node, int b, int e, lld v){
- if(st[node] > v) return -1;
- if(b == e) return b;
- if(st[2 * node + 1] <= v) return query(2 * node + 1, (b + e) / 2 + 1, e, v);
- return query(2 * node, b, (b + e) / 2, v);
- }
- int main(){
- scanf("%d", &t);
- while(t --){
- scanf("%d %d", &n, &x);
- for(int i = 1; i <= n; i ++)
- scanf("%d", &a[i]);
- s[0] = 0;
- for(int i = 1; i <= n; i ++)
- s[i] = s[i - 1] + a[i];
- for(int i = 0; i < 4*MAX_N; i ++)
- st[i] = INFLL;
- ans = INF;
- for(int i = 1; i <= n; i ++){
- int j = query(1, 0, n, s[i] - x);
- if(j != -1)
- ans = min(ans, i - j);
- insert(1, 0, n, i, s[i]);
- }
- if(ans == INF) ans = -1;
- printf("%d\n", ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment