Mooncrater's blog

By Mooncrater, history, 5 years ago, In English

I am trying to solve this question for two days now.

Gist of the problem:

2D plane is given. Only the first quadrant is to be used. Three type of queries:

  1. add x y: Add a point (x,y) to the coordinate system
  2. remove x y: Remove an already existing point (x,y) from the coordinate system.
  3. find x y: Find the left-most, bottom-most strictly above and on the right of (x,y).

Constraints: $$$1 \leq x,y \leq 1e9$$$ $$$queries \leq 2e5$$$

Approach to solution:

Firstly we need to map the $$$x$$$ co-ordinates to the 2e5 range, so that we can use a segment tree on them. I have done this using the code:

int n;cin>>n ;
f(i,0,n)
{
    cin>>type[i]>>queries[i][0]>>queries[i][1] ;
    v.push_back(queries[i][0]) ;
}
sort(v.begin(),v.end()) ;
int u = unique(v.begin(),v.end())-v.begin() ;
f(i,0,u) mp[v[i]] = i+1 ;

where v is a vector<int>, which saves the x coordinates for each query. Then we sort it, and use unique to find the unique entries. u is the total number of unique x coordinates. Then I use a map<int,int> mp, which stores the 1e9->2e5 mapping.

Now, we can build a segment tree. The segment tree will simply store the maximum y value for a segment. This is useful, as when find x y is called, we can query for the range (map[x]+1,u) for a number having value more than y. So, we get the mapped x.

Now we can store all the y's for a single (mapped) x,by creating an array of sets. I've used set<int> xset[MAXN] for this purpose. We can find the first element greater than some element by using xset[x].upper_bound(y).

All being said, here is the insertion function:

void insert(int node,int l,int r,int x,int y)
{
    if(x<l || r<x) return ;
    if(l==r)
    {
        tree[node] = {x,y} ;
        return ;
    }
    int mid = (l+r)>>1 ;
    insert(2*node+1,l,mid,x,y) ;
    insert(2*node+2,mid+1,r,x,y) ;
    tree[node].Y = max(tree[2*node+1].Y,tree[2*node+2].Y) ;
}

This is used along with the add x y query. tree represents the segment tree, where tree[i].X represents the x value and tree[i].Y represents the y value.

This function is called as:

if(type[i]=="add")
{
    xset[mp[queries[i][0]]].insert(queries[i][1]) ;
    insert(0,0,u,mp[queries[i][0]],queries[i][1]) ;
}

Now the removal function which goes along with the remove x y:

void remove(int node,int l,int r,int x,int y)
{
    if(x<l || r<x) return ;
    if(l==r)
    {
        tree[node] = {0,0} ;
        return ;
    }
    int mid = (l+r)>>1 ;
    remove(2*node+1,l,mid,x,y) ;
    remove(2*node+2,mid+1,r,x,y) ;
    tree[node].Y = max(tree[2*node+1].Y,tree[2*node+2].Y) ;
}

Which is called by the following code:

else if(type[i]=="remove")
{
    xset[mp[queries[i][0]]].erase(queries[i][1]) ;
    remove(0,0,u,mp[queries[i][0]],queries[i][1]) ;
}

And now comes the MVP. The function that goes along with the find x y:

int find_next(int node,int l,int r,int start,int end,int val)
{
    if(tree[node].Y<=val) 
        return 0 ;
    if(end<l || r<start) 
        return 0 ;
    if(l>r) 
        return 0;
    if(l==r)
    {
        return tree[node].X ;
    }
    int mid = (l+r)>>1 ;
    int v1 =  find_next(2*node+1,l,mid,start,end,val) ;
    if(v1==0)
        return find_next(2*node+2,mid+1,r,start,end,val) ;
    return v1 ;
    
}

Here have the range (start,end), where we need to find some element which has a value strictly greater than val. This is done by checking the maximum element of the current range. If it is greater than val, then we're sure we have come to the right place. If not, then we ignore this range by returning a zero.

Now we'd like to go to the left child if possible, because remember, in the find query, we needed the first element strictly greater than y. So, if possible, let's find such element in the left child. If no such element is found in the left child, then we look for the element with the mentioned properties in the right child.

Here is the main code that calls this code:


else //find { int next = find_next(0,0,u,mp[queries[i][0]]+1,u,queries[i][1]) ; // int next = find_next2(0,0,u,mp[queries[i][0]],queries[i][1]) ;//<----- if(next==0) cout<<"-1\n"; else { auto it = xset[next].upper_bound(queries[i][1]) ;//<---- if(it==xset[next].end()) cout<<"-1\n" ; else { cout<<v[next-1]<<" "<<*it<<"\n" ; } } }

Here we try to find the next x element by calling find_next(0,0,u,mp[queries[i][0]]+1,u,queries[i][1]). Look that we're querying for the range mp[queries[i][0]]+1 to u, for values greater than queries[i][1]. If we get a zero as a result, then we know that no such element exists. If it's not a zero, then we can search our y in x's set. If it is not found then set.upper_bound returns an iterator pointing set.end(). So, we can check whether an element strictly greater than y is present in xset[next] or not. If it is present then we output the answer.

Remember f(i,0,u) mp[v[i]] = i+1 ;? This means that v's ith element is mapped as i+1th element. So, we o/p v[next]-1, instead of v[next].

Here is my latest submission. I've submitted ~10 similar solutions in 2 days. I know that I have got the most part of the solution right, but am not able to find what exactly am I doing wrong here.

Any help is appreciated.

  • Vote: I like it
  • -12
  • Vote: I do not like it

»
5 years ago, # |
Rev. 3   Vote: I like it +1 Vote: I do not like it

Have a look at the test case where your code failed. Your code gave the wrong coordinates even before any 'remove' queries were processed, so you didn't need to include the logic for that part, since your blog is already unnecessarily too long. That being said,

The segment tree will simply store the maximum y value for a segment. This is useful, as when find x y is called, we can query for the range (map[x]+1,u) for a number having value more than y. So, we get the mapped x.
There are many problems with this statement. The answer isn't simply the largest y in this range. The actual logic should be 'The first point whose x-coor i > x which has its y-coor > y'. This is one of the problems i found in your logic. Here's a small test case, on which your code is going wrong, which you can use to debug the code yourself:

I/P:
3
add 5 7
add 8 8
find 7 5

O/P:
8 8

Your O/P:
5 7

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sorry. I posted an earlier submission which failed on Test Case 4. I've updated the submission link now, which failed on Test Case 6. It works on the test case you provided.

    Regarding my logic, let me re-iterate.

    Yes, I am saving the maximum value for a range. But I am not using the maximum value to output it. Instead the logic is to find the first element with maximum value greater than y.

    Once we know the element, we can find the next bigger value in it's set, which is present in xset.

    I hope the logic is clear to you now.

    I've tried to follow the editorial.