oj.uz

Submission #1020986

# Submission time Handle Problem Language Result Execution time Memory
1020986 2024-07-12T12:36:55 Z NeroZein Distributing Candies (IOI21_candies) C++17
0 / 100
 90 ms 11972 KB 
#include "candies.h"
#include <bits/stdc++.h>
 
using namespace std; 
 
vector<int> distribute_candies(vector<int> c_, vector<int> ql, vector<int> qr, vector<int> v) {
  int n = (int) c_.size(), q = (int) ql.size();
  vector<pair<int, int>> c(n); 
  for (int i = 0; i < n; ++i) {
    c[i] = {c_[i], i};
  }
  sort(c.begin(), c.end());
  vector<pair<int, int>> reach(n);
  for (int i = 0; i < n; ++i) {
    reach[i].first = -1; 
  }
  bool neg = true; 
  long long mn = 0, mx = 0, sum = 0;
  for (int i = 0; i < q; ++i) {
    if (v[i] < 0 && neg) {
      reach[n - 1] = {i, 0};
      continue;
    }
    neg = false; 
    sum += v[i];
    mn = min(mn, sum);
    mx = max(mx, sum);
    if (v[i] > 0) {
      long long bigjump = sum - mn;
      int l = -1, r = n - 1;
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (c[mid].first <= bigjump) {
          l = mid;
        } else {
          r = mid - 1;
        }
      }
      if (l != -1) {
        reach[l] = {i, c[l].first};
      }      
    } else {
      long long smalljump = sum - mx;
      int l = -1, r = n - 1; 
      while (l < r) {
        int mid = (l + r + 1) >> 1;
        if (smalljump <= -c[mid].first) {
          l = mid;
        } else {
          r = mid - 1; 
        }
      }
      if (l != -1) {
        reach[l] = {i, 0};
      }
    }
  }
  for (int i = n - 2; i >= 0; --i) {
    if (reach[i + 1].first > reach[i].first) {
      reach[i].first = reach[i + 1].first; 
      reach[i].second = min(reach[i + 1].second, c[i].first);
    }
  }
  vector<long long> ps(q);
  ps[0] = v[0];
  for (int i = 1; i < q; ++i) {
    ps[i] = ps[i - 1] + v[i]; 
  }
  vector<int> s(n);
  for (int i = 0; i < n; ++i) {
    long long tmp = ps[q - 1];
    if (reach[i].first != -1) {
      tmp -= ps[reach[i].first];      
    }
    s[c[i].second] = reach[i].second + tmp; 
  }
  return s;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 90 ms 11972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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