oj.uz

Submission #999343

# Submission time Handle Problem Language Result Execution time Memory
999343 2024-06-15T10:25:44 Z 우민규(#10874) Distributing Candies (IOI21_candies) C++17
8 / 100
 180 ms 21296 KB 
#include <bits/stdc++.h>

#include "candies.h"
using namespace std;

// |x| (x+a).max(b).min(c)
struct Clamp {
  int64_t a;
  int64_t b;
  int64_t c;
  // compose
  Clamp operator()(const Clamp& rhs) {
    // {-1, 0, 4}({2, 0, 0})
    // ((x+ra).clamp(rb, rc) + a).clamp(b, c)
    // (x-1).clamp(-1,-1).clamp(0,4)
    // ((x+ra+a).clamp(rb+a,rc+a)).clamp(b, c)
    // (x-1).clamp()
    // (x+ra+a).clamp(max(rb+a, b), min(rc+a, c))
    if (rhs.c + a <= b) {
      return {0, b, b};
    } else if (c <= rhs.b + a) {
      return {0, c, c};
    } else {
      return {rhs.a + a, max(rhs.b + a, b), min(rhs.c + a, c)};
    }
  }
  int64_t operator()(const int64_t rhs) { return min(max(rhs + a, b), c); }
};
const Clamp IDENTITY{0, INT64_MIN / 2, INT64_MAX / 2};

struct Seg {
  int n;
  vector<Clamp> seg;
  Seg(vector<int>& c) {
    n = c.size();
    seg.assign(2 * n, IDENTITY);
    for (int i = 0; i < n; ++i) {
      seg[i + n] = {0, 0, c[i]};
    }
    for (int i = 0; i < n; ++i) seg[i] = IDENTITY;
  }
  void push(int i) {
    for (int j = __lg(n) + 2; j > 0; --j) {
      int k = i >> j;
      seg[2 * k] = seg[k](seg[2 * k]);
      seg[2 * k + 1] = seg[k](seg[2 * k + 1]);
      seg[k] = IDENTITY;
    }
  }
  void apply(int l, int r, Clamp f) {
    l += n, r += n;
    push(l), push(r - 1);
    while (l < r) {
      if (l & 1) {
        seg[l] = f(seg[l]);
        l++;
      }
      if (r & 1) {
        r--;
        seg[r] = f(seg[r]);
      }
      l /= 2, r /= 2;
    }
  }
  Clamp value(int i) {
    push(i + n);
    return seg[i + n];
  }
};

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
  Seg seg(c);
  for (int i = 0; i < l.size(); ++i) {
    int li = l[i];
    int ri = r[i] + 1;
    int vi = v[i];
    seg.apply(li, ri, {vi, 0, INT64_MAX / 2});
  }
  vector<int> ret;
  for (int i = 0; i < c.size(); ++i) {
    ret.push_back(min(seg.value(i)(0), (int64_t)c[i]));
  }
  return ret;
}

#ifndef EVAL
#include "grader.cpp"
#endif

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:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int i = 0; i < l.size(); ++i) {
      |                   ~~^~~~~~~~~~
candies.cpp:81:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for (int i = 0; i < c.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 17012 KB Output is correct
2 Correct 169 ms 21296 KB Output is correct
3 Correct 171 ms 20940 KB Output is correct

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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