oj.uz

Submission #968589

# Submission time Handle Problem Language Result Execution time Memory
968589 2024-04-23T16:28:11 Z IUA_Hasin Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 29520 KB 
#include "candies.h"

#include <algorithm>
#include <vector>

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(), q = v.size();
  std::vector<std::vector<std::pair<int, int>>> queriesL(n), queriesR(n);
  for (int i = 0; i < q; ++i) {
    queriesL[l[i]].emplace_back(i, v[i]);
    queriesR[r[i]].emplace_back(i, v[i]);
  }

  std::vector<int> s(n), vals(q);
  for (int i = 0; i < n; ++i) {
    for (auto [idx, val] : queriesL[i]) {
      vals[idx] = -val;
    }

    int mini = 0, maxi = 0, sum = 0, idx = 0;
    for (int j = q - 1; j >= 0; --j) {
      sum += vals[j];
      mini = std::min(mini, sum);
      maxi = std::max(maxi, sum);
      if (maxi - mini > c[i]) {
        idx = j;
        break;
      }
    }

    if (maxi - mini <= c[i]) {
      s[i] = -mini;
    } else {
      if (vals[idx] < 0) {
        s[i] = c[i] - maxi;
      } else {
        s[i] = -mini;
      }
    }

    for (auto [idx, val] : queriesR[i]) {
      vals[idx] = 0;
    }
  }

  return s;
}

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 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1217 ms 25588 KB Output is correct
2 Execution timed out 5013 ms 29520 KB Time limit exceeded
3 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 504 ms 11564 KB Output is correct
3 Correct 486 ms 12120 KB Output is correct
4 Execution timed out 5043 ms 25524 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 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 125 ms 9164 KB Output is correct
4 Correct 167 ms 12264 KB Output is correct
5 Execution timed out 5077 ms 20544 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 348 KB Output is correct
5 Correct 2 ms 604 KB Output is correct
6 Correct 1217 ms 25588 KB Output is correct
7 Execution timed out 5013 ms 29520 KB Time limit exceeded
8 Halted 0 ms 0 KB -