oj.uz

Submission #379238

# Submission time Handle Problem Language Result Execution time Memory
379238 2021-03-17T14:46:17 Z ADMathNoob Meteors (POI11_met) C++11
100 / 100
 2210 ms 43820 KB 
#include <bits/stdc++.h>

using namespace std;

struct Fenwick {
  int n;
  vector<long long> tree;

  Fenwick(int _n) : n(_n) {
    tree.resize(n + 1);
  }

  long long get(int x) {
    long long res = 0;
    for (x++; x > 0; x -= x & -x) {
      res += tree[x];
    }
    return res;
  }

  void modify(int x, long long v) {
    for (x++; x <= n; x += x & -x) {
      tree[x] += v;
    }
  }
};

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

#ifdef _DEBUG
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  freopen("debug_output.txt", "w", stderr);
#endif

  int n, m;
  cin >> n >> m;
  vector<vector<int>> owned_by(n);
  for (int i = 0; i < m; i++) {
    int s;
    cin >> s;
    --s;
    assert(0 <= s && s < n);
    owned_by[s].push_back(i);
  }
  vector<int> target(n);
  for (int i = 0; i < n; i++) {
    cin >> target[i];
    assert(1 <= target[i] && target[i] <= (int) 1e9);
  }
  int k;
  cin >> k;
  vector<int> ll(k), rr(k);
  vector<int> add(k);
  for (int i = 0; i < k; i++) {
    cin >> ll[i] >> rr[i] >> add[i];
    --ll[i];
    --rr[i];
    assert(0 <= ll[i] && ll[i] < m);
    assert(0 <= rr[i] && rr[i] < m);
    assert(1 <= add[i] && add[i] <= (int) 1e9);
  }

  vector<int> low(n, 0), high(n, k);
  while (true) {
    bool done = true;
    vector<int> mid(n);
    vector<vector<int>> check_at(k + 1);
    for (int i = 0; i < n; i++) {
      if (low[i] < high[i]) {
        done = false;
      }
      mid[i] = (low[i] + high[i]) >> 1;
      check_at[mid[i]].push_back(i);
    }
    if (done) {
      break;
    }
    Fenwick ft(m + 1);
    for (int qq = 0; qq < k; qq++) {
      if (ll[qq] <= rr[qq]) {
        ft.modify(ll[qq], add[qq]);
        ft.modify(rr[qq] + 1, -add[qq]);
      } else {
        ft.modify(ll[qq], add[qq]);
        // ft.modify(m, -add[qq]);
        ft.modify(0, add[qq]);
        ft.modify(rr[qq] + 1, -add[qq]);
      }
      for (int i : check_at[qq]) {
        long long sum = 0;
        for (int j : owned_by[i]) {
          sum += ft.get(j);
          if (sum >= target[i]) {
            break;
          }
        }
        if (sum >= target[i]) {
          high[i] = mid[i];
        } else {
          low[i] = mid[i] + 1;
        }
      }
    }
    for (int i = 0; i < n; i++) {
      assert(low[i] <= high[i]);
    }
  }
  for (int i = 0; i < n; i++) {
    assert(low[i] == high[i]);
    if (low[i] == k) {
      cout << "NIE\n";
    } else {
      cout << low[i] + 1 << '\n';
    }
  }

  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 364 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Correct 2 ms 364 KB Output is correct
3 Correct 2 ms 492 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 3788 KB Output is correct
2 Correct 122 ms 5096 KB Output is correct
3 Correct 121 ms 4684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 4172 KB Output is correct
2 Correct 101 ms 4172 KB Output is correct
3 Correct 114 ms 5176 KB Output is correct
4 Correct 30 ms 2668 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 3884 KB Output is correct
2 Correct 98 ms 5328 KB Output is correct
3 Correct 48 ms 2776 KB Output is correct
4 Correct 108 ms 4872 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 3436 KB Output is correct
2 Correct 100 ms 4320 KB Output is correct
3 Correct 80 ms 3564 KB Output is correct
4 Correct 129 ms 5480 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1149 ms 23332 KB Output is correct
2 Correct 653 ms 15224 KB Output is correct
3 Correct 263 ms 11528 KB Output is correct
4 Correct 2078 ms 40632 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1126 ms 22416 KB Output is correct
2 Correct 674 ms 15220 KB Output is correct
3 Correct 227 ms 10908 KB Output is correct
4 Correct 2210 ms 43820 KB Output is correct