oj.uz

Submission #1049386

# Submission time Handle Problem Language Result Execution time Memory
1049386 2024-08-08T17:49:23 Z QuangBui Meteors (POI11_met) C++14
74 / 100
 280 ms 31036 KB 
// QuangBuiCP
// https://oj.uz/problem/view/POI11_met
#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, 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();
}

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 3 ms 16732 KB Output is correct
2 Correct 3 ms 16732 KB Output is correct
3 Correct 2 ms 16912 KB Output is correct

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 18268 KB Output is correct
2 Correct 51 ms 20048 KB Output is correct
3 Correct 53 ms 18408 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 18252 KB Output is correct
2 Correct 65 ms 18256 KB Output is correct
3 Correct 43 ms 19292 KB Output is correct
4 Correct 13 ms 18524 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 18132 KB Output is correct
2 Correct 52 ms 19796 KB Output is correct
3 Correct 14 ms 17404 KB Output is correct
4 Correct 52 ms 18532 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 17904 KB Output is correct
2 Correct 59 ms 18268 KB Output is correct
3 Correct 29 ms 18000 KB Output is correct
4 Correct 65 ms 19124 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 31036 KB Output is correct
2 Incorrect 166 ms 23248 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 280 ms 29448 KB Output is correct
2 Incorrect 190 ms 22032 KB Output isn't correct
3 Halted 0 ms 0 KB -