oj.uz

Submission #379234

# Submission time Handle Problem Language Result Execution time Memory
379234 2021-03-17T14:36:44 Z ADMathNoob Meteors (POI11_met) C++11
74 / 100
 1256 ms 32032 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) {
    assert(0 <= x && x < n);
    long long res = 0;
    for (x++; x > 0; x -= x & -x) {
      res += tree[x];
    }
    return res;
  }

  void modify(int x, long long v) {
    assert(0 <= x && x < n);
    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<long long> 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<long long> 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]) {
          high[i] = mid[i];
        } else {
          low[i] = mid[i] + 1;
        }
      }
    }
  }
  for (int i = 0; i < n; 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 492 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 74 ms 4204 KB Output is correct
2 Correct 121 ms 5996 KB Output is correct
3 Correct 106 ms 5196 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 4940 KB Output is correct
2 Correct 108 ms 5068 KB Output is correct
3 Correct 128 ms 6124 KB Output is correct
4 Correct 33 ms 2788 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 4312 KB Output is correct
2 Correct 101 ms 6128 KB Output is correct
3 Correct 49 ms 2924 KB Output is correct
4 Correct 105 ms 5640 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 4076 KB Output is correct
2 Correct 107 ms 5068 KB Output is correct
3 Correct 89 ms 4204 KB Output is correct
4 Correct 144 ms 6388 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1237 ms 32032 KB Output is correct
2 Incorrect 720 ms 23544 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1256 ms 31032 KB Output is correct
2 Incorrect 708 ms 22084 KB Output isn't correct
3 Halted 0 ms 0 KB -