Segment Game - Codeforces

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

UPDATE : I got a Qlog2(N) solution

Given a number N . then N lines follows some segment L[i] R[i] , where L[i] = left side of segment , R[i]= right side of segment

L1 R1

L2 R2

. . . . . .

LN RN

Then Given Q queries . Then Q lines as follows .

X3 .

For each query you have to answer how many Segment are including the value Xi ( X >= L[i] && X <= R[i] )

Constraint :

1<=N<=10^5

0<=Li , Ri <= 10^9

1<=Q<=10^5

0<=Xi<=10^9

Sample input:

1 6

3 7

5 9

6 9

Sample output:

Explanation : 3rd segment 5-9 , 4th segment 6-9 both including 8 . Because : 8>=5 && 8<=9 , 8>=6 && 8<=9 . So ans is 2 .

How to solve it efficiently ?

My binary search solution

#include<bits/stdc++.h>

using namespace std;

int n,q,xi,ans;

pair<int,int> ar[200000];

int main() {

while(cin>>n)
{

      for(int i=1;i<=n;i++)
        scanf("%d %d",&ar[i].first,&ar[i].second);

    sort(ar+1,ar+n+1);

    cin>>q;

    unordered_map<int,int> val;

    while(q--)
    {
        scanf("%d",&xi);

        if(val.count(xi))
        {
            printf("%d\n",val[xi]);
            continue;
        }

        ans=0;
        int low=0,high=n+1;
        while(high-low>1)
        {
            int mid=(high+low)>>1;
            if(ar[mid].first>xi)
                high=mid;
            else
              low=mid;
        }

        for(int i=1;i<high;i++)
            if(ar[i].second >= xi)
             ans++;

        printf("%d\n",ans);
        val[xi]=ans;

    }

}


return 0;

}

My O( Qlog(N) ) solution

#include<bits/stdc++.h>

using namespace std;

#define debug(...) printf( VA_ARGS )

//#define debug(...) /****nothing****/

#define pb push_back

#define mp make_pair

#define LL long long

int n,q,xi,ans;

pair<int,int> ar[200000];

int main()

{

while(cin>>n)
{

    vector<pair<int,int> > vct;

    for(int i=1;i<=n;i++)
      {
        scanf("%d %d",&ar[i].first,&ar[i].second) ;
       vct.push_back(make_pair(ar[i].first,1)) ;
       vct.push_back(make_pair(ar[i].second+1,-1)) ;
      }

    sort(vct.begin(),vct.end());
    int cnt=0;

    map<int,int> val;

    for(int i=0;i<vct.size();i++)
    {
        cnt+=vct[i].second;
        val[vct[i].first]=cnt;
    }

    cin>>q;

    while(q--)
    {
        scanf("%d",&xi);

        map<int,int>::iterator it=val.upper_bound(xi);
        it--;

        printf("%d\n",it->second);
    }
}


return 0;

}

I used the technique which has been used in this problem ( Two Tv's http://codeforces.net/problemset/problem/845/C )

Comments (5)

Show archived | Write comment?

RejectByLifeCompanyGirls

7 years ago, # |

Always give problem link.

→ Reply

parth_15

I may be wrong but as far as I have seen other's solution, I haven't seen anyone writing binary search like this. you have written as while(high-low>1) but generally all people write while(low<=high) as the first one might get into infinite loop.

blue__legend

I have an offline solution although it doesn't involve segment tree its complexity is better then whats proposed in the blog. O(N log N + Q log N). The main idea is to sort all the ranges and as well as all the queries. After that its kind of sliding window. We will maintain a priority queue. We will process queries sorted in ascending order. Suppose a range is defined by L, R and Qi is current query then we will insert all R into min priority queue PQ for which L<Qi and pop out from PQ while PQ.top()<Qi. Ans for the current query will be the size of the priority queue.

SummerSky

Here is my solution, but I am not sure whether it is correct or not.

At first, for the given N segment lines, we should reduce (or compress) their ranges to [1, 2e+5]. In other words, we just "remap" the ending points of every segment line to some integer belonging to [1, 2e+5]. If you are familiar with C++, you can use "map" provided in STL.

Next, for the 1e+5 queries, we use binary search to find out the minimum value of R_i or L_i that is not less than X_i. Specifically, we implement binary search in L₁, R₁, L₂, R₂, ..., L_N, R_N to find out the minimum value which is larger than or equal to X_i.

Then, for any segment that contain point X_i, it must contain R_i as well, which can be proved by contradiction. Now, the original problem is reduced to find out the number of segment lines that contain R_i. This can be solved by using prefix idea. We adopt an array a[2N], and set a[L_i] = 1 while a[R_i + 1] = - 1. Furthermore, we adopt another array S[2N] to calculate the prefix sum of a[2N]. Then, the value of S[R_i] is just the number of segment lines that contain point R_i.

Building a[2N] and S[2N] has complexity O(N), and implementing binary search has complexity O(logN). Thus, the total complexity turns out to be O(QlogN).

I am not quite confident of the above solution...

Dalgerok

http://codeforces.net/problemset/problem/369/E

coding_is_fun's blog