# CFR 609 F. Frogs and mosquitoes ( Discretization, Segment Tree, Binary Search )

Problem - 609F - Codeforces

First line contains two integers n, m (1 ≤ n, m ≤ 2e5) — the number of frogs and mosquitoes.
Each of the next n lines contains two integers xi, ti (0 ≤ xi, ti ≤ 1e9) — the position and the initial length of the tongue of the i-th frog. It is guaranteed that all xi are different.
Next m lines contain two integers each pj, bj (0 ≤ pj, bj ≤ 1e9) — the position and the size of the j-th mosquito.

O( N lg N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 2e5 );
const int MAXX = int( 1e9 );

int N, M;
int X[ MAXN ], T[ MAXN ];

struct segt {
int lb, rb;
long long maxreach;
segt *lc, *rc;
segt( int _l = 0, int _r = 0 ) {
lb = _l, rb = _r;
maxreach = 0;
lc = rc = NULL;
}
void pull() {
maxreach = max( lc ? lc->maxreach : 0LL, rc ? rc->maxreach : 0LL );
}
void modify( int k, long long v ) {
if( lb + 1 == rb ) {
maxreach = v;
return;
}
int mid = lb + rb >> 1;
if( k < mid ) {
if( not lc ) {
lc = new segt( lb, mid );
}
lc->modify( k, v );
} else {
if( not rc ) {
rc = new segt( mid, rb );
}
rc->modify( k, v );
}
pull();
}
long long query( int k ) {
if( lb + 1 == rb ) {
return maxreach;
}
int mid = lb + rb >> 1;
if( k < mid ) return lc->query( k );
return rc->query( k );
}
int binsearch( int g ) {
if( lb + 1 == rb ) {
return lb;
}
int mid = lb + rb >> 1;
if( lc and lc->maxreach >= g ) {
return lc->binsearch( g );
} else if( rc and rc->maxreach >= g and mid <= g ) {
return rc->binsearch( g );
}
return -1;
}
} *root = new segt( 0, MAXX + 1 );

unordered_map< int, int > eaten;
multiset< pair< int, int > > mosq;

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> M;
for( int i = 0; i < N; ++i ) {
cin >> X[ i ] >> T[ i ];
root->modify( X[ i ], X[ i ] + T[ i ] );
}
for( int i = 0; i < M; ++i ) {
int P, B;
cin >> P >> B;
int fp = root->binsearch( P );
if( fp == -1 ) {
mosq.emplace( P, B );
continue;
}
++eaten[ fp ];
long long r = root->query( fp ) + B;
for( auto it = mosq.lower_bound( make_pair( fp, 0 ) ); it != mosq.end(); ) {
int p, b;
tie( p, b ) = *it;
if( p <= r ) {
it = mosq.erase( it );
r += b;
++eaten[ fp ];
} else {
break;
}
}
root->modify( fp, r );
}
for( int i = 0; i < N; ++i ) {
cout << eaten[ X[ i ] ] << " " << root->query( X[ i ] ) - X[ i ] << "\n";
}
return 0;
}
```