Submission #735744

#	Time	Username	Problem	Language	Result	Execution time	Memory
735744		cadmiumsky	Meetings (IOI18_meetings)	C++17	100 / 100	4849 ms	424336 KiB

meetings

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

using namespace std;

using ll = long long;
//#define int ll
using pii = pair<int,int>;
#define sz(x) ((int)(x).size())

const int nmax = 75e4 + 5;
const int nbit = 20;
const ll inf = 4e18 + 5;

namespace RMQ {
  vector<signed> costs;
  int rmq[nbit][nmax];
  int lg2[nmax];
  void init(vector<signed> H) {
    costs = move(H);
    int n = sz(costs);
    for(int i = 2; i <= n; i++)
      lg2[i] = lg2[i >> 1] + 1;
    for(int i = 0; i < n; i++)
      rmq[0][i] = i;
    for(int step = 1; step < nbit; step++)
      for(int i = 0; i + (1 << step) <= n; i++)
        rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]);
  }
  int query(int l, int r) {
    int step = lg2[r - l + 1];
    return costs[rmq[step][l]] <= costs[rmq[step][r - (1 << step) + 1]]? rmq[step][r - (1 << step) + 1] : rmq[step][l];
  }
};

pii qs[nmax];
ll rez[nmax];

struct line {
  ll m, b;
  line(ll x = 0, ll y = inf): m(x), b(y) {;}
  ll operator()(const ll& x) const {
    return m * x + b;
  }
  line operator + (const line& x) const { return line(x.m + m, min(inf, x.b + b)); }
  line operator += (const line& x) { return *this = *this + x; }
};

int N;

struct LiChao {
  line aint[nmax * 4];
  line lazy[nmax * 4];
  
  void pushlazy(int node) {
    aint[2 * node] += lazy[node];
    aint[2 * node + 1] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
    lazy[2 * node] += lazy[node];
    lazy[node] = line(0, 0);
  }
  void forcepush(line x, int node, int cl, int cr) {
    int mid = cl + cr >> 1;
    if(x(mid) < aint[node](mid)) {
      swap(x, aint[node]);
    }
    if(cl == cr) return;
    pushlazy(node);
    if(x(cl) < aint[node](cl))
      forcepush(x, 2 * node, cl, mid);
    else 
      forcepush(x, 2 * node + 1, mid + 1, cr);
    return;
  }
  void pushline(int node, int cl, int cr) {
    int mid = cl + cr >> 1;
    forcepush(aint[node], 2 * node, cl, mid);
    forcepush(aint[node], 2 * node + 1, mid + 1, cr);
    aint[node] = line();
  }
  
  void maxline(int l, int r, line x, int node, int cl, int cr) {
    if(r < cl || cr < l) return;
    if(l <= cl && cr <= r) { forcepush(x, node, cl, cr); return; }
    pushlazy(node);
    int mid = cl + cr >> 1;
    maxline(l, r, x, 2 * node, cl, mid);
    maxline(l, r, x, 2 * node + 1, mid + 1, cr);
  }
  void addline(int l, int r, line x, int node, int cl, int cr) {
    if(r < cl || cr < l) return;
    if(l <= cl && cr <= r) {
      aint[node] += x;
      lazy[node] += x;
      return;
    }
    pushlazy(node);
    //pushline(node, cl, cr);
    int mid = cl + cr >> 1;
    addline(l, r, x, 2 * node, cl, mid);
    addline(l, r, x, 2 * node + 1, mid + 1, cr);
  }
  ll query(int p, int node, int cl, int cr) {
    if(cr < p || p < cl) return inf;
    if(cl == cr) {return aint[node](p); }
    int mid = cl + cr >> 1;
    pushlazy(node);
    if(p <= mid)
      return min(aint[node](p), query(p, 2 * node, cl, mid));
    return min(aint[node](p), query(p, 2 * node + 1, mid + 1, cr));
  }
  
  ll query(int p) { return query(p, 1, 0, N - 1); }
  void addline(int l, int r, line x) { addline(l, r, x, 1, 0, N - 1); }
  void maxline(int l, int r, line x) { maxline(l, r, x, 1, 0, N - 1); }
};

namespace CartTree {
  int Ls[nmax], Rs[nmax];
  int L[nmax], R[nmax];
  ll val[nmax];
  vector<int> atrqs[nmax];
  int root;
  
  LiChao toleft, toright;
  
  void init(vector<signed> H) {
    vector<int> st;
    for(int i = 0; i < sz(H); i++) {
      val[i] = H[i];
      int last = -1;
      while(!st.empty() && H[st.back()] <= H[i])
        R[st.back()] = i - 1,
        last = st.back(),
        st.pop_back();
      
      L[i] = (st.empty()? 0 : st.back() + 1); 
      Ls[i] = last;
      Rs[i] = -1;
      if(!st.empty())
        Rs[st.back()] = i;
      else
        root = i;
      
      st.emplace_back(i);
    }
    for(auto x : st)
      R[x] = sz(H) - 1;
  }
  
  void push(int idx, int l, int r) {
    int mid = RMQ::query(l, r);
    atrqs[mid].emplace_back(idx);
  }
  
  void start(int node) {
    if(node == -1)
      return;
    
    start(Ls[node]);
    start(Rs[node]);
    
    for(auto idx : atrqs[node]) {
      auto [l, r] = qs[idx];
      ll lv = (l == node? 0 : toright.query(l));
      ll rv = (r == node? 0 : toleft.query(r));
      lv += val[node] * (r - node + 1);
      rv += val[node] * (node - l + 1);
      rez[idx] = min({lv, rv, (r - l + 1) * val[node]});
    }
    
    auto [l, r] = pii{L[node], R[node]};
    toleft.addline(node, r, line{0, (node - l + 1) * val[node]});
    toleft.maxline(node, r, line(val[node], (l == node? 0 : toleft.query(node - 1)) + -(node - 1) * val[node]));
    
    toright.addline(l, node, line{0, (r - node + 1) * val[node]});
    toright.maxline(l, node, line(-val[node], (r == node? 0 : toright.query(node + 1)) + (node + 1) * val[node]));
    
    return;
  }
}

std::vector<long long> minimum_costs(std::vector<signed> H, std::vector<signed> L, std::vector<signed> R) {
  N = sz(H);
  
  CartTree::init(H);
  RMQ::init(H);
  
  for(int i = 0; i < sz(L); i++) {
    qs[i] = pii{L[i], R[i]};
    CartTree::push(i, L[i], R[i]);
  }
  
  CartTree::start(CartTree::root);
  
  vector<ll> r;
  r.reserve(sz(L));
  for(int i = 0; i < sz(L); i++)
    r.emplace_back(rez[i]);
  return r;
}
//#undef int

Compilation message (stderr)

meetings.cpp: In function 'void RMQ::init(std::vector<int>)':
meetings.cpp:28:87: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |         rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]);
      |                                                                                  ~~~~~^~~
meetings.cpp:28:124: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   28 |         rmq[step][i] = (costs[rmq[step - 1][i]] <= costs[rmq[step - 1][i + (1 << step - 1)]]? rmq[step - 1][i + (1 << step - 1)] : rmq[step - 1][i]);
      |                                                                                                                       ~~~~~^~~
meetings.cpp: In member function 'void LiChao::forcepush(line, int, int, int)':
meetings.cpp:63:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'void LiChao::pushline(int, int, int)':
meetings.cpp:76:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'void LiChao::maxline(int, int, line, int, int, int)':
meetings.cpp:86:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'void LiChao::addline(int, int, line, int, int, int)':
meetings.cpp:99:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   99 |     int mid = cl + cr >> 1;
      |               ~~~^~~~
meetings.cpp: In member function 'll LiChao::query(int, int, int, int)':
meetings.cpp:106:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |     int mid = cl + cr >> 1;
      |               ~~~^~~~

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