Advertisement
Georgiy1108

Untitled

Sep 20th, 2019
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.99 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<long long> a, tree, add;
  6. const long long INF = (long long)1e18;
  7.  
  8. void build(long long i, long long  l, long long r, vector<long long> &t)
  9. {
  10.     if (r == l + 1)
  11.         tree[i] = a[l];
  12.     else
  13.     {
  14.         long long m = (l + r) / 2;
  15.         build(2 * i + 1, l, m, t);
  16.         build(2 * i + 2, m, r, t);
  17.         t[i] = t[2 * i + 1] + t[2 * i + 2];    
  18.     }
  19. }
  20.  
  21. void add_segment(long long i, long long l, long long r, long long ql, long long qr, long long delta, vector<long long> &t)
  22. {
  23.     if (qr <= l || r <= ql)
  24.         return;
  25.     if (ql <= l && qr >= r)
  26.     {
  27.         add[i] += delta;
  28.         return;
  29.     }
  30.     long long m = (l + r) / 2;
  31.     add_segment(2 * i + 1, l, m, ql, qr, delta, t);
  32.     add_segment(2 * i + 2, m, r, ql, qr, delta, t);
  33.     t[i] = t[2 * i + 1] + add[2 * i + 1] + t[2 * i + 2] + add[2 * i + 2];
  34. }
  35.  
  36. long long query(long long i, long long l, long long r, long long ql, long long qr, vector<long long> &t)
  37. {
  38.     if (qr <= l || r <= ql)
  39.         return 0;
  40.     if (ql <= l && r <= qr)
  41.     {
  42.         return t[i] + add[i];
  43.     }
  44.     long long m = (l + r) / 2;
  45.     return query(2 * i + 1, l, m, ql, qr, t) + add[i] + query(2 * i + 2, m, r, ql, qr, t);
  46. }
  47.  
  48. main()
  49. {
  50.     long long n, m;
  51.     cin >> n >> m;
  52.     a.resize(n + m + 1);
  53.     tree.resize(4 * (n + m) + 1, 0);
  54.     add.resize(4 * (n + m) + 1, 0);
  55.     vector<long long> v(n + m);
  56.     vector<pair<long long, long long>> mas;
  57.     vector<long long> can(n + m, -1), left(n + m, -1);
  58.     long long l = -1;
  59.     for(long long i = 0; i < n + m; i++)
  60.     {
  61.         cin >> v[i];
  62.         if(i == 0)
  63.             if(v[i] > 0)
  64.                 a[i] = v[i], can[i] = 0, l = i;// ближайшее положительное;
  65.         else
  66.         {
  67.             if(v[i] > 0)
  68.             {
  69.                 a[i] = v[i];
  70.                 can[i] = 0;
  71.                 left[i] = l;// ближайшее положительное
  72.                 l = i;
  73.             }
  74.             else
  75.                 left[i] = l;
  76.         }
  77.         if(v[i] < 0)
  78.             mas.push_back({abs(v[i]), i});
  79.     }
  80.     sort(mas.begin(), mas.end());// сортируем по значению
  81.     build(0, 0, n + m, tree);
  82.     for(auto i : mas)
  83.     {
  84.         if(query(0, 0, n + m, 0, i.second + 1, tree) >= i.first)// если хватает денег
  85.         {
  86.             long long x = i.first;
  87.             can[i.second] = 1;
  88.             int t = i.second;
  89.             while(x > 0)// пока не уменьшили текущее число
  90.             {
  91.                 long long cur = min(x, query(0, 0, n + m, left[i.second], left[i.second] + 1, tree));
  92.                 add_segment(0, 0, n + m, left[i.second], left[i.second] + 1, -cur, tree);// уменьшаем ближайшее
  93.                 if(query(0, 0, n + m, left[i.second], left[i.second] + 1, tree) == 0)// если текущее равно 0
  94.                 {
  95.                     int g = i.second;
  96.                     i.second = left[i.second]; // следующее ближайшее
  97.                     left[g] = left[i.second]; // эвристика сжатия путей.
  98.                     left[t] = left[i.second];
  99.                 }
  100.                 if(left[i.second] == -1)
  101.                     break;
  102.                 x -= cur;
  103.             }  
  104.         }
  105.     }
  106.     for(int i = 0; i < can.size(); i++)
  107.     {
  108.         if(can[i] == 0)
  109.             cout << "resupplied";
  110.         else if(can[i] == -1)
  111.             cout << "declined";
  112.         else
  113.             cout << "approved";
  114.         cout << "\n";
  115.     }  
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement