Advertisement
erek1e

POI Task Meteors

Jul 20th, 2022
700
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.82 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <tuple>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. const long long INF = 2e9;
  9.  
  10. void update(vector<long long> &fenwick, int index, long long value) {
  11.     while (index < (int)fenwick.size()) {
  12.         fenwick[index] += value;
  13.         index += index & -index;
  14.     }
  15. }
  16. void updateRange(vector<long long> &fenwick, int l, int r, long long value) {
  17.     update(fenwick, l, value);
  18.     if (r+1 < (int)fenwick.size()) update(fenwick, r+1, -value);
  19. }
  20. long long query(vector<long long> &fenwick, int index) {
  21.     long long sum = 0;
  22.     while (index) {
  23.         sum += fenwick[index];
  24.         index -= index & -index;
  25.     }
  26.     return sum;
  27. }
  28.  
  29. int main() {
  30.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  31.     int n, m; cin >> n >> m;
  32.     vector<vector<int>> stateIndices(n);
  33.     for (int i = 1; i <= m; ++i) {
  34.         int state; cin >> state;
  35.         stateIndices[state-1].push_back(i);
  36.     }
  37.  
  38.     vector<int> minMeteors(n);
  39.     for (int &x : minMeteors) cin >> x;
  40.  
  41.     int k; cin >> k;
  42.     vector<tuple<int, int, int>> meteors(k);
  43.     for (auto &met : meteors) cin >> get<0>(met) >> get<1>(met) >> get<2>(met);
  44.  
  45.     // Parallel Binary Search on number of meteors for range
  46.     vector<int> stateL(n, 0), stateR(n, k+1);
  47.     vector<pair<int, int>> q;
  48.     while (true) {
  49.         bool going = false; // at least one binary search still active
  50.         q.clear();
  51.         for (int s = 0; s < n; ++s) {
  52.             if (stateL[s]+1 < stateR[s]) {
  53.                 q.emplace_back((stateL[s]+stateR[s])/2, s);
  54.                 going = true;
  55.             }
  56.         }
  57.         sort(q.begin(), q.end());
  58.  
  59.         if (!going) break;
  60.        
  61.         int nextQ = 0; // index in q
  62.  
  63.         // Build segment tree and ask queries along the way
  64.         vector<long long> fenwick(1+m);
  65.         for (int i = 0; i < k; ++i) {
  66.             // Update the segment tree
  67.             int qL = get<0>(meteors[i]), qR = get<1>(meteors[i]), a = get<2>(meteors[i]);
  68.             if (qL <= qR) updateRange(fenwick, qL, qR, a);
  69.             else updateRange(fenwick, qL, m, a), updateRange(fenwick, 1, qR, a);
  70.  
  71.             // Make any state queries necessary
  72.             while (nextQ < (int)q.size() && q[nextQ].first == i+1) {
  73.                 int s = q[nextQ].second;
  74.                 long long total = 0;
  75.                 for (int index : stateIndices[s]) {
  76.                     total += query(fenwick, index);
  77.                     if (total > INF) break; // to avoid overflow
  78.                 }
  79.                 if (total < minMeteors[s]) stateL[s] = i+1;
  80.                 else stateR[s] = i+1;
  81.                 nextQ++;
  82.             }
  83.         }
  84.     }
  85.  
  86.     for (int s = 0; s < n; ++s) {
  87.         if (stateR[s] == k+1) cout << "NIE\n";
  88.         else cout << stateR[s] << '\n';
  89.     }
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement