Submission #425202

#	Time	Username	Problem	Language	Result	Execution time	Memory
425202		Tangent	Meetings (IOI18_meetings)	C++17	17 / 100	81 ms	4532 KiB

meetings

#include "meetings.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<vii> vvii;
typedef vector<vll> vvll;
typedef vector<vpii> vvpii;
typedef vector<vpll> vvpll;

#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(a) a.begin(), a.end()

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int Q = L.size();
  int N = H.size();

  vpii segments;
  vii segment(N);
  rep(i, N) {
    if (H[i] == 1) {
      if (i && H[i - 1] == 1) {
        segments.back().second++;
      } else {
        segments.emplace_back(i, i + 1);
      }
      segment[i] = segments.size() - 1;
    } else {
      segment[i] = segments.size();
    }
  }

  vii t(2 * segments.size());
  rep(i, segments.size()) {
    t[segments.size() + i] = segments[i].second - segments[i].first;
  }
  for (int i = segments.size() - 1; i > 0; i--) {
    t[i] = max(t[i * 2], t[i * 2 + 1]);
  }
  vll res(Q);
  rep(i, Q) {
    int best = 0;
    int l, r;
    if (H[L[i]] == 1) {
      best = max(best, min(R[i] + 1, segments[segment[L[i]]].second) - L[i]);
      l = segment[L[i]] + 1;
    } else {
      l = segment[L[i]];
    }
    if (H[R[i]] == 1) {
      best = max(best, R[i] - max(L[i], segments[segment[R[i]]].first) + 1);
      r = segment[R[i]];
    } else {
      r = segment[R[i]];
    }
    if (l < r) {
      l += segments.size();
      r += segments.size();
      int curr = 0;
      while (l < r) {
        if (l % 2) {
          curr = max(curr, t[l++]);
        }
        if (r % 2) {
          curr = max(curr, t[--r]);
        }
        l /= 2;
        r /= 2;
      }
      best = max(best, curr);
    }
    res[i] = (R[i] - L[i] + 1) * 2 - best; 
  }
  return res;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:18:40: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 | #define ffor(i, a, b) for (ll i = a; i < b; i++)
      |                                        ^
meetings.cpp:19:19: note: in expansion of macro 'ffor'
   19 | #define rep(i, n) ffor(i, 0, n)
      |                   ^~~~
meetings.cpp:44:3: note: in expansion of macro 'rep'
   44 |   rep(i, segments.size()) {
      |   ^~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40