oj.uz

Submission #778181

# Submission time Handle Problem Language Result Execution time Memory
778181 2023-07-10T07:08:19 Z NeroZein Meetings (IOI18_meetings) C++17
19 / 100
 5500 ms 7648 KB 
#include "meetings.h"
#include "bits/stdc++.h"
using namespace std; 

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int q = L.size();
  auto go = [&](int l, int r) {
    vector<int> a(r - l + 1);
    for (int i = l; i <= r; ++i) {
      a[i - l] = H[i]; 
    }
    vector<long long> in(r - l + 1);
    for (int it = 0; it < 2; ++it) {
      long long res = 0; 
      stack<pair<int, int>> stk; //element, occ
      for (int i = 0; i < (int) a.size(); ++i) {
        int c = 1; 
        while (!stk.empty() && stk.top().first < a[i]) {
          res -= (long long) stk.top().first * stk.top().second;
          c += stk.top().second;
          stk.pop();
        }
        res += (long long) a[i] * c;
        stk.push({a[i], c}); 
        in[i] += res; 
      }
      reverse(a.begin(), a.end());
      reverse(in.begin(), in.end()); 
    }
    long long mn = LLONG_MAX;
    for (int i = 0; i < (int) a.size(); ++i) {
      mn = min(mn, in[i] - a[i]);
    }
    return mn;
  };
  vector<long long> ans(q); 
  for (int i = 0; i < q; ++i) {
    ans[i] = go(L[i], R[i]); 
  }
  return ans;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 168 ms 628 KB Output is correct
11 Correct 549 ms 636 KB Output is correct
12 Correct 154 ms 644 KB Output is correct
13 Correct 533 ms 636 KB Output is correct
14 Correct 79 ms 656 KB Output is correct
15 Correct 87 ms 640 KB Output is correct

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2055 ms 2424 KB Output is correct
3 Execution timed out 5550 ms 7648 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2055 ms 2424 KB Output is correct
3 Execution timed out 5550 ms 7648 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 168 ms 628 KB Output is correct
11 Correct 549 ms 636 KB Output is correct
12 Correct 154 ms 644 KB Output is correct
13 Correct 533 ms 636 KB Output is correct
14 Correct 79 ms 656 KB Output is correct
15 Correct 87 ms 640 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 2055 ms 2424 KB Output is correct
18 Execution timed out 5550 ms 7648 KB Time limit exceeded
19 Halted 0 ms 0 KB -