Submission #966261

#	Time	Username	Problem	Language	Result	Execution time	Memory
966261		AkibAzmain	Distributing Candies (IOI21_candies)	C++17	100 / 100	624 ms	42272 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll sts = 1;
vector < ll > pf;
vector < pair < ll, ll > > stn, stx;

void
pfa (ll i, ll x)
{
  while (i < pf.size ())
    {
      pf[i] += x;
      i += (i + 1) & -(i + 1);
    }
}

ll
pfs (ll i)
{
  ll sum = 0;
  while (i >= 0)
    {
      sum += pf[i];
      i -= (i + 1) & -(i + 1);
    }
  return sum;
}

void
stp (vector < pair < ll, ll > > &st, int i)
{
  if (i < sts)
    {
      st[i * 2].first += st[i].second;
      st[i * 2].second += st[i].second;
      st[i * 2 + 1].first += st[i].second;
      st[i * 2 + 1].second += st[i].second;
    }
  st[i].second = 0;
}

void
sta1 (vector < pair < ll, ll > > &st, ll i, int j, ll x, ll n, ll l, ll r, bool c)
{
  if (j < l || r < i) return;
  if (i <= l && r <= j)
    {
      st[n].first += x, st[n].second += x;
      return;
    }
  stp (st, n);
  int m = (l + r + 1) / 2;
  sta1 (st, i, j, x, n * 2, l, m - 1, c);
  sta1 (st, i, j, x, n * 2 + 1, m, r, c);
  st[n].first = (c
                 ? max (st[n * 2].first, st[n * 2 + 1].first)
                 : min (st[n * 2].first, st[n * 2 + 1].first));
}

void
sta (ll i, ll x)
{
  pfa (i, x);
  sta1 (stn, i, sts - 1, x, 1, 0, sts - 1, false);
  sta1 (stx, i, sts - 1, x, 1, 0, sts - 1, true);
}

ll
stnx1 (vector < pair < ll, ll > > &st, ll i, ll j, ll n, ll l, ll r, bool c)
{
  assert (!(j < l || r < i));
  if (i <= l && r <= j) return st[n].first;
  stp (st, n);
  ll m = (l + r + 1) / 2;
  if (j < m) return stnx1 (st, i, j, n * 2, l, m - 1, c);
  if (m <= i) return stnx1 (st, i, j, n * 2 + 1, m, r, c);
  ll x = stnx1 (st, i, j, n * 2, l, m - 1, c);
  ll y = stnx1 (st, i, j, n * 2 + 1, m, r, c);
  return (c ? max (x, y) : min (x, y));
}

ll
stnx (ll i, bool c)
{
  return stnx1 ((c ? stx : stn), 0, i, 1, 0, sts - 1, c);
}

ll
tst1 (ll x, ll n, ll l, ll r, ll mn, ll mx)
{
  if (n >= sts) return l;
  stp (stn, n);
  stp (stx, n);
  ll mn2 = min (mn, stn[n * 2].first), mx2 = max (mx, stx[n * 2].first), m = (l + r + 1) / 2;
  if (mx2 - mn2 >= x)
    return tst1 (x, n * 2, l, m - 1, mn, mx);
  else
    return tst1 (x, n * 2 + 1, m, r, mn2, mx2);
}

ll
tst (ll x)
{
  return tst1 (x, 1, 0, sts - 1, 0, 0);
}

std::vector<int> distribute_candies (std::vector<int> c, std::vector<int> l,
                                     std::vector<int> r, std::vector<int> v)
{
  ll n = c.size();
  v.push_back (0);
  l.push_back (0);
  r.push_back (-1);
  vector < ll > a;
  for (auto &x : v) a.push_back (x);
  reverse (a.begin (), a.end ());
  reverse (l.begin (), l.end ());
  reverse (r.begin (), r.end ());
  a.push_back (-1e18);
  l.push_back (0);
  r.push_back (n - 1);
  for (auto &x : a) x *= -1;
  vector < vector < pair < ll, ll > > > ea (n + 1);
  for (int i = 0; i < a.size (); ++i)
    ea[l[i]].push_back ({ i, a[i] }),
      ea[r[i] + 1].push_back ({ i, -a[i] });
  while (sts < a.size ()) sts *= 2;
  stn.resize (sts * 2);
  stx.resize (sts * 2);
  pf.resize (a.size ());
  vector < int > ans (n);
  for (int i = 0; i < n; ++i)
    {
      for (auto &x : ea[i]) sta (x.first, x.second);
      int j = tst (c[i]);
      if (pfs (j) == stnx (j, false))
        ans[i] = c[i] - stnx (j, true);
      else
        ans[i] = -stnx (j, false);
    }
  return ans;
}

Compilation message (stderr)

candies.cpp: In function 'void pfa(ll, ll)':
candies.cpp:13:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |   while (i < pf.size ())
      |          ~~^~~~~~~~~~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:127:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   for (int i = 0; i < a.size (); ++i)
      |                   ~~^~~~~~~~~~~
candies.cpp:130:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  130 |   while (sts < a.size ()) sts *= 2;
      |          ~~~~^~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33