oj.uz

Submission #439911

# Submission time Handle Problem Language Result Execution time Memory
439911 2021-07-01T07:56:48 Z loctildore Distributing Candies (IOI21_candies) C++17
0 / 100
 1282 ms 49712 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Incorrect 6 ms 9676 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1282 ms 49712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 9676 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9648 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9676 KB Output is correct
2 Incorrect 6 ms 9676 KB Output isn't correct
3 Halted 0 ms 0 KB -