Submission #379234

#	Time	Username	Problem	Language	Result	Execution time	Memory
379234		ADMathNoob	Meteors (POI11_met)	C++11	74 / 100	1256 ms	32032 KiB

met

#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 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13