Guest User

Untitled

a guest
Jan 2nd, 2014
720
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.27 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define INFLL 1223372036854775808
  3. #define INF 1000000009
  4. #define MAX_N 500005
  5. using namespace std;
  6.  
  7. typedef long long int lld;
  8.  
  9. int t, n, x, a[MAX_N], ans;
  10. lld s[MAX_N], st[4*MAX_N];
  11.  
  12. void insert(int node, int b, int e, int pos, lld v){
  13.   if(b == e) st[node] = v;
  14.   else{
  15.     int med = (b + e) / 2;
  16.     if(pos <= med) insert(2 * node, b, med, pos, v);
  17.     else insert(2 * node + 1, med + 1, e, pos, v);
  18.     st[node] = min(st[2 * node], st[2 * node + 1]);
  19.    
  20.   }
  21. }
  22.  
  23. int query(int node, int b, int e, lld v){
  24.   if(st[node] > v) return -1;
  25.   if(b == e) return b;
  26.   if(st[2 * node + 1] <= v) return query(2 * node + 1, (b + e) / 2 + 1, e, v);
  27.   return query(2 * node, b, (b + e) / 2, v);
  28. }
  29.  
  30. int main(){
  31.  
  32.   scanf("%d", &t);
  33.   while(t --){
  34.  
  35.     scanf("%d %d", &n, &x);
  36.     for(int i = 1; i <= n; i ++)
  37.       scanf("%d", &a[i]);
  38.  
  39.     s[0] = 0;
  40.     for(int i = 1; i <= n; i ++)
  41.       s[i] = s[i - 1] + a[i];
  42.  
  43.     for(int i = 0; i < 4*MAX_N; i ++)
  44.       st[i] = INFLL;
  45.  
  46.     ans = INF;
  47.     for(int i = 1; i <= n; i ++){
  48.       int j = query(1, 0, n, s[i] - x);
  49.       if(j != -1)
  50.         ans = min(ans, i - j);
  51.       insert(1, 0, n, i, s[i]);
  52.     }
  53.     if(ans == INF) ans = -1;
  54.    
  55.     printf("%d\n", ans);
  56.   }
  57.  
  58.   return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment