peltorator

!Recursive Parallel Binary Search

Feb 21st, 2018
133
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <queue>
  6. #include <deque>
  7. #include <algorithm>
  8. #include <math.h>
  9. #include <string>
  10. #include <cstring>
  11. #include <set>
  12.  
  13. using namespace std;
  14.  
  15. typedef long long ll;
  16. typedef double ld;
  17.  
  18. const int N = 300001;
  19.  
  20. vector<int> owner[N];
  21. ll need[N];
  22. int ql[N], qr[N];
  23. ll a[N];
  24. int ans[N];
  25. const int T = 2000001;
  26. ll tree[T];
  27.  
  28. void upd(int v, int l, int r, int ql, int qr, ll val)
  29. {
  30.     if (r <= l|| l >= qr || ql >= r)
  31.         return;
  32.     if (ql <= l && r <= qr)
  33.     {
  34.         tree[v] += val;
  35.         return;
  36.     }
  37.     int mid = (r + l) / 2;
  38.     upd(2 * v, l, mid, ql, qr, val);
  39.     upd(2 * v + 1, mid, r, ql, qr, val);
  40. }
  41.  
  42. int m;
  43.  
  44. ll find(int v, int l, int r, int q)
  45. {
  46.     if (l + 1 == r)
  47.         return tree[v];
  48.     int mid = (r + l) / 2;
  49.     if (q < mid)
  50.         return tree[v] + find(2 * v, l, mid, q);
  51.     return tree[v] + find(2 * v + 1, mid, r, q);
  52. }
  53.  
  54. void divide(int l, int r, vector<int> v) // челики, у которых ответ на полуинтервале [l;r)
  55. {
  56.     if (!v.size())
  57.         return;
  58.     if (r <= l)
  59.         return;
  60.     if (l + 1 == r)
  61.     {
  62.         for (int i : v)
  63.             ans[i] = l;
  64.         return;
  65.     }
  66.     vector<int> left, right;
  67.     int mid = (r + l) / 2;
  68.  
  69.     for (int i = l; i < mid; i++)
  70.         if (ql[i] < qr[i])
  71.             upd(1, 0, m, ql[i], qr[i], a[i]);
  72.         else
  73.             upd(1, 0, m, ql[i], m, a[i]), upd(1, 0, m, 0, qr[i], a[i]);
  74.  
  75.  
  76.     for (int i : v)
  77.     {
  78.         ll cur = 0;
  79.         for (int j : owner[i])
  80.         {
  81.             cur += find(1, 0, m, j);
  82.             if (cur >= need[i])
  83.                 break;
  84.         }
  85.         if (cur >= need[i])
  86.             left.push_back(i);
  87.         else
  88.             right.push_back(i);
  89.     }
  90.     v.clear();
  91.     divide(mid, r, right);
  92.     right.clear();
  93.  
  94.     for (int i = l; i < mid; i++)
  95.         if (ql[i] < qr[i])
  96.             upd(1, 0, m, ql[i], qr[i], -a[i]);
  97.         else
  98.             upd(1, 0, m, ql[i], m, -a[i]), upd(1, 0, m, 0, qr[i], -a[i]);
  99.  
  100.     divide(l, mid, left);
  101.     left.clear();
  102.  }
  103.  
  104. int main()
  105. {
  106.    // freopen("in.txt", "r", stdin);
  107.     ios::sync_with_stdio(0);
  108.     int n;
  109.     cin >> n >> m;
  110.     for (int i = 0; i < m; i++)
  111.     {
  112.         int x;
  113.         cin >> x;
  114.         x--;
  115.         owner[x].push_back(i);
  116.     }
  117.     for (int i = 0; i < n; i++)
  118.         ans[i] = -1;
  119.     for (int i = 0; i < n; i++)
  120.         cin >> need[i];
  121.     vector<int> kek;
  122.     int k;
  123.     cin >> k;
  124.     for (int i = 0; i < k; i++)
  125.         cin >> ql[i] >> qr[i] >> a[i], ql[i]--;
  126.     for (int i = 0; i < n; i++)
  127.         kek.push_back(i);
  128.     divide(0, k + 1, kek);
  129.     for (int i = 0; i < n; i++)
  130.     {
  131.         if (ans[i] == k)
  132.             cout << "NIE\n";
  133.         else
  134.             cout << ans[i] + 1 << "\n";
  135.     }
  136.     return 0;
  137. }
RAW Paste Data