oj.uz

답안 #609120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
609120 2022-07-27T12:22:39 Z piOOE 모임들 (IOI18_meetings) C++17
100 / 100
 2968 ms 495336 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const ll inf = 3e18;

struct segtree {
  segtree *left{}, *right{};
  ll lazy_k = -228, lazy_b = 0, first = 0, last = 0;
  //pushed line, value in first point, value in last point
  //if (k == -228) then this is just add b

  void apply(ll k, ll b, int l, int r) {
    if (k == -228) {
      lazy_b += b;
      first += b;
      last += b;
    } else {
      lazy_k = k, lazy_b = b;
      first = k * l + b;
      last = k * (r - 1) + b;
    }
  }

  void push(int l, int r) {
    if (!left) {
      left = new segtree(), right = new segtree();
    }
    int mid = (l + r) >> 1;
    left->apply(lazy_k, lazy_b, l, mid);
    right->apply(lazy_k, lazy_b, mid, r);
    lazy_k = -228, lazy_b = 0;
  }

  void pull() {
    first = left->first;
    last = right->last;
  }

  void update(int l, int r, ll a, ll k, ll b, int lx, int rx) {
    if (l >= rx || lx >= r) {
      return;
    } else if (l <= lx && rx <= r) {
      if (first + a <= k * lx + b) {
        apply(-228, a, lx, rx);
        return;
      } else if (last + a >= k * (rx - 1) + b) {
        apply(k, b, lx, rx);
        return;
      }
    }
    int mid = (lx + rx) >> 1;
    push(lx, rx);
    left->update(l, r, a, k, b, lx, mid);
    right->update(l, r, a, k, b, mid, rx);
    pull();
  }

  ll query(int i, int lx, int rx) {
    if (lx + 1 == rx) {
      return first;
    } else {
      push(lx, rx);
      int mid = (lx + rx) >> 1;
      if (i < mid) {
        return left->query(i, lx, mid);
      } else {
        return right->query(i, mid, rx);
      }
    }
  }
};

vector<ll> minimum_costs(vector<int> h, vector<int> L, vector<int> R) {
  int n = (int) h.size();
  int q = (int) L.size();
  vector<ll> ans(q, inf);
  for (int _ = 0; _ < 2; ++_) {

    int logn = __lg(n) + 1;
    vector<vector<pair<int, int>>> sp(logn);
    for (int l = 0; l < logn; ++l) {
      sp[l].resize(n - (1 << l) + 1);
      for (int i = 0; i <= n - (1 << l); ++i) {
        if (l == 0) {
          sp[l][i] = {h[i], -i};
        } else {
          sp[l][i] = max(sp[l - 1][i], sp[l - 1][i + (1 << (l - 1))]);
        }
      }
    }
    auto get_max = [&](int l, int r) {
      assert(r > l && l >= 0 && r <= n);
      int lg = __lg(r - l);
      return max(sp[lg][l], sp[lg][r - (1 << lg)]);
    };

    vector adj(n, array<int, 2>{-1, -1});
    vector<vector<array<int, 3>>> queries(n);

    vector<int> right(n), left(n);

    vector<int> stk;
    int root = -1;
    for (int i = 0; i < n; ++i) {
      while (!stk.empty() && h[stk.back()] < h[i]) {
        stk.pop_back();
      }
      if (!stk.empty()) {
        adj[i][0] = adj[stk.back()][1];
        adj[stk.back()][1] = i;
      } else {
        adj[i][0] = root;
        root = i;
      }
      stk.push_back(i);
    }

    for (int i = 0; i < q; ++i) {
      auto [hight, j] = get_max(L[i], R[i] + 1);
      j = -j;
      queries[j].push_back({L[i], R[i], i});
    }

    auto *t = new segtree();

    function<void(int)> dfs = [&](int v) {
      for (int to: adj[v]) {
        if (to != -1) {
          dfs(to);
        }
      }
      ll mx = h[v];
      for (auto [l, r, i]: queries[v]) {
        ans[i] = min(ans[i], (v - l + 1) * mx + (r == v ? 0 : t->query(r, 0, n)));
      }
      int l = adj[v][0] == -1 ? v : left[adj[v][0]];
      int r = adj[v][1] == -1 ? v : right[adj[v][1]];
      left[v] = l, right[v] = r;
      t->update(v, r + 1, mx * (v - l + 1), h[v], (l == v ? 0 : t->query(v - 1, 0, n)) - mx * (v - 1), 0, n);
    };

    dfs(root);

    reverse(h.begin(), h.end());
    for (int i = 0; i < q; ++i) {
      L[i] = n - L[i] - 1;
      R[i] = n - R[i] - 1;
      swap(L[i], R[i]);
    }
  }
  return ans;
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Correct 4 ms 1456 KB Output is correct
5 Correct 6 ms 1464 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1464 KB Output is correct
8 Correct 4 ms 1748 KB Output is correct
9 Correct 4 ms 1592 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Correct 4 ms 1456 KB Output is correct
5 Correct 6 ms 1464 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1464 KB Output is correct
8 Correct 4 ms 1748 KB Output is correct
9 Correct 4 ms 1592 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 7 ms 2552 KB Output is correct
12 Correct 9 ms 2524 KB Output is correct
13 Correct 10 ms 2516 KB Output is correct
14 Correct 9 ms 2900 KB Output is correct
15 Correct 8 ms 2516 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 56 ms 6720 KB Output is correct
3 Correct 288 ms 55816 KB Output is correct
4 Correct 256 ms 48312 KB Output is correct
5 Correct 202 ms 57080 KB Output is correct
6 Correct 224 ms 57676 KB Output is correct
7 Correct 284 ms 59432 KB Output is correct

Subtask #4
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 56 ms 6720 KB Output is correct
3 Correct 288 ms 55816 KB Output is correct
4 Correct 256 ms 48312 KB Output is correct
5 Correct 202 ms 57080 KB Output is correct
6 Correct 224 ms 57676 KB Output is correct
7 Correct 284 ms 59432 KB Output is correct
8 Correct 228 ms 49108 KB Output is correct
9 Correct 178 ms 48780 KB Output is correct
10 Correct 230 ms 49084 KB Output is correct
11 Correct 227 ms 48212 KB Output is correct
12 Correct 262 ms 47988 KB Output is correct
13 Correct 236 ms 48544 KB Output is correct
14 Correct 300 ms 55952 KB Output is correct
15 Correct 208 ms 48060 KB Output is correct
16 Correct 281 ms 56128 KB Output is correct

Subtask #5
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 1364 KB Output is correct
3 Correct 6 ms 1364 KB Output is correct
4 Correct 4 ms 1456 KB Output is correct
5 Correct 6 ms 1464 KB Output is correct
6 Correct 5 ms 1620 KB Output is correct
7 Correct 4 ms 1464 KB Output is correct
8 Correct 4 ms 1748 KB Output is correct
9 Correct 4 ms 1592 KB Output is correct
10 Correct 8 ms 2516 KB Output is correct
11 Correct 7 ms 2552 KB Output is correct
12 Correct 9 ms 2524 KB Output is correct
13 Correct 10 ms 2516 KB Output is correct
14 Correct 9 ms 2900 KB Output is correct
15 Correct 8 ms 2516 KB Output is correct
16 Correct 1 ms 304 KB Output is correct
17 Correct 56 ms 6720 KB Output is correct
18 Correct 288 ms 55816 KB Output is correct
19 Correct 256 ms 48312 KB Output is correct
20 Correct 202 ms 57080 KB Output is correct
21 Correct 224 ms 57676 KB Output is correct
22 Correct 284 ms 59432 KB Output is correct
23 Correct 228 ms 49108 KB Output is correct
24 Correct 178 ms 48780 KB Output is correct
25 Correct 230 ms 49084 KB Output is correct
26 Correct 227 ms 48212 KB Output is correct
27 Correct 262 ms 47988 KB Output is correct
28 Correct 236 ms 48544 KB Output is correct
29 Correct 300 ms 55952 KB Output is correct
30 Correct 208 ms 48060 KB Output is correct
31 Correct 281 ms 56128 KB Output is correct
32 Correct 2530 ms 364916 KB Output is correct
33 Correct 1958 ms 380840 KB Output is correct
34 Correct 1899 ms 383596 KB Output is correct
35 Correct 2565 ms 384188 KB Output is correct
36 Correct 1536 ms 381852 KB Output is correct
37 Correct 1770 ms 383980 KB Output is correct
38 Correct 2902 ms 441472 KB Output is correct
39 Correct 2968 ms 441452 KB Output is correct
40 Correct 2170 ms 390856 KB Output is correct
41 Correct 2543 ms 492296 KB Output is correct
42 Correct 2851 ms 494764 KB Output is correct
43 Correct 2910 ms 495336 KB Output is correct
44 Correct 2629 ms 440456 KB Output is correct