Advertisement
Guest User

Untitled

a guest
Dec 19th, 2015
477
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.76 KB | None | 0 0
  1. #undef NDEBUG
  2. #ifdef SU1
  3. #define _GLIBCXX_DEBUG
  4. #endif
  5.  
  6. #include <bits/stdc++.h>
  7.  
  8. #define forn(i, n) for (int i = 0; i < int(n); i++)
  9. #define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
  10. #define fore(i, l, r) for (int i = int(l); i < int(r); i++)
  11. #define correct(x, y, n, m) (0 <= (x) && (x) < (n) && 0 <= (y) && (y) < (m))
  12. #define all(a) (a).begin(), (a).end()
  13. #define sz(a) int((a).size())
  14. #define pb(a) push_back(a)
  15. #define mp(x, y) make_pair((x), (y))
  16. #define x first
  17. #define y second
  18.  
  19. using namespace std;
  20.  
  21. typedef long long li;
  22. typedef long double ld;
  23. typedef pair<int, int> pt;
  24.  
  25. template<typename X> inline X abs(const X& a) { return a < 0? -a: a; }
  26. template<typename X> inline X sqr(const X& a) { return a * a; }
  27.  
  28. const int INF = int(1e9);
  29. const li INF64 = li(1e18);
  30. const ld EPS = 1e-9, PI = 3.1415926535897932384626433832795;
  31.  
  32. #ifdef SU1
  33. #define LLD "%lld"
  34. #else
  35. #define LLD "%I64d"
  36. #endif
  37.  
  38. typedef pair<pair<int, li>, pt> frog;
  39.  
  40. const int N = 200200;
  41.  
  42. int n, m;
  43. frog a[N];
  44. pt b[N];
  45.  
  46. inline bool read() {
  47.     if (!(cin >> n >> m)) return false;
  48.     forn(i, n) assert(scanf("%d" LLD, &a[i].x.x, &a[i].x.y) == 2), a[i].y = mp(i, 0);
  49.     forn(i, m) assert(scanf("%d%d", &b[i].x, &b[i].y) == 2);
  50.     return true;
  51. }
  52.  
  53. li t[4 * N];
  54.  
  55. void build(int idx, int l, int r) {
  56.     if (l == r)
  57.         t[idx] = a[l].x.x + a[l].x.y;
  58.     else {
  59.         int md = (l + r) >> 1;
  60.         build(2 * idx + 1, l, md);
  61.         build(2 * idx + 2, md + 1, r);
  62.         t[idx] = max(t[2 * idx + 1], t[2 * idx + 2]);
  63.     }
  64. }
  65.  
  66. inline bool cmpId(const frog& a, const frog& b) { return a.y.x < b.y.x; }
  67.  
  68. li max(int idx, int l, int r, int lf, int rg) {
  69.     if (l == lf && r == rg)
  70.         return t[idx];
  71.     int md = (l + r) >> 1;
  72.     li ans = -1;
  73.     if (lf <= md) ans = max(ans, max(2 * idx + 1, l, md, lf, min(md, rg)));
  74.     if (md < rg) ans = max(ans, max(2 * idx + 2, md + 1, r, max(lf, md + 1), rg));
  75.     return ans;
  76. }
  77.  
  78. int find(int idx, int l, int r, li x) {
  79.     if (l == r) return l;
  80.     int md = (l + r) >> 1;
  81.     if (t[2 * idx + 1] >= x) return find(2 * idx + 1, l, md, x);
  82.     return find(2 * idx + 2, md + 1, r, x);
  83. }
  84.  
  85. void upd(int idx, int l, int r, int pos, li val) {
  86.     if (l == r) return void(t[idx] = val);
  87.     int md = (l + r) >> 1;
  88.     if (pos <= md) upd(2 * idx + 1, l, md, pos, val);
  89.     else upd(2 * idx + 2, md + 1, r, pos, val);
  90.     t[idx] = max(t[2 * idx + 1], t[2 * idx + 2]);
  91. }
  92.  
  93. #ifdef SU1
  94. //#define LOG
  95. #endif
  96.  
  97. inline void solve() {
  98.     sort(a, a + n);
  99.     build(0, 0, n - 1);
  100.  
  101.     multiset<pt> mos;
  102.  
  103.     forn(i, m) {
  104.         int x = b[i].x, w = b[i].y;
  105.         int idx = int(lower_bound(a, a + n, mp(mp(x + 1, -1ll), mp(-1, -1))) - a);
  106.         li maxv = idx ? max(0, 0, n - 1, 0, idx - 1) : -1;
  107.         //cerr << "$$$" << i << ' ' << maxv << endl;
  108.         if (maxv < x) {
  109.             mos.insert(mp(x, w));
  110.             continue;
  111.         }
  112.         int f = find(0, 0, n - 1, x);
  113.         assert(a[f].x.x <= x && x <= a[f].x.x + a[f].x.y);
  114.         a[f].x.y += w;
  115.         upd(0, 0, n - 1, f, a[f].x.x + a[f].x.y);
  116.         a[f].y.y++;
  117. #ifdef LOG
  118.         cerr << "i=" << i << endl;
  119.         cerr << "Frog #" << a[f].y.x << " eat moscuito at x=" << x << endl;
  120. #endif
  121.         while (true) {
  122.             multiset<pt>::iterator it = mos.lower_bound(mp(a[f].x.x, -1));
  123.             if (it == mos.end() || it->x > a[f].x.x + a[f].x.y)
  124.                 break;
  125.             a[f].x.y += it->y;
  126.             upd(0, 0, n - 1, f, a[f].x.x + a[f].x.y);
  127.             a[f].y.y++;
  128. #ifdef LOG
  129.             cerr << "i=" << i << endl;
  130.             cerr << "Frog #" << a[f].y.x << " eat moscuito at x=" << it->x << endl;
  131. #endif
  132.             mos.erase(it);
  133.         }
  134.     }
  135.  
  136.     sort(a, a + n, cmpId);
  137.     forn(i, n) printf("%d " LLD "\n", a[i].y.y, a[i].x.y);
  138. }
  139.  
  140. int main() {
  141. #ifdef SU1
  142.     assert(freopen("input.txt", "rt", stdin));
  143.     //assert(freopen("output.txt", "wt", stdout));
  144. #endif
  145.    
  146.     cout << setprecision(10) << fixed;
  147.     cerr << setprecision(5) << fixed;
  148.  
  149.     while (read()) {
  150.         solve();
  151.         break;
  152.     }
  153.    
  154.     return 0;
  155. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement