oj.uz

Submission #546824

# Submission time Handle Problem Language Result Execution time Memory
546824 2022-04-08T14:38:10 Z Trisanu_Das 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1524 ms 25420 KB Output is correct
2 Execution timed out 5076 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 1 ms 340 KB Output is correct
2 Correct 620 ms 11440 KB Output is correct
3 Correct 601 ms 12204 KB Output is correct
4 Execution timed out 5060 ms 25392 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 159 ms 9032 KB Output is correct
4 Correct 199 ms 12136 KB Output is correct
5 Execution timed out 5028 ms 20640 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 1524 ms 25420 KB Output is correct
7 Execution timed out 5076 ms 29520 KB Time limit exceeded
8 Halted 0 ms 0 KB -