Advertisement
Georgiy1108

Untitled

Sep 20th, 2019
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.00 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. vector<long long> a, tree, add, tree2;
  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. //  ios::sync_with_stdio(0);
  51. //  cin.tie(0);
  52.     long long n, m;
  53.     cin >> n >> m;
  54.     a.resize(n + m + 1);
  55.     tree.resize(4 * (n + m) + 1, 0);
  56.     add.resize(4 * (n + m) + 1, 0);
  57.     tree2.resize(4 * (n + m) + 1, 0);
  58.     vector<long long> v(n + m);
  59.     vector<pair<long long, long long>> mas;
  60.     vector<long long> can(n + m, -1);
  61.     vector<long long> left(n + m, -1);
  62.     long long l = -1;
  63.     for(long long i = 0; i < n + m; i++)
  64.     {
  65.         cin >> v[i];
  66. //      cout << v[i] << "\n";
  67.         if(i == 0)
  68.         {
  69.             if(v[i] > 0)
  70.                 a[i] = v[i], can[i] = 0, l = i;
  71.         }
  72.         else
  73.         {
  74.             if(v[i] > 0)
  75.             {
  76.                 a[i] = v[i];
  77. //              cout << a[i] << " ";
  78.                 can[i] = 0;
  79.                 l = i;
  80.             }
  81.             else
  82.                 left[i] = l;
  83.         }
  84.         if(v[i] < 0)
  85.             mas.push_back({abs(v[i]), i});
  86.     }
  87. //  for(long long i = 0; i < n + m; i++)
  88. //      cout << a[i] << " ";
  89.     sort(mas.begin(), mas.end());
  90. //  for(auto i : mas)
  91. //      cout << i.first << " " << i.second << "\n";
  92.     build(0, 0, n + m, tree);
  93.     for(auto i : mas)
  94.     {
  95. //      cout << i.first << " " << i.second << " " << query(0, 0, n + m, 0, i.second + 1, tree) << " ";
  96. //      cout << query(0, 0, n + m, 0, n + m, tree2) << " " << left[i.second] << "\n";
  97.         if(query(0, 0, n + m, 0, i.second + 1, tree) + min(query(0, 0, n + m, i.second + 1, n + m, tree), 0LL) >= i.first)
  98.         {
  99. //          cout << "1";
  100. //          cout << left[i.second] << "\n";
  101.             long long x = -i.first;
  102.             can[i.second] = 1;
  103. //          if(a[left[i.second]] <= 0)
  104. //              x = -i.first;
  105. //          else
  106. //          {
  107. //              a[left[i.second]] -= i.first;
  108. //             
  109. //              if(a[left[i.second]] < 0)
  110. //                  x = a[left[i.second]];
  111. //          }
  112. //          cout << x << "\n";
  113.             add_segment(0, 0, n + m, left[i.second], left[i.second] + 1, x, tree);
  114.         }
  115.     }
  116.     for(int i = 0; i < can.size(); i++)
  117.     {
  118.         if(can[i] == 0)
  119.             cout << "resupplied";
  120.         else if(can[i] == -1)
  121.         {
  122.             cout << "declined";
  123.         }
  124.         else
  125.         {
  126.             cout << "approved";
  127.            
  128.         }  
  129.         cout << "\n";
  130.     }
  131.        
  132. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement