Advertisement
erek1e

POI Task Warehouse Store

Jul 21st, 2022
614
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.19 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. struct Segment {
  8.     long long minPrefixSum, sum;
  9.     Segment combine(const Segment &s2) const {
  10.         Segment s;
  11.         s.minPrefixSum = min(minPrefixSum, sum+s2.minPrefixSum);
  12.         s.sum = sum + s2.sum;
  13.         return s;
  14.     }
  15.     Segment () {}
  16.     Segment (long long x): minPrefixSum(x), sum(x) {}
  17. };
  18. Segment combine(const Segment &s1, const  Segment &s2) {return s1.combine(s2);}
  19.  
  20. template <typename T>
  21. struct Segtree {
  22.     int n;
  23.     vector<T> tree;
  24.     T (*combine)(const T &, const T &);
  25.     Segtree(T (*fCombine)(const T &, const T &)): combine(fCombine){}
  26.     void build(const vector<T> &v) {
  27.         n = v.size();
  28.         tree.resize(2*n);
  29.         for (int i = 0; i < n; ++i) tree[n+i] = v[i];
  30.         for (int i = n-1; i > 0; --i) tree[i] = combine(tree[2*i], tree[2*i+1]);
  31.     }
  32.     void update(int index, T value) {
  33.         index += n;
  34.         tree[index] = value;
  35.         while (index > 1) {
  36.             if (index & 1) tree[index>>1] = combine(tree[index^1], tree[index]);
  37.             else tree[index>>1] = combine(tree[index], tree[index^1]);
  38.             index>>=1;
  39.         }
  40.     }
  41.     T queryRoot() {
  42.         return tree[1];
  43.     }
  44. };
  45.  
  46. int main() {
  47.     int n; cin >> n;
  48.     vector<Segment> a(n);
  49.     for (int i = 0; i < n; ++i) cin >> a[i].sum, a[i].minPrefixSum = a[i].sum;
  50.    
  51.     vector<pair<int, int>> b(n);
  52.     for (int i = 0; i < n; ++i) cin >> b[i].first, b[i].second = i;
  53.     sort(b.begin(), b.end());
  54.    
  55.     Segtree<Segment> s(combine);
  56.     // Take next power of 2 since order of segments matters
  57.     while (__builtin_popcount((int)a.size()) > 1) a.push_back(0);
  58.     s.build(a);
  59.  
  60.     vector<int> accepted;
  61.     for (auto [x, i] : b) {
  62.         a[i].sum -= x, a[i].minPrefixSum -= x;
  63.         s.update(i, a[i]);
  64.         if (s.queryRoot().minPrefixSum >= 0) accepted.push_back(i+1);
  65.         else {
  66.             a[i].sum += x, a[i].minPrefixSum += x;
  67.             s.update(i, a[i]);
  68.         }
  69.     }
  70.     cout << accepted.size() << endl;
  71.     sort(accepted.begin(), accepted.end());
  72.     for (int x : accepted) cout << x << ' ';
  73.     cout << endl;
  74.     return 0;
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement