oj.uz

Submission #999351

# Submission time Handle Problem Language Result Execution time Memory
999351 2024-06-15T10:42:15 Z 우민규(#10874) Distributing Candies (IOI21_candies) C++17
29 / 100
 91 ms 11600 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) {
  int offsety = 0;
  // {y, x} act coord {y+offsety, x}
  vector<pair<int64_t, int64_t>> line{{0, INT64_MAX}, {0, 0}};
  for (int i = 0; i < l.size(); ++i) {
    int vi = v[i];
    offsety += vi;
    pair<int64_t, int64_t> pp{-1, -1};
    while (!line.empty() && line.back().first + offsety < 0 ||
           line.back().first + offsety >= line.back().second) {
      pp = line.back();
      line.pop_back();
    }
    if (line.empty()) {
      offsety = 0;
      line.push_back({0, INT64_MAX});
      line.push_back({0, 0});
    } else if (line.back().first == pp.first) {
      line.push_back({pp.first, pp.first + offsety});
      line.push_back({-offsety, 0});
    } else {
      line.push_back(
          {-offsety, line.back().second - (line.back().first + offsety)});
      line.push_back({-offsety, 0});
    }
  }
  reverse(line.begin(), line.end());
  for (int i = 0; i < c.size(); ++i) {
    auto it =
        lower_bound(line.begin(), line.end(), pair<int64_t, int64_t>{0, c[i]},
                    [&](pair<int64_t, int64_t> a, pair<int64_t, int64_t> b) {
                      return tie(a.second, a.first) < tie(b.second, b.first);
                    });

    auto a = *it;
    auto b = *--it;
    c[i] = offsety + b.first + (c[i] - b.second) * (b.first != a.first);
  }
  return c;
}

#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:76:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for (int i = 0; i < l.size(); ++i) {
      |                   ~~^~~~~~~~~~
candies.cpp:80:26: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   80 |     while (!line.empty() && line.back().first + offsety < 0 ||
      |            ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
candies.cpp:99:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |   for (int i = 0; i < c.size(); ++i) {
      |                   ~~^~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 34 ms 5104 KB Output is correct
4 Correct 32 ms 2904 KB Output is correct
5 Correct 67 ms 6604 KB Output is correct
6 Correct 91 ms 10832 KB Output is correct
7 Correct 72 ms 11600 KB Output is correct
8 Correct 68 ms 10064 KB Output is correct
9 Correct 64 ms 11444 KB Output is correct

Subtask #5
0 / 33.0

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