oj.uz

Submission #735744

# Submission time Handle Problem Language Result Execution time Memory
735744 2023-05-04T14:23:34 Z cadmiumsky Meetings (IOI18_meetings) C++17
100 / 100
 4849 ms 424336 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 205824 KB Output is correct
2 Correct 95 ms 206084 KB Output is correct
3 Correct 84 ms 206096 KB Output is correct
4 Correct 85 ms 206176 KB Output is correct
5 Correct 85 ms 206080 KB Output is correct
6 Correct 85 ms 206212 KB Output is correct
7 Correct 87 ms 206168 KB Output is correct
8 Correct 89 ms 206232 KB Output is correct
9 Correct 91 ms 206276 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 205824 KB Output is correct
2 Correct 95 ms 206084 KB Output is correct
3 Correct 84 ms 206096 KB Output is correct
4 Correct 85 ms 206176 KB Output is correct
5 Correct 85 ms 206080 KB Output is correct
6 Correct 85 ms 206212 KB Output is correct
7 Correct 87 ms 206168 KB Output is correct
8 Correct 89 ms 206232 KB Output is correct
9 Correct 91 ms 206276 KB Output is correct
10 Correct 90 ms 206592 KB Output is correct
11 Correct 90 ms 206660 KB Output is correct
12 Correct 97 ms 206552 KB Output is correct
13 Correct 104 ms 206608 KB Output is correct
14 Correct 91 ms 206884 KB Output is correct
15 Correct 92 ms 206532 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 205832 KB Output is correct
2 Correct 128 ms 209288 KB Output is correct
3 Correct 357 ms 225908 KB Output is correct
4 Correct 380 ms 220568 KB Output is correct
5 Correct 343 ms 227772 KB Output is correct
6 Correct 355 ms 227968 KB Output is correct
7 Correct 419 ms 228452 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 205832 KB Output is correct
2 Correct 128 ms 209288 KB Output is correct
3 Correct 357 ms 225908 KB Output is correct
4 Correct 380 ms 220568 KB Output is correct
5 Correct 343 ms 227772 KB Output is correct
6 Correct 355 ms 227968 KB Output is correct
7 Correct 419 ms 228452 KB Output is correct
8 Correct 331 ms 221084 KB Output is correct
9 Correct 293 ms 221032 KB Output is correct
10 Correct 309 ms 221124 KB Output is correct
11 Correct 340 ms 220632 KB Output is correct
12 Correct 292 ms 220660 KB Output is correct
13 Correct 301 ms 220780 KB Output is correct
14 Correct 357 ms 225968 KB Output is correct
15 Correct 311 ms 220568 KB Output is correct
16 Correct 432 ms 226076 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 205824 KB Output is correct
2 Correct 95 ms 206084 KB Output is correct
3 Correct 84 ms 206096 KB Output is correct
4 Correct 85 ms 206176 KB Output is correct
5 Correct 85 ms 206080 KB Output is correct
6 Correct 85 ms 206212 KB Output is correct
7 Correct 87 ms 206168 KB Output is correct
8 Correct 89 ms 206232 KB Output is correct
9 Correct 91 ms 206276 KB Output is correct
10 Correct 90 ms 206592 KB Output is correct
11 Correct 90 ms 206660 KB Output is correct
12 Correct 97 ms 206552 KB Output is correct
13 Correct 104 ms 206608 KB Output is correct
14 Correct 91 ms 206884 KB Output is correct
15 Correct 92 ms 206532 KB Output is correct
16 Correct 86 ms 205832 KB Output is correct
17 Correct 128 ms 209288 KB Output is correct
18 Correct 357 ms 225908 KB Output is correct
19 Correct 380 ms 220568 KB Output is correct
20 Correct 343 ms 227772 KB Output is correct
21 Correct 355 ms 227968 KB Output is correct
22 Correct 419 ms 228452 KB Output is correct
23 Correct 331 ms 221084 KB Output is correct
24 Correct 293 ms 221032 KB Output is correct
25 Correct 309 ms 221124 KB Output is correct
26 Correct 340 ms 220632 KB Output is correct
27 Correct 292 ms 220660 KB Output is correct
28 Correct 301 ms 220780 KB Output is correct
29 Correct 357 ms 225968 KB Output is correct
30 Correct 311 ms 220568 KB Output is correct
31 Correct 432 ms 226076 KB Output is correct
32 Correct 2516 ms 326392 KB Output is correct
33 Correct 1900 ms 348132 KB Output is correct
34 Correct 2171 ms 344376 KB Output is correct
35 Correct 2642 ms 345656 KB Output is correct
36 Correct 1990 ms 346488 KB Output is correct
37 Correct 2105 ms 344628 KB Output is correct
38 Correct 3189 ms 385676 KB Output is correct
39 Correct 3220 ms 385652 KB Output is correct
40 Correct 2709 ms 350024 KB Output is correct
41 Correct 4610 ms 421320 KB Output is correct
42 Correct 4849 ms 424236 KB Output is correct
43 Correct 4760 ms 424336 KB Output is correct
44 Correct 3860 ms 385160 KB Output is correct