Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #undef NDEBUG
- #ifdef SU1
- #define _GLIBCXX_DEBUG
- #endif
- #include <bits/stdc++.h>
- #define forn(i, n) for (int i = 0; i < int(n); i++)
- #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
- #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
- #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
- #define all(a) (a).begin(), (a).end()
- #define sz(a) int((a).size())
- #define pb(a) push_back(a)
- #define mp(x, y) make_pair((x), (y))
- #define x first
- #define y second
- using namespace std;
- typedef long long li;
- typedef long double ld;
- typedef pair<int, int> pt;
- template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
- template<typename X> inline X sqr(const X& a) { return a * a; }
- const int INF = int(1e9);
- const li INF64 = li(1e18);
- const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
- #ifdef SU1
- #define LLD "%lld"
- #else
- #define LLD "%I64d"
- #endif
- typedef pair<pair<int, li>, pt> frog;
- const int N = 200200;
- int n, m;
- frog a[N];
- pt b[N];
- inline bool read() {
- if (!(cin >> n >> m)) return false;
- forn(i, n) assert(scanf("%d" LLD, &a[i].x.x, &a[i].x.y) == 2), a[i].y = mp(i, 0);
- forn(i, m) assert(scanf("%d%d", &b[i].x, &b[i].y) == 2);
- return true;
- }
- li t[4 * N];
- void build(int idx, int l, int r) {
- if (l == r)
- t[idx] = a[l].x.x + a[l].x.y;
- else {
- int md = (l + r) >> 1;
- build(2 * idx + 1, l, md);
- build(2 * idx + 2, md + 1, r);
- t[idx] = max(t[2 * idx + 1], t[2 * idx + 2]);
- }
- }
- inline bool cmpId(const frog& a, const frog& b) { return a.y.x < b.y.x; }
- li max(int idx, int l, int r, int lf, int rg) {
- if (l == lf && r == rg)
- return t[idx];
- int md = (l + r) >> 1;
- li ans = -1;
- if (lf <= md) ans = max(ans, max(2 * idx + 1, l, md, lf, min(md, rg)));
- if (md < rg) ans = max(ans, max(2 * idx + 2, md + 1, r, max(lf, md + 1), rg));
- return ans;
- }
- int find(int idx, int l, int r, li x) {
- if (l == r) return l;
- int md = (l + r) >> 1;
- if (t[2 * idx + 1] >= x) return find(2 * idx + 1, l, md, x);
- return find(2 * idx + 2, md + 1, r, x);
- }
- void upd(int idx, int l, int r, int pos, li val) {
- if (l == r) return void(t[idx] = val);
- int md = (l + r) >> 1;
- if (pos <= md) upd(2 * idx + 1, l, md, pos, val);
- else upd(2 * idx + 2, md + 1, r, pos, val);
- t[idx] = max(t[2 * idx + 1], t[2 * idx + 2]);
- }
- #ifdef SU1
- //#define LOG
- #endif
- inline void solve() {
- sort(a, a + n);
- build(0, 0, n - 1);
- multiset<pt> mos;
- forn(i, m) {
- int x = b[i].x, w = b[i].y;
- int idx = int(lower_bound(a, a + n, mp(mp(x + 1, -1ll), mp(-1, -1))) - a);
- li maxv = idx ? max(0, 0, n - 1, 0, idx - 1) : -1;
- //cerr << "$$$" << i << ' ' << maxv << endl;
- if (maxv < x) {
- mos.insert(mp(x, w));
- continue;
- }
- int f = find(0, 0, n - 1, x);
- assert(a[f].x.x <= x && x <= a[f].x.x + a[f].x.y);
- a[f].x.y += w;
- upd(0, 0, n - 1, f, a[f].x.x + a[f].x.y);
- a[f].y.y++;
- #ifdef LOG
- cerr << "i=" << i << endl;
- cerr << "Frog #" << a[f].y.x << " eat moscuito at x=" << x << endl;
- #endif
- while (true) {
- multiset<pt>::iterator it = mos.lower_bound(mp(a[f].x.x, -1));
- if (it == mos.end() || it->x > a[f].x.x + a[f].x.y)
- break;
- a[f].x.y += it->y;
- upd(0, 0, n - 1, f, a[f].x.x + a[f].x.y);
- a[f].y.y++;
- #ifdef LOG
- cerr << "i=" << i << endl;
- cerr << "Frog #" << a[f].y.x << " eat moscuito at x=" << it->x << endl;
- #endif
- mos.erase(it);
- }
- }
- sort(a, a + n, cmpId);
- forn(i, n) printf("%d " LLD "\n", a[i].y.y, a[i].x.y);
- }
- int main() {
- #ifdef SU1
- assert(freopen("input.txt", "rt", stdin));
- //assert(freopen("output.txt", "wt", stdout));
- #endif
- cout << setprecision(10) << fixed;
- cerr << setprecision(5) << fixed;
- while (read()) {
- solve();
- break;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement