1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include<bits/stdc++.h>
#define ll long long
#define INF 2147483647
int inp(){
char c = getchar();
while(c < '0' || c > '9')
c = getchar();
int sum = 0;
while(c >= '0' && c <= '9'){
sum = sum * 10 + c - '0';
c = getchar();
}
return sum;
}
struct Node{
int l;
int r;
int id;
bool operator < (const Node &b) const {
if(l == b.l)
return r > b.r;
return l < b.l;
}
};
std::set<Node> s;
std::multiset<std::pair<int, int> > s2;
int ans[200010], x[200010], t[200010], p[200010], b[200010];
std::set<Node>::iterator operator + (std::set<Node>::iterator it, const int &b){
it++;
return it;
}
std::set<Node>::iterator operator - (std::set<Node>::iterator it, const int &b){
it--;
return it;
}
int id[200010];
bool cmp(int a, int b){
return x[a] < x[b];
}
int main(){
int n = inp();
int m = inp();
for(int i = 1; i <= n; i++){
x[i] = inp();
t[i] = inp();
id[i] = i;
}
std::sort(id + 1, id + n + 1, cmp);
s.insert((Node){x[id[1]], x[id[1]] + t[id[1]], id[1]});
for(int i = 2; i <= n; i++)
if(std::max(s.rbegin()->r + 1, x[id[i]]) <= x[id[i]] + t[id[i]])
s.insert((Node){std::max(s.rbegin()->r + 1, x[id[i]]), x[id[i]] + t[id[i]], id[i]});
for(int i = 1; i <= m; i++){
p[i] = inp();
b[i] = inp();
std::set<Node>::iterator it = s.upper_bound((Node){p[i], p[i]});
it--;
if(it->r >= p[i] && it->l <= p[i]){
t[it->id] += b[i];
ans[it->id]++;
Node nxt = *it;
s.erase(it);
s.insert((Node){nxt.l, nxt.r + b[i], nxt.id});
it = s.find((Node){nxt.l, nxt.r + b[i], nxt.id});
std::multiset<std::pair<int, int> >::iterator it2 = s2.lower_bound(std::make_pair(it->l, 1));
while(it2 != s2.end() && it2->first <= it->r){
t[it->id] += it2->second;
ans[it->id]++;
Node nxt = *it;
s.erase(it);
s.insert((Node){nxt.l, nxt.r + it2->second, nxt.id});
it = s.find((Node){nxt.l, nxt.r + it2->second, nxt.id});
s2.erase(it2);
it2 = s2.lower_bound(std::make_pair(it->l, 1));
}
while((it + 1) != s.end() && it->r >= (it + 1)->r)
s.erase(it + 1);
if((it + 1) != s.end()){
Node nxt = *(it + 1);
s.erase(it + 1);
s.insert((Node){std::max(nxt.l, it->r + 1), nxt.r, nxt.id});
}
} else
s2.insert(std::make_pair(p[i], b[i]));
}
for(int i = 1; i <= n; i++)
printf("%d %d\n", ans[i], t[i]);
}
|
