Блог пользователя Ahnaf.Shahriar.Asif

Автор Ahnaf.Shahriar.Asif, история, 6 лет назад, По-английски

Hello, I have tried a lot to solve MKTHNUM-spoj. For solving this , I have slightly changed the problem statement, it goes like this :

you are asked to find a number such that there are k-1 numbers less than that in range [l...r]

Then I made a merge sort tree and sorted the initial array and Binary Searched it. My time complexity is : O((log2(n))2) . I am getting Runtime Error in case 11 (i think). But couldn't find the bug :'( .

Updt: Now I am getting wrong answer. first 14 test cases ran smmothly

here goes my code :

#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;

const int N = 100099;
vector<int>tree[N*3];
int ara[N+12];

void build(int at ,int l,int r)
{
    if(l == r){
	tree[at].push_back(ara[l]);
	return;
    }
    int mid = (l+r)/2;
    build(at*2,l,mid);
    build(at*2+1,mid+1,r);
	
    merge(all(tree[at*2]),all(tree[at*2+1]),back_inserter(tree[at]));
}

int query(int at,int L,int R,int l,int r,int indx)
{
    if(l > R or r < L)return 0;
    if(L >= l and r >= R){
	int pp = upper_bound(all(tree[at]),ara[indx])-tree[at].begin();
	return pp;
    }
    int mid = (L+R)/2;
    return query(at*2,L,mid,l,r,indx) + query(at*2+1,mid+1,R,l,r,indx);
}

int main()
{
    int n,q,l,r,k;
    scanf("%d%d",&n,&q);
    for(int i= 1; i <= n;i++){
	scanf("%d",&ara[i]);
    }
    build(1,1,n);
    sort(ara+1,ara+1+n);
    while(q--){
	scanf("%d%d%d",&l,&r,&k);
	int high = n,low = 1,mid,ans = -1;
	int cnt = 0;
	while(low <= high){
	    mid = (low+high)/2;
	    int pp = query(1,1,n,l,r,mid);
	    if(k <= pp){
		ans = mid;
		high = mid-1;
	   }
	   else low = mid+1;
	}
    printf("%d\n",ans);
    }	
    return 0;
}
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Ahnaf.Shahriar.Asif (previous revision, new revision, compare).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Ahnaf.Shahriar.Asif (previous revision, new revision, compare).

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I didn't carefully analyze your code, but are you sure that 3 * N is intended for your tree?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I know , N * 4 is safe, but one day, I checked from 1 - 108 that if i * log2(i) >= i * 3 but i saw that, for all i >= 7 , i * 3 >= i * log2(i), you can check it out , just run a loop from 1 to 108 :)

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, it is true that segment tree takes exactly 2N nodes. But it is not true that they all nodes should take indexes in range [1, 2N], indexes can go outside of that range.

      Anyway, from your explanation it seems like you think segment tree takes nodes. Which is wrong actually, it takes exactly 2N nodes, but if you index them like — for node x, left node has value 2x and right node has value 2x + 1 — then the indexes can go outside of that bound.

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The sample test case is a tricky one. The problem asks you to give the k'th number, not its index. So this might be one mistake.