Submission #1049681

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049681		QuangBui	Meteors (POI11_met)	C++17	74 / 100	277 ms	37468 KiB

met

// QuangBuiCP
// https://oj.uz/problem/view/POI11_met
#include "bits/stdc++.h"
using namespace std;

#define int long long

const int N = (int) 3e5 + 5;

int n, m, events;

int64_t Bit[N];

void Update(int x, int64_t val) {
  while (x <= m) {
    Bit[x] += val;
    x += x & -x;
  }
}

void Update(int from, int to, int64_t val) {
  Update(from, val);
  Update(to + 1, -val);
  if (from > to) {
    Update(1, val);
    Update(m + 1, -val);
  }
}

int64_t Query(int x) {
  int64_t res = 0;
  while (x >= 1) {
    res += Bit[x];
    x -= x & -x;
  }
  return res;
}

vector<int> properties[N];
int64_t target[N];
int L[N], R[N];
int64_t collectable[N];

int answer[N];

// [from, to)
void BinarySearch(int from, int to, vector<int>& candidates) {
  if (from + 1 == to || candidates.empty()) {
    for (int cand : candidates) {
      answer[cand] = from;
    }
    return;
  }
  int mid = (from + to) / 2;
  for (int i = from; i < mid; ++i) {
    Update(L[i], R[i], collectable[i]);
  }
  vector<int> doable, not_doable;
  for (int who : candidates) {
    int64_t sum = 0;
    for (int land : properties[who]) {
      sum += Query(land);
    }
    if (sum >= target[who]) {
      doable.push_back(who);
    } else {
      target[who] -= sum;
      not_doable.push_back(who);
    }
  }
  for (int i = from; i < mid; ++i) {
    Update(L[i], R[i], -collectable[i]);
  }
  BinarySearch(from, mid, doable);
  BinarySearch(mid, to, not_doable);
  doable.clear();
  not_doable.clear();
}

signed main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);
#endif // LOCAL

  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int who; cin >> who;
    properties[who].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    cin >> target[i];
  }
  cin >> events;
  for (int i = 0; i < events; ++i) {
    cin >> L[i] >> R[i] >> collectable[i];
  }
  vector<int> owners(n);
  iota(owners.begin(), owners.end(), 1);
  BinarySearch(0, events + 1, owners);
  for (int i = 1; i <= n; ++i) {
    if (answer[i] == events) {
      cout << "NIE\n";
    } else {
      cout << answer[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