Submission #1020986

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020986		NeroZein	Distributing Candies (IOI21_candies)	C++17	0 / 100	90 ms	11972 KiB

candies

#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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33