Lời giải

Chúng ta sẽ lần lượt xử lí các con muỗi theo thứ tự chúng hạ cánh. Giả dụ ta có các đoạn thẳng ~(x_i, y_i)~ trên trục ~Ox~ với ~y_i = x_i + t_i~ (~x_i, t_i~ đã được định nghĩa trong đề bài).

Gọi vị trí mà con muỗi đang xét hạ cánh là ~p~. Dễ thấy ta sẽ phải tìm đoạn thẳng có ~x_i~ là tối thiểu và ~y_i \ge p~. Nếu như ~x_i \le p~ thì chú ếch thứ ~i~ sẽ ăn được con muỗi đang xét. Nếu không ta sẽ thêm con muỗi đó vào một tập hợp gồm những con muỗi chưa bị ăn.

Nếu như chú ếch thứ ~i~ đã ăn được con muỗi này, độ dài lưỡi của chú sẽ tăng lên đúng bằng độ lớn của con muỗi đó. Lúc này, ta sẽ cập nhật đoạn thẳng ~(x_i, y_i)~. Tiếp đó, ta sẽ tìm con muỗi trong tập hợp những con muỗi chưa bị ăn mà ở gần chú ếch thứ ~i~ nhất và kiểm tra xem con muỗi này có thể bị ăn hay không. Ta sẽ lặp lại quá trình này cho đến khi không còn con muỗi nào có thể bị ăn nữa.

Các đoạn thẳng ~(x_i, y_i)~ ta có thể lưu trữ bằng cây IT. Để tìm đoạn thẳng như trên ta sẽ sử dụng kĩ thuật chặt nhị phân trên cây IT. Blog này nói khá rõ nên mình sẽ không nói lại.

Độ phức tạp: ~\mathcal{O}((n + m)\log{n})~

Code mẫu

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long
#define pii pair<int,int>
#define sz(a) (int)a.size()

using namespace std;

const int N = 2e5 + 5;

int n, m;
int x[N], t[N], cnt[N], pos[N];
pii IT[4 * N];
vector<pair<int, pii>> v;
multiset<pii> se;

void build(int id, int l, int r) {
    if (l == r) {
        IT[id] = v[l - 1].second;
        return;
    }

    int m = (l + r) >> 1;
    build(id * 2, l, m);
    build(id * 2 + 1, m + 1, r);

    IT[id] = max(IT[id * 2], IT[id * 2 + 1]);
}

pii get(int id, int l, int r, int val) {    
    if (l == r) return IT[id];

    int m = (l + r) >> 1;
    if (IT[id * 2].first >= val) return get(id * 2, l, m, val);
    return get(id * 2 + 1, m + 1, r, val);
}

void update(int id, int l, int r, int pos, int val) {
    if (l == r) {
        IT[id].first += val;
        return;
    }

    int m = (l + r) >> 1;
    if (pos <= m) update(id * 2, l, m, pos, val);
    else update(id * 2 + 1, m + 1, r, pos, val);

    IT[id] = max(IT[id * 2], IT[id * 2 + 1]);   
}

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for1(i,1,n) {
        cin >> x[i] >> t[i];
        v.push_back({x[i], {x[i] + t[i], i}});
    }

    sort(v.begin(), v.end());
    for1(i,1,n) pos[v[i - 1].second.second] = i;
    build(1, 1, n);

    while (m--) {
        int p, b;
        cin >> p >> b;

        if (IT[1].first < p) {
            se.insert({p, b});
            continue;
        }

        auto frog = get(1, 1, n, p);
        int id = frog.second;
        if (x[id] <= p) {
            update(1, 1, n, pos[id], b);
            cnt[id]++;
            t[id] += b;

            while (sz(se)) {
                auto it = se.lower_bound({x[id], 0});
                if (it == se.end() || (*it).first > x[id] + t[id]) break;

                update(1, 1, n, pos[id], (*it).second);
                cnt[id]++;
                t[id] += (*it).second;
                se.erase(it);
            }
        }
        else se.insert({p, b});
    }

    for1(i,1,n) cout << cnt[i] << " " << t[i] << "\n";

}