Submission #102846

#	Time	Username	Problem	Language	Result	Execution time	Memory
102846		wxh010910	Meetings (IOI18_meetings)	C++17	100 / 100	3537 ms	421616 KiB

meetings

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

using namespace std;

typedef long long ll;

struct node_t {
  int left, right;
  ll k, b, l, r;
  bool cover;

  node_t(bool cover = false, ll k = 0, ll b = 0):cover(cover), k(k), b(b) {
  }

  void apply(node_t tag) {
    if (tag.cover) {
      k = b = l = r = 0;
      cover = true;
    }
    k += tag.k;
    b += tag.b;
    l += tag.k * left + tag.b;
    r += tag.k * right + tag.b;
  }

  void reset() {
    k = b = 0;
    cover = false;
  }
};

class segtree_t {
  vector<node_t> tree;
  int n;

  void build(int x, int l, int r) {
    tree[x].left = l;
    tree[x].right = r;
    if (l != r) {
      int y = l + r >> 1, z = x + (y - l + 1 << 1);
      build(x + 1, l, y);
      build(z, y + 1, r);
    }
  }

  void push(int x, int z) {
    if (tree[x].cover || tree[x].k || tree[x].b) {
      tree[x + 1].apply(tree[x]);
      tree[z].apply(tree[x]);
      tree[x].reset();
    }
  }

  void pull(int x, int z) {
    tree[x].l = tree[x + 1].l;
    tree[x].r = tree[z].r;
  }

  ll query(int x, int l, int r, int p) {
    if (l == r) {
      return tree[x].l;
    } else {
      int y = l + r >> 1, z = x + (y - l + 1 << 1);
      push(x, z);
      if (p <= y) {
        return query(x + 1, l, y, p);
      } else {
        return query(z, y + 1, r, p);
      }
    }
  }

  void add(int x, int l, int r, int ql, int qr, ll value) {
    if (l == ql && r == qr) {
      tree[x].apply(node_t(false, 0, value));
    } else {
      int y = l + r >> 1, z = x + (y - l + 1 << 1);
      push(x, z);
      if (qr <= y) {
        add(x + 1, l, y, ql, qr, value);
      } else if (ql > y) {
        add(z, y + 1, r, ql, qr, value);
      } else {
        add(x + 1, l, y, ql, y, value);
        add(z, y + 1, r, y + 1, qr, value);
      }
      pull(x, z);
    }
  }

  void merge(int x, int l, int r, int ql, int qr, ll k, ll b) {
    if (l == ql && r == qr) {
      ll my_l = k * l + b, my_r = k * r + b;
      if (my_l >= tree[x].l && my_r >= tree[x].r) {
        return;
      }
      if (tree[x].l >= my_l && tree[x].r >= my_r) {
        tree[x].apply(node_t(true, k, b));
        return;
      }
    }
    int y = l + r >> 1, z = x + (y - l + 1 << 1);
    push(x, z);
    if (qr <= y) {
      merge(x + 1, l, y, ql, qr, k, b);
    } else if (ql > y) {
      merge(z, y + 1, r, ql, qr, k, b);
    } else {
      merge(x + 1, l, y, ql, y, k, b);
      merge(z, y + 1, r, y + 1, qr, k, b);
    }
    pull(x, z);
  }

 public:
  segtree_t(int n):n(n) {
    tree.resize((n << 1) - 1);
    build(0, 0, n - 1);
  }

  ll query(int p) {
    return query(0, 0, n - 1, p);
  }

  void add(int l, int r, ll value) {
    add(0, 0, n - 1, l, r, value);
  }

  void merge(int l, int r, ll k, ll b) {
    merge(0, 0, n - 1, l, r, k, b);
  }
};

vector<ll> minimum_costs(vector<int> h, vector<int> l, vector<int> r) {
  int n = h.size(), log_n = 0;
  while (1 << log_n <= n) {
    ++log_n;
  }

  auto my_max = [&](int x, int y) {
    return h[x] < h[y] ? y : x;
  };

  vector<vector<int>> rmq(log_n, vector<int> (n));
  vector<int> length(n);
  for (int i = 0; i < n; ++i) {
    rmq[0][i] = i;
  }
  for (int i = 1; i < log_n; ++i) {
    for (int j = 0; j + (1 << i) <= n; ++j) {
      rmq[i][j] = my_max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]);
    }
  }
  for (int i = 2; i < n; ++i) {
    length[i] = length[i >> 1] + 1;
  }

  auto query_my_max = [&](int l, int r) {
    int k = length[r - l];
    return my_max(rmq[k][l], rmq[k][r - (1 << k) + 1]);
  };

  int m = l.size();
  vector<ll> answer(m);
  vector<vector<int>> event(n);
  for (int i = 0; i < m; ++i) {
    event[query_my_max(l[i], r[i])].push_back(i);
  }
  segtree_t prefix(n), suffix(n);
  
  function<void(int, int)> solve = [&](int left, int right) {
    int mid = query_my_max(left, right);
    if (left < mid) {
      solve(left, mid - 1);
    }
    if (mid < right) {
      solve(mid + 1, right);
    }
    for (auto p : event[mid]) {
      answer[p] = (ll)h[mid] * (r[p] - l[p] + 1);
      if (l[p] < mid) {
        answer[p] = min(answer[p], suffix.query(l[p]) + (ll)h[mid] * (r[p] - mid + 1));
      }
      if (r[p] > mid) {
        answer[p] = min(answer[p], prefix.query(r[p]) + (ll)h[mid] * (mid - l[p] + 1));
      }
    }
    ll prefix_value = h[mid] + (left < mid ? prefix.query(mid - 1) : 0);
    ll suffix_value = h[mid] + (mid < right ? suffix.query(mid + 1) : 0);
    prefix.add(mid, mid, prefix_value);
    suffix.add(mid, mid, suffix_value);
    if (mid < right) {
      prefix.add(mid + 1, right, (ll)h[mid] * (mid - left + 1));
      prefix.merge(mid + 1, right, h[mid], prefix_value - (ll)h[mid] * mid);
    }
    if (left < mid) {
      suffix.add(left, mid - 1, (ll)h[mid] * (right - mid + 1));
      suffix.merge(left, mid - 1, -h[mid], suffix_value + (ll)h[mid] * mid);
    }
  };

  solve(0, n - 1);
  return answer;
}

Compilation message (stderr)

meetings.cpp: In constructor 'node_t::node_t(bool, ll, ll)':
meetings.cpp:11:8: warning: 'node_t::cover' will be initialized after [-Wreorder]
   bool cover;
        ^~~~~
meetings.cpp:10:6: warning:   'll node_t::k' [-Wreorder]
   ll k, b, l, r;
      ^
meetings.cpp:13:3: warning:   when initialized here [-Wreorder]
   node_t(bool cover = false, ll k = 0, ll b = 0):cover(cover), k(k), b(b) {
   ^~~~~~
meetings.cpp: In member function 'void segtree_t::build(int, int, int)':
meetings.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
               ~~^~~
meetings.cpp:41:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
                                    ~~~~~~^~~
meetings.cpp: In member function 'll segtree_t::query(int, int, int, int)':
meetings.cpp:64:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
               ~~^~~
meetings.cpp:64:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
                                    ~~~~~~^~~
meetings.cpp: In member function 'void segtree_t::add(int, int, int, int, int, ll)':
meetings.cpp:78:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
               ~~^~~
meetings.cpp:78:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
       int y = l + r >> 1, z = x + (y - l + 1 << 1);
                                    ~~~~~~^~~
meetings.cpp: In member function 'void segtree_t::merge(int, int, int, int, int, ll, ll)':
meetings.cpp:103:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int y = l + r >> 1, z = x + (y - l + 1 << 1);
             ~~^~~
meetings.cpp:103:40: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
     int y = l + r >> 1, z = x + (y - l + 1 << 1);
                                  ~~~~~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:152:64: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
       rmq[i][j] = my_max(rmq[i - 1][j], rmq[i - 1][j + (1 << i - 1)]);
                                                              ~~^~~

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