fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define int long long
  5. using namespace std;
  6. const long long oo=1e18;
  7. const int mod=1e9+7;
  8. int B=320;
  9. void home()
  10. {
  11.     freopen("main.inp","r",stdin);
  12.     freopen("main.out","w",stdout);
  13. }
  14. bool bit(int x,int i){return (x>>i)&1;}
  15. struct Query
  16. {
  17.     int st,l,r,k,id;
  18.     bool operator<(const Query &ot)const
  19.     {
  20.         if(l/B!=ot.l/B)return l/B<ot.l/B;
  21.         if((l/B)%2==0)return r<ot.r;
  22.         else return r>ot.r;
  23.     }
  24. }Q[100005];
  25. int n,q;
  26. int a[100005];
  27. int ans[100005],sum[450],cnt[450],on[100005],vals[100005];
  28. pair<int,int>val[100005];
  29. void add(int i)
  30. {
  31.     int id=val[i].se;
  32.     sum[id/B]+=val[i].fi;
  33.     cnt[id/B]++;on[id]=true;
  34. }
  35. void del(int i)
  36. {
  37.     int id=val[i].se;
  38.     sum[id/B]-=val[i].fi;
  39.     cnt[id/B]--;on[id]=false;
  40. }
  41. int Find(int id,int k)
  42. {
  43.     int l=id,d=0;
  44.     for(;l/B==id/B&&l<=n;l++)
  45.     {
  46.         if(!on[l])continue;
  47.         if(a[l]>k)return l-id;
  48.         k-=a[l],d++;
  49.     }
  50.     if(l>n)return n-id+1;
  51.     l/=B;
  52.     while(l*B<=n&&sum[l]<=k)
  53.     {
  54.         k-=sum[l];d+=cnt[l];
  55.         l++;
  56.     }
  57.     l*=B;
  58.     if(l>n)return n-id+1;
  59.     for(;l<=n;l++)
  60.     {
  61.         if(!on[l])continue;
  62.         if(a[l]>k)return l-id;
  63.         k-=a[l],d++;
  64.     }
  65.     return l-id;
  66. }
  67. void Tcmduc_VOI26()
  68. {
  69.     cin>>n>>q;
  70.     for(int i=1;i<=n;i++)
  71.     {
  72.         cin>>a[i];vals[i]=a[i];
  73.         val[i]={a[i],i};
  74.     }
  75.     sort(val+1,val+n+1);
  76.     sort(vals+1,vals+n+1);
  77.     for(int i=1;i<=q;i++)
  78.     {
  79.         int st,l,r,k;cin>>st>>l>>r>>k;
  80.         int posL=lower_bound(vals+1,vals+n+1,l)-vals;
  81.         int posR=upper_bound(vals+1,vals+n+1,r)-vals-1;
  82.         Q[i]={st,posL,posR,k,i};
  83.     }
  84.     sort(Q+1,Q+q+1);
  85.     int L=1,R=0;
  86.     for(int i=1;i<=q;i++)
  87.     {
  88.         auto [st,l,r,k,id]=Q[i];
  89.         while(L>l)add(--L);
  90.         while(R<r)add(++R);
  91.         while(L<l)del(L++);
  92.         while(R>r)del(R--);
  93.         ans[id]=Find(st,k);
  94.     }
  95.     for(int i=1;i<=q;i++)cout<<ans[i]<<'\n';
  96. }
  97. signed main()
  98. {
  99.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);//home();
  100.     Tcmduc_VOI26();
  101.     return 0;
  102. }
  103.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Kswr3T
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!