Submission #437717

#	Time	Username	Problem	Language	Result	Execution time	Memory
437717		mythos	Distributing Candies (IOI21_candies)	C++17	0 / 100	222 ms	98024 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define ar array
#define pii pair<int, int>
#define vi vector<int>
#define sz(s) (int) s.size()
#define all(s) s.begin(), s.end()
#define pb push_back
#define fi first
#define se second
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define trav(x, a) for (auto& (x) : (a)) 

typedef long long ll;
typedef unsigned long long ull;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

const ll inf = 1ll << 60;

struct SegTree {
  int lo, mi, hi;
  ll save;
  pair<ll, int> mnval, mxval;
  SegTree *l, *r;

  SegTree(int lo, int hi) {
    mi = lo + hi >> 1;
    save = 0;
    mnval = mxval = {0, lo};
    if (lo != hi) {
      l = new SegTree(lo, mi);
      r = new SegTree(mi + 1, hi);
    }
  }

  void pushdown() {
    if (save) {
      l -> mnval.fi += save;
      l -> mxval.fi += save;
      l -> save += save;
      r -> mnval.fi += save;
      r -> mxval.fi += save;
      r -> save += save;
      save = 0;
    }
  }

  void upd(int x, int y, ll val) {
    if (lo == x && hi == y) {
      mnval.fi += val;
      mxval.fi += val;
      save += val;
    } else {
      pushdown();
      if (x <= mi)
        l -> upd(x, min(y, mi), val);
      else
        r -> upd(max(x, mi + 1), y, val);
    }
  }

  int find(ll diff, ll curmx, ll curmn) {
    if (max(mxval.fi, curmx) - min(mnval.fi, curmn) < diff)
      return -1;
    if (lo == hi)
      return lo;
    pushdown();
    if (max(r -> mxval.fi, curmx) - min(r -> mnval.fi, curmn) >= diff)
      return r -> find(diff, curmx, curmn);
    return l -> find(diff, max(curmx, r -> mxval.fi), min(curmn, r -> mnval.fi));
  }

  pair<ll, int> getmn(int x, int y) {
    if (lo == x && hi == y)
      return mnval;
    pushdown();
    auto u = x <= mi ? l -> getmn(x, min(y, mi)) : make_pair(inf, -1);
    auto v = mi < y ? r -> getmn(max(x, mi + 1), y) : make_pair(inf, -1);
    return min(u, v);
  }

  pair<ll, int> getmx(int x, int y) {
    if (lo == x && hi == y)
      return mxval;
    pushdown();
    auto u = x <= mi ? l -> getmx(x, min(y, mi)) : make_pair(-inf, -1);
    auto v = mi < y ? r -> getmx(max(x, mi + 1), y) : make_pair(-inf, -1);
    return max(u, v);
  }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  int n = sz(c), q = sz(l);
  vector<vi> queries(n, vi());
  rep(i, 0, q) {
    queries[l[i]].pb(i + 1);
    if (r[i] + 1 < n)
      queries[r[i] + 1].pb(-i - 1);
  }
  SegTree* tree = new SegTree(0, q);
  vi ans;
  rep(i, 0, n) {
    trav(id, queries[i]) {
      if (id < 0) tree -> upd(-id, q, -v[-id - 1]);
      else tree -> upd(id, q, v[id - 1]);
    }
    int u = tree -> find(c[i], -inf, inf);
    auto [vlst, _] = tree -> getmn(q, q);
    auto [vmn, idmn] = tree -> getmn(max(u, 0), q);
    if (u < 0) ans.pb(vlst - vmn);
    else {
      auto [vmx, idmx] = tree -> getmx(u, q);
      if (idmx > idmn) ans.pb(c[i] - vmx + vlst);
      else ans.pb(vlst - vmn);
    }
  }
  return ans;
}

Compilation message (stderr)

candies.cpp: In constructor 'SegTree::SegTree(int, int)':
candies.cpp:38:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     mi = lo + hi >> 1;
      |          ~~~^~~~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:19:31: warning: unnecessary parentheses in declaration of 'id' [-Wparentheses]
   19 | #define trav(x, a) for (auto& (x) : (a))
      |                               ^
candies.cpp:115:5: note: in expansion of macro 'trav'
  115 |     trav(id, queries[i]) {
      |     ^~~~

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