oj.uz

Submission #1011904

# Submission time Handle Problem Language Result Execution time Memory
1011904 2024-07-01T10:51:45 Z atom Meteors (POI11_met) C++17
100 / 100
 899 ms 36592 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

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

namespace bit {
  ll b[N], n;

  void init(int _n) {
    n = _n;
    fill(b, b + n + 1, 0);
  }
  inline int lowbit(int x) {
    return x & (-x);
  }
  void upd(int x, int v) {
    for(int i = x ; i <= n ; i += lowbit(i)) b[i] += v;
  }
  void update(int l, int r, int v) {
    upd(r + 1, -v), upd(l, v);
    if(l > r) upd(1, v), upd(n + 1, -v);
  }
  ll query(int x) {
    ll ans = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i)) ans += b[i];
    return ans;
  }
}

int n, m, k, target[N], ans[N];
vector<tuple<int, int, int> > event;
vector<int> lands[N];

void totBS(int l, int r, vector<int>& candi) {
  if(l + 1 == r || candi.empty()) {
    for(auto c : candi) ans[c] = l;
    return;
  }
  int mid = (l + r) >> 1;
  // do things: events from [l, mid)
  for(int i = l ; i < mid ; ++i) {
    auto [el, er, ea] = event[i];
    bit::update(el, er, ea);
  }
  // split candi into two parts
  vector<int> ok, not_ok;
  for(auto c : candi) {
    ull sum = 0;
    for(auto land : lands[c]) sum += bit::query(land);
    if(sum >= (ull)target[c]) ok.push_back(c);
    else {
      target[c] -= sum;
      not_ok.push_back(c);
    }
  }
  // undo things
  for(int i = l ; i < mid ; ++i) {
    auto [el, er, ea] = event[i];
    bit::update(el, er, -ea);
  }
  // continue binary search and free memory
  totBS(l, mid, ok); vector<int> ().swap(ok);
  totBS(mid, r, not_ok); vector<int> ().swap(not_ok);
}

void init() {
  cin >> n >> m;
  for(int i = 1 ; i <= m ; ++i) {
    int x; cin >> x; lands[x].push_back(i);
  }
  for(int i = 1 ; i <= n ; ++i) cin >> target[i];
  cin >> k;
  for(int i = 0 ; i < k ; ++i) {
    int l, r, a; cin >> l >> r >> a;
    event.push_back({l, r, a});
  }
}
void solve() {
  bit::init(m);
  vector<int> all; 
  for(int i = 1 ; i <= n ; ++i) all.push_back(i);
  totBS(0, k + 1, all);
  vector<int> ().swap(all);
  for(int i = 1 ; i <= n ; ++i) {
    if(ans[i] == k) cout << "NIE\n";
    else cout << ans[i] + 1 << '\n';
  }
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  init();
  solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 12220 KB Output is correct
2 Correct 58 ms 14020 KB Output is correct
3 Correct 58 ms 12204 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 12120 KB Output is correct
2 Correct 60 ms 12116 KB Output is correct
3 Correct 46 ms 13016 KB Output is correct
4 Correct 13 ms 11864 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 12120 KB Output is correct
2 Correct 52 ms 13516 KB Output is correct
3 Correct 13 ms 11604 KB Output is correct
4 Correct 56 ms 12376 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11908 KB Output is correct
2 Correct 67 ms 12128 KB Output is correct
3 Correct 29 ms 12120 KB Output is correct
4 Correct 75 ms 13000 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 270 ms 24756 KB Output is correct
2 Correct 137 ms 19268 KB Output is correct
3 Correct 77 ms 16336 KB Output is correct
4 Correct 783 ms 34012 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 279 ms 23336 KB Output is correct
2 Correct 170 ms 19536 KB Output is correct
3 Correct 44 ms 16788 KB Output is correct
4 Correct 899 ms 36592 KB Output is correct