用线段树维护每个点覆盖的最小id, 用multiset维护没有吃的蚊子。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = ;
const double eps = 1e-;
const double PI = acos(-); struct Forg {
int x, cnt, id;
LL t;
bool operator < (const Forg& rhs) const {
return x < rhs.x;
}
void print() {
printf("id: %d x: %d cnt: %d t: %lld\n", id, x, cnt, t);
}
}; int n, m;
Forg frog[N];
PII mos[N]; LL anst[N], ansc[N]; vector<LL> oo;
multiset<PII> uneat; int getPosL(LL x) {
return lower_bound(oo.begin(), oo.end(), x) - oo.begin() + ;
}
int getPosR(LL x) {
return upper_bound(oo.begin(), oo.end(), x) - oo.begin();
} namespace SGT {
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
int a[N << ];
void init() {
memset(a, inf, sizeof(a));
}
void update(int L, int R, int val, int l, int r, int rt) {
if(L > R) return;
if(l >= L && r <= R) {
a[rt] = min(a[rt], val);
return;
}
int mid = l + r >> ;
if(L <= mid) update(L, R, val, lson);
if(R > mid) update(L, R, val, rson);
}
int query(int p, int l, int r, int rt) {
if(l == r) return a[rt];
int mid = l + r >> ;
if(p <= mid) return min(a[rt], query(p, lson));
else return min(a[rt], query(p, rson));
}
} int main() {
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) {
scanf("%d%lld", &frog[i].x, &frog[i].t);
frog[i].id = i;
}
sort(frog + , frog + + n);
for(int i = ; i <= m; i++) {
scanf("%d%d", &mos[i].fi, &mos[i].se);
oo.push_back(mos[i].fi);
}
sort(oo.begin(), oo.end());
oo.erase(unique(oo.begin(), oo.end()), oo.end());
SGT::init();
for(int i = ; i <= n; i++) {
SGT::update(getPosL(frog[i].x), getPosR(frog[i].x + frog[i].t), i, , SZ(oo), );
}
for(int i = ; i <= m; i++) {
int p = mos[i].fi, b = mos[i].se;
int who = SGT::query(getPosL(p), , SZ(oo), );
if(who < inf) {
LL pre = frog[who].x + frog[who].t;
frog[who].t += b;
frog[who].cnt++;
LL now = frog[who].x + frog[who].t;
SGT::update(getPosL(pre + ), getPosR(now), who, , SZ(oo), );
while(SZ(uneat)) {
auto it = uneat.lower_bound(mk(pre + , -inf));
if(it == uneat.end()) break;
who = SGT::query(getPosL(it->fi), , SZ(oo), );
if(who >= inf) break;
frog[who].t += it->se;
frog[who].cnt++;
now = frog[who].x + frog[who].t;
SGT::update(getPosL(pre + ), getPosR(now), who, , SZ(oo), );
uneat.erase(it);
}
} else {
uneat.insert(mos[i]);
}
}
for(int i = ; i <= n; i++)
anst[frog[i].id] = frog[i].t, ansc[frog[i].id] = frog[i].cnt;
for(int i = ; i <= n; i++) printf("%lld %lld\n", ansc[i], anst[i]);
return ;
} /*
*/