Advertisement
erek1e

POI Task Meteors (74pts - WA)

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