peltorator

!Parallel Binary Search

Feb 21st, 2018
175
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 ll INF = 1e9 + 9;
  19. const int N = 300001;
  20.  
  21. vector<int> g[N], need[N];
  22. int l[N],r[N], L[N], R[N], m;
  23. ll cnt[N], a[N], tree[N];
  24.  
  25. void upd(int x, ll val)
  26. {
  27.     while (x <= m)
  28.     {
  29.         tree[x] += val;
  30.         x += (x & -x);
  31.  
  32.     }
  33. }
  34. ll get(int x)
  35. {
  36.     ll s = 0;
  37.     while (x)
  38.     {
  39.         s+=tree[x];
  40.         x-=(x & -x);
  41.     }
  42.     return s;
  43. }
  44.  
  45. int main()
  46. {
  47.   //  freopen("in.txt", "r", stdin);
  48.     int n;
  49.     cin >> n >> m;
  50.     for (int i = 1; i <= m; i++)
  51.     {
  52.         int x;
  53.         cin >> x;
  54.         g[x].push_back(i);
  55.     }
  56.     for (int i = 1; i <= n; i++)
  57.         cin >> cnt[i];
  58.     int k;
  59.     cin >> k;
  60.     for (int i = 1; i <= k; i++)
  61.         cin >> l[i] >> r[i] >> a[i];
  62.     for (int i = 0; i <= n; i++)
  63.         L[i] = 1, R[i] = k + 1;
  64.     bool ok = 1;
  65.     while (ok)
  66.     {
  67.         ok = 0;
  68.         for(int i = 0; i < N; i++)
  69.             tree[i] = 0;
  70.         for(int i = 1; i <= n; i++)
  71.             if(L[i] != R[i])
  72.                 need[(L[i] + R[i]) / 2].push_back(i);
  73.         for (int i = 1; i <= k; i++)
  74.         {
  75.             if (l[i] <= r[i])
  76.             {
  77.                 upd(l[i], a[i]);
  78.                 upd(r[i] + 1, -a[i]);
  79.             }
  80.             else
  81.             {
  82.                 upd(1, a[i]);
  83.                 upd(r[i] + 1, -a[i]);
  84.                 upd(l[i], a[i]);
  85.             }
  86.             while (need[i].size())
  87.             {
  88.                 int cur = need[i].back();
  89.                 need[i].pop_back();
  90.                 ll sum = 0;
  91.                 ok = 1;
  92.                 for (auto sectors: g[cur])
  93.                 {
  94.                     sum += get(sectors);
  95.                     if(sum >= cnt[cur])
  96.                         break;
  97.                 }
  98.                 if (sum >= cnt[cur])
  99.                     R[cur] = i;
  100.                 else
  101.                     L[cur] = i + 1;
  102.             }
  103.         }
  104.     }
  105.     for(int i = 1; i <= n; i++)
  106.     {
  107.         if(L[i] <= k)
  108.             cout << L[i] << "\n";
  109.         else
  110.             cout << "NIE\n";
  111.     }
  112.     return 0;
RAW Paste Data