Submission #625093

#	Time	Username	Problem	Language	Result	Execution time	Memory
625093		juancarlovieri	Distributing Candies (IOI21_candies)	C++17	0 / 100	1094 ms	26280 KiB

candies

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


#define int long long
#define sl i + 1
#define sr i + (sm - ss + 1) * 2
#define sm (ss + se) / 2
#define block 350

int pend[400005], tree[400005], pend2[400005];
int pre[200005];

void push(int i, int ss, int se) {
  // assert(!(pend[i] and pend2[i]));
  if (pend2[i] == 1) {
    tree[i] = 0;
    if (ss != se) {
      pend2[sl] = 1;
      pend2[sr] = 1;
      pend[sl] = 0;
      pend[sr] = 0;
    }
    pend2[i] = 0;
  }

  if (pend2[i] == 2) {
    tree[i] = pre[se] - (ss ? pre[ss - 1] : 0);
    if (ss != se) {
      pend2[sl] = 2;
      pend2[sr] = 2;
      pend[sl] = 0;
      pend[sr] = 0;
    }
    pend2[i] = 0;
  }

  if (pend[i]) {
    tree[i] += pend[i];
    if (ss != se) {
      pend[sl] += pend[i];
      pend[sr] += pend[i];
    }
    pend[i] = 0;
  }
}

void upd(int l, int r, int val, int ss = 0, int se = 200000, int i = 0) {
  push(i, ss, se);
  if (ss > se or l > se or r < ss) return;
  if (ss >= l and se <= r) {
    pend[i] += val;
    // cout << i << endl;
    push(i, ss, se);
    return;
  }
  upd(l, r, val, ss, sm, sl);
  upd(l, r, val, sm + 1, se, sr);

  tree[i] = max(tree[sl], tree[sr]);
}


void forc(int l, int r, int val, int ss = 0, int se = 200000, int i = 0) {
  push(i, ss, se);
  if (ss > se or l > se or r < ss) return;
  if (ss >= l and se <= r) {
    pend2[i] = val;
    push(i, ss, se);
    return;
  }
  forc(l, r, val, ss, sm, sl);
  forc(l, r, val, sm + 1, se, sr);

  tree[i] = max(tree[sl], tree[sr]);
}

int get(int l, int r, int ss = 0, int se = 200000, int i = 0) {
  push(i, ss, se);
  if (ss > se or ss > r or se < l) return 0;
  if (ss >= l and se <= r) return tree[i];
  return max(get(l, r, ss, sm, sl), get(l, r, sm + 1, se, sr));
}


std::vector<signed> distribute_candies(std::vector<signed> c, std::vector<signed> l,
                                    std::vector<signed> r, std::vector<signed> v) {
  int n = c.size();
  int q = l.size();
  vector<pair<int, int>> all;
  for (int i = 0; i < n; ++i) all.push_back({c[i], i});
  sort(all.begin(), all.end());

  pre[0] = all[0].first;
  for (int i = 1; i < n; ++i) {
    pre[i] = pre[i - 1] + all[i].first;
  }

  // for (int i = 0; i < n; ++i) {
  //   cout << pre[i] << ' ';
  // }
  // cout << endl;

  for (int i = 0; i < q; ++i) {
    int x = v[i];
    if (x > 0) {
      int lo = 0, hi = n - 1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (get(0, mid) + x < all[mid].first) hi = mid - 1;
        else lo = mid + 1;
      }
      // hi = -1;
      if (hi != -1) {
        forc(0, hi, 2);
      }
      // cout << hi << endl;
      upd(hi + 1, n - 1, x);
      // cout << get(0, n - 1) << endl;
    } else {
      x *= -1;
      int lo = 0, hi = n - 1;
      while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (get(0, mid) > x) {
          hi = mid - 1;
        } else {
          lo = mid + 1;
        }
      }
      // cout << hi << endl;
      // hi = -1;
      if (hi != -1) {
        forc(0, hi, 1);
      }
      upd(hi + 1, n - 1, -x);
    }
  }

  std::vector<signed> s(n);
  for (int i = 0; i < n; ++i) {
    s[all[i].second] = get(i, i);
  }
  return s;
}

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