oj.uz

Submission #999345

# Submission time Handle Problem Language Result Execution time Memory
999345 2024-06-15T10:28:04 Z 우민규(#10874) Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 10860 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) {
  vector<int> vals(c.size(), 0);
  for (int i = 0; i < l.size(); ++i) {
    int li = l[i];
    int ri = r[i] + 1;
    int vi = v[i];
    for (int i = li; i < ri; ++i) {
      vals[i] += vi;
      vals[i] = min(vals[i], c[i]);
      vals[i] = max(vals[i], 0);
    }
  }
  return vals;
}

#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) {
      |                   ~~^~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 348 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5089 ms 7400 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 127 ms 5104 KB Output is correct
3 Correct 123 ms 3904 KB Output is correct
4 Execution timed out 5049 ms 7504 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 312 ms 7792 KB Output is correct
4 Correct 314 ms 4028 KB Output is correct
5 Execution timed out 5072 ms 10860 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 600 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Execution timed out 5089 ms 7400 KB Time limit exceeded
7 Halted 0 ms 0 KB -