oj.uz

Submission #966261

# Submission time Handle Problem Language Result Execution time Memory
966261 2024-04-19T15:37:16 Z AkibAzmain Distributing Candies (IOI21_candies) C++17
100 / 100
 624 ms 42272 KB 
#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

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.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 600 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 42168 KB Output is correct
2 Correct 550 ms 42212 KB Output is correct
3 Correct 624 ms 42208 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 391 ms 33712 KB Output is correct
3 Correct 87 ms 7764 KB Output is correct
4 Correct 530 ms 42204 KB Output is correct
5 Correct 516 ms 42012 KB Output is correct
6 Correct 488 ms 42272 KB Output is correct
7 Correct 520 ms 42180 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 436 KB Output is correct
3 Correct 154 ms 33616 KB Output is correct
4 Correct 76 ms 7772 KB Output is correct
5 Correct 264 ms 39088 KB Output is correct
6 Correct 253 ms 40880 KB Output is correct
7 Correct 252 ms 39104 KB Output is correct
8 Correct 255 ms 39192 KB Output is correct
9 Correct 257 ms 40220 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 3 ms 604 KB Output is correct
5 Correct 3 ms 600 KB Output is correct
6 Correct 551 ms 42168 KB Output is correct
7 Correct 550 ms 42212 KB Output is correct
8 Correct 624 ms 42208 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 391 ms 33712 KB Output is correct
11 Correct 87 ms 7764 KB Output is correct
12 Correct 530 ms 42204 KB Output is correct
13 Correct 516 ms 42012 KB Output is correct
14 Correct 488 ms 42272 KB Output is correct
15 Correct 520 ms 42180 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 436 KB Output is correct
18 Correct 154 ms 33616 KB Output is correct
19 Correct 76 ms 7772 KB Output is correct
20 Correct 264 ms 39088 KB Output is correct
21 Correct 253 ms 40880 KB Output is correct
22 Correct 252 ms 39104 KB Output is correct
23 Correct 255 ms 39192 KB Output is correct
24 Correct 257 ms 40220 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 82 ms 7624 KB Output is correct
27 Correct 311 ms 33472 KB Output is correct
28 Correct 530 ms 42204 KB Output is correct
29 Correct 555 ms 42272 KB Output is correct
30 Correct 524 ms 42016 KB Output is correct
31 Correct 519 ms 42000 KB Output is correct
32 Correct 524 ms 42268 KB Output is correct