[Codeforces]609F. Frogs and mosquitoes

題目連結：http://codeforces.com/problemset/problem/609/F

可以用青蛙的位置建一顆線段樹，存青哇所能吃到的位置的最大值。
對於這隻蚊子，先二分搜找到最後一隻位置小於蚊子的青蛙，接著區間搜尋哪一隻青蛙是可以吃到且是最左邊的。
開個multiset存哪幾隻蚊子先前沒被吃掉，如果有青蛙可以吃的距離有增加，就找multiset內有沒有蚊子可以被吃掉。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <queue>
#include <vector>
#include <set>
#define lld long long
#define PB push_back
#define F first
#define S second
#define jizz cin.tie(0);ios_base::sync_with_stdio(0);
#define endl '\n'
#define N 200005
#define M (l+r)/2
#define INF 2147483647
using namespace std;
typedef pair<int,int> Pair;
int n,m;
Pair x[N];
int seg[4*N],sol[N],ans[N];
multiset<Pair> s;
void pull(int id){
    seg[id] = max(seg[id<<1],seg[id<<1|1]);
}
void build(int l,int r, int id){
    if(l == r){
        seg[id] = x[sol[l]].F+x[sol[l]].S;
        return;
    }
    build(l,M,id<<1);
    build(M+1,r,id<<1|1);
    pull(id);
}
void update(int l,int r,int k,int id){
    if(r < k || l > k)return;
    if(l == k && r == k){
        seg[id] = x[sol[l]].F + x[sol[l]].S;
        return;
    }
    update(l,M,k,id<<1);
    update(M+1,r,k,id<<1|1);
    pull(id);
}
int query(int l,int r,int ll,int rr,int id,int k){
    if(r < ll || l > rr)return INF;
    if(l >= ll && r <= rr){
        if(seg[id] < k)return INF;
        if(l == r)return l;
        if(seg[id << 1] >= k)return query(l,M,ll,rr,id << 1,k);
        else return query(M+1,r,ll,rr,id << 1|1,k);
    }
    return min(query(l,M,ll,rr,id << 1,k),query(M+1,r,ll,rr,id << 1|1,k));
}

int main(){jizz
    cin >> n >> m;
    for(int i = 1 ; i <= n ; i++)cin >> x[i].F >> x[i].S;
    for(int i = 1; i <= n ; i++)sol[i] = i;
    sort(sol+1,sol+n+1,[](int a,int b){return x[a].F < x[b].F;});
    build(1,n,1);
    for(int i = 0 ; i < m ; i++){
        int a,b;cin >> a >> b;
        int r = n+1,l = 0;
        while(r-l > 1){
            if(x[sol[M]].F > a)r = M;
            else l = M;
        }if(l == 0)continue;
        int tmp = query(1,n,1,l,1,a);
        if(tmp == INF)s.insert({a,b});
        else{
            ans[sol[tmp]]++,x[sol[tmp]].S += b;
            while(!s.empty()){
                auto it = s.upper_bound({x[sol[tmp]].F+x[sol[tmp]].S+1,-1});
                if(it == s.begin())break;
                it--;
                if(it->F < x[sol[tmp]].F)break;
                ans[sol[tmp]]++,x[sol[tmp]].S += it->S;
                s.erase(it);
            }
            update(1,n,tmp,1);
        }
    }
    for(int i = 1; i <= n ; i++)cout << ans[i] << ' ' << x[i].S << endl;
    return 0;
}