Submission #520218

#	Time	Username	Problem	Language	Result	Execution time	Memory
520218		ivan_tudor	Distributing Candies (IOI21_candies)	C++17	8 / 100	495 ms	38976 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
const int N = 200005;
struct saint{
  long long mx, mn;
};
long long lazy[4*N];
saint aint[4*N];
void push(int nod, int l, int r){
  aint[nod].mx += lazy[nod];
  aint[nod].mn += lazy[nod];
  if(l != r){
    lazy[2*nod] += lazy[nod];
    lazy[2*nod + 1] += lazy[nod];
  }
  lazy[nod] = 0;
}
saint join(saint a, saint b){
  saint res;
  res.mx = max(a.mx, b.mx);
  res.mn = min(a.mn, b.mn);
  return res;
}
void aint_update(int nod, int l, int r, int ul, int ur, long long val){
  push(nod, l, r);
  if(r < ul || ur < l)
    return;
  if(ul <= l && r <= r){
    lazy[nod] += val;
    push(nod, l, r);
    return;
  }
  int mid = (l + r)/2;
  aint_update(2*nod, l, mid, ul, ur, val);
  aint_update(2*nod + 1, mid + 1, r, ul, ur, val);
  aint[nod] = join(aint[2*nod], aint[2*nod + 1]);
}
long long aint_query(int nod, int l, int r, int pz){
  push(nod, l, r);
  if(pz < l || pz > r)
    return LLONG_MIN;
  if(l == r)
    return aint[nod].mx;
  int mid =  (l + r)/2;
  return max(aint_query(2*nod, l, mid, pz), aint_query(2*nod + 1, mid + 1, r, pz));
}
int aint_cautb(int nod, int l, int r, long long c, long long &mxy, long long &mni){
  push(nod, l, r);
  long long cmx = mxy, cmn = mni;
  cmx = max(cmx, aint[nod].mx);
  cmn = min(cmn, aint[nod].mn);
  if(cmx - cmn <= c){
    mxy = cmx;
    mni = cmn;
    return l;
  }
  if(l == r){
    return r + 1;
  }
  int mid = (l + r)/2;
  int poz = aint_cautb(2*nod + 1, mid + 1, r, c, mxy, mni);
  if(poz > mid + 1)
    return poz;
  return aint_cautb(2*nod, l, mid, c, mxy, mni);
}
struct update{
  int id;
  long long val;
};
vector<update> upd[N];
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int n = c.size();
    std::vector<int> s(n);
    int rmax = r.size();
    for(int i = 0; i < r.size();i ++){
      upd[l[i]].push_back({i + 1, v[i]});
      upd[r[i] + 1].push_back({i + 1, -v[i]});
    }
    for(int i = 0; i < n; i++){
      for(auto x:upd[i]){
        aint_update(1, 0, rmax, x.id, rmax, x.val);
      }
      long long mxc = LLONG_MIN, mnc = LLONG_MAX;
      int pzm = aint_cautb(1, 0, rmax, c[i], mxc, mnc);
      long long last_val = aint_query(1, 0, rmax, rmax);
      if(pzm == 0){
        s[i] = last_val;
      }
      else{
        long long val = aint_query(1, 0, rmax, pzm - 1);
        if(val > mxc){
          s[i]  = last_val - mnc;
        }
        else if(val < mnc){
          s[i] = last_val - (mxc - c[i]);
        }
        else{
          assert(0);
        }
      }
    }
    return s;
}

Compilation message (stderr)

candies.cpp: In function 'void aint_update(int, int, int, int, int, long long int)':
candies.cpp:30:19: warning: self-comparison always evaluates to true [-Wtautological-compare]
   30 |   if(ul <= l && r <= r){
      |                 ~ ^~ ~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |     for(int i = 0; i < r.size();i ++){
      |                    ~~^~~~~~~~~~

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