oj.uz

Submission #1049379

# Submission time Handle Problem Language Result Execution time Memory
1049379 2024-08-08T17:40:55 Z QuangBui Meteors (POI11_met) C++14
74 / 100
 240 ms 25940 KB 
// QuangBuiCP
#include "bits/stdc++.h"
using namespace std;

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

int n, m, events;

int64_t Bit[N];

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

void Update(int from, int to, int 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], collectable[N];

int answer[N];

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();
}

int 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.0 / 12.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 14684 KB Output is correct
2 Correct 2 ms 14844 KB Output is correct
3 Correct 2 ms 14852 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 15452 KB Output is correct
2 Correct 49 ms 17224 KB Output is correct
3 Correct 47 ms 15684 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 15444 KB Output is correct
2 Correct 50 ms 15436 KB Output is correct
3 Correct 41 ms 16472 KB Output is correct
4 Correct 13 ms 15964 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 15404 KB Output is correct
2 Correct 48 ms 16980 KB Output is correct
3 Correct 11 ms 14684 KB Output is correct
4 Correct 46 ms 15752 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 15136 KB Output is correct
2 Correct 62 ms 15468 KB Output is correct
3 Correct 29 ms 15164 KB Output is correct
4 Correct 68 ms 16324 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 25940 KB Output is correct
2 Incorrect 148 ms 18016 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 238 ms 24224 KB Output is correct
2 Incorrect 159 ms 17624 KB Output isn't correct
3 Halted 0 ms 0 KB -