You are not logged in. Please login at www.codechef.com to post your questions!

×

Needed help in spoj K-query question...giving WA..plz help...

include <bits stdc++.h="">

using namespace std;

typedef long long ll;

define pb(a) push_back((a))

define all(x) (x).begin(),(x).end()

define lc ((n)<<1)

define rc ((n)<<1|1)

const int N = 4e5+5; ll n,q; ll a[N]; vector<ll> v; vector<ll> seg[N];

void build(ll n,ll b,ll e) { if(b==e){ seg[n].pb(a[b]); return; } ll mid = (b+e)/2; build(lc,b,mid); build(rc,mid+1,e); merge(seg[lc].begin() , seg[lc].end(), seg[rc].begin(), seg[rc].end(),back_inserter(seg[n])); }

ll query(ll n,ll b,ll e,ll i,ll j,ll v) { if(b>j || e< i) return 0; if(b>=i && e<= j) { { ll k = upper_bound(all(seg[n]), v ) - seg[n].begin(); return k; } } ll mid = (b+e)/2; return query(lc,b,mid,i,j,v) + query(rc,mid+1,e,i,j,v); }

int main() {

scanf("%lld",&n);
for(ll i = 1; i <= n; i ++ )
{
    scanf("%lld",&a[i]);
    v.pb(a[i]);
}

sort(all(v));

//cout<<endl;

build(1,1,n);
scanf("%lld",&q);

while(q--) 
{
    ll l,r,x;
    scanf("%d %d %d",&l,&r,&x);
    ll low = 1, high = n , mid, ans=0 ;
    //cout<<a[x];
    ll p;
    p=query(1,1,n,l,r,x);
    //cout<<query(1,1,n,l,r,x)<<endl;
    //cout<<p;

    if(p==0)
    {
        cout<<r-l+1<<endl;
        continue;
    }

    while(low <= high)
    {
        mid = low + high >> 1;

        ll k = query(1,1,n,l,r,mid);

        if(k >= p) 
        {
            ans = k;
            high = mid-1;
        }
        else low = mid+1;
        //cout<<low<<" "<<high<<" ";
    }
    //cout<<ans<<endl;
   printf("%lld\n",(r-l+1)-ans);
}
return 0;

}

asked 19 May '18, 12:56

shivstr54's gravatar image

3★shivstr54
11
accept rate: 0%

edited 19 May '18, 12:58

Its giving WA...

(19 May '18, 12:57) shivstr543★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,755
×1,038

question asked: 19 May '18, 12:56

question was seen: 90 times

last updated: 19 May '18, 12:58