Submission #439911

#	Time	Username	Problem	Language	Result	Execution time	Memory
439911		loctildore	Distributing Candies (IOI21_candies)	C++17	0 / 100	1282 ms	49712 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define x first
#define y second
#define elif else if
#define endl '\n'
#define all(x) begin(x), end(x)
template <typename T>
ostream& operator << (ostream& os, const vector<T>& a) {
    os << '[';
    bool E = false;
    for(const T& x : a) {
        if(E) os << ' ';
        os << x;
        E = true;
    }
    return os << ']';
}
struct node{
  ll l,r;
  node *lft = NULL,*rght = NULL;
  ll offset = 0, minimum = 0, maximum = 0;
  //offset is already applied to min/max at this layer
  node(ll ltemp, ll rtemp){
    l=ltemp;r=rtemp;
  }
};
void add(node *x, ll l, ll r, ll val) {
  if (r <= x->l||x->r <= l) {
    return;
  }
  if (l <= x->l&&x->r <= r) {
    x->offset+=val;
    x->minimum+=val;
    x->maximum+=val;
    return;
  }
  if (x->lft == NULL){
    x->lft = new node(x->l,(x->l+x->r)/2);
  }
  if (x->rght == NULL){
    x->rght = new node((x->l+x->r)/2,x->r);
  }
  add(x->lft,l,r,val);
  add(x->rght,l,r,val);
  x->minimum=min(x->lft->minimum,x->rght->minimum)+x->offset;
  x->maximum=max(x->lft->maximum,x->rght->minimum)+x->offset;
}
ll findval(node *x, ll poll){
  if (poll < x->l||x->r <= poll) {
    return LLONG_MIN;
  }
  if (x->l+1==x->r) {
    return x->offset;
  }
  if (x->lft == NULL){
    x->lft = new node(x->l,(x->l+x->r)/2);
  }
  if (x->rght == NULL){
    x->rght = new node((x->l+x->r)/2,x->r);
  }
  ll temp = findval(x->lft, poll);
  if (temp == LLONG_MIN){
    temp = findval(x->rght, poll);
  }
  return temp+x->offset;
}
pair<ll,ll> limitfind(node *x, ll l, ll r){
  if (r <= x->l||x->r <= l) {
    return {LLONG_MIN,LLONG_MAX};
  }
  if (l <= x->l&&x->r <= r) {
    return {x->maximum,x->minimum};
  }
  if (x->lft == NULL){
    x->lft = new node(x->l,(x->l+x->r)/2);
  }
  if (x->rght == NULL){
    x->rght = new node((x->l+x->r)/2,x->r);
  }
  pair<ll,ll> tempa=limitfind(x->lft,l,r);
  pair<ll,ll> tempb=limitfind(x->rght,l,r);
  return {max(tempa.f,tempb.f)+x->offset,min(tempa.s,tempb.s)+x->offset};
}
node *root;
vector<ll> strt[200069],nd[200069];
vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
  root=new node(0,200069);
  vector<int> rtn;
  for (ll i = 0; i < v.size(); i++) {
    strt[l[i]].push_back(i);
    nd[r[i]+1].push_back(i);
  }
  add(root,0,200069,1000000069);
  add(root,1,200069,-1000000069);
  for (ll i = 0; i < c.size(); i++) {
    for (ll j : strt[i]) {
      add(root,j+2,200069,v[j]);
    }
    for (ll j : nd[i]) {
      add(root,j+2,200069,-v[j]);
    }
    ll s=-1,e=200068;
    while (s+1!=e) {
      ll m=e-(e-s)/2;
      pair<ll,ll> temp=limitfind(root, m, 200069);
      if (temp.f-temp.s<=c[i]){
        e=m;
      }
      else{
        s=m;
      }
    }
    ll temp=findval(root, 200068)-findval(root, e);
    if (findval(root, e)-findval(root, e-1)>0) {
      temp+=c[i];
    }
    if (temp<0||temp>c[i]) {
      //if this works I'm a god
      e++;
      temp=findval(root, 200068)-findval(root, e);
      if (findval(root, e)-findval(root, e-1)>0) {
        temp+=c[i];
      }
    }
    rtn.push_back(temp);
  }
  return rtn;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:94:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for (ll i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
candies.cpp:100:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |   for (ll i = 0; i < c.size(); i++) {
      |                  ~~^~~~~~~~~~

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