oj.uz

Submission #970874

# Submission time Handle Problem Language Result Execution time Memory
970874 2024-04-27T12:34:36 Z nguyentunglam Meetings (IOI18_meetings) C++17
100 / 100
 3099 ms 242376 KB 
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;

const int N = 750'000 + 10;

int pre[N], nxt[N], lg[N], sp[20][N];

long long h[N];

vector<int> query[N];

struct IT {
pair<long long, long long> lazy[N << 2];

void gather(pair<long long, long long> &a, pair<long long, long long> &b) {
  if (b.first != -1e9) a = b;
  else a.second += b.second;
}

void push(int s, int l, int r) {
  if (l == r) return;
  gather(lazy[s << 1], lazy[s]);
  gather(lazy[s << 1 | 1], lazy[s]);
  lazy[s] = make_pair(-1e9, 0);
}

void up(int s, int l, int r, int from, int to, pair<long long, long long> val) {
  push(s, l, r);
  if (l > to || r < from) return;
  if (from <= l && r <= to) {
    gather(lazy[s], val);
    return;
  }
  int mid = l + r >> 1;
  up(s << 1, l, mid, from, to, val);
  up(s << 1 | 1, mid + 1, r, from, to, val);
}

pair<long long, long long> get(int s, int l, int r, int pos) {
  push(s, l, r);
  if (l == r) return lazy[s];
  int mid = l + r >> 1;
  if (pos <= mid) return get(s << 1, l, mid, pos);
  return get(s << 1 | 1, mid + 1, r, pos);
}
} prefix, suffix;

int best(int x, int y) {
  if (h[x] == h[y]) return x < y ? x : y;
  return h[x] > h[y] ? x : y;
}

int getmax (int l, int r) {
  int k = lg[r - l + 1];
  return best(sp[k][l], sp[k][r - (1 << k) + 1]);
}

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();

  for(int i = 0; i < n; i++) sp[0][i] = i, h[i] = H[i];

  for(int i = 2; i <= n; i++) lg[i] = lg[i / 2] + 1;

  for(int j = 1; j <= lg[n]; j++) for(int i = 0; i + (1 << j) - 1 < n; i++) {
    sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
  }

  vector<long long> ans(q);

  for(int i = 0; i < q; i++) {
    ans[i] = 1e18;
//    cout << L[i] << " " << R[i] << " " << h[i] << endl;
    if (L[i] == R[i]) ans[i] = h[L[i]];
    else {
      int x = getmax(L[i], R[i]);
      query[x].emplace_back(i);
    }
  }

//  for(int i = 0; i < q; i++) cout << ans[i] << endl;

  vector<int> order(n);
  for(int i = 0; i < n; i++) order[i] = i;

  sort(order.begin(), order.end(), [] (const int &x, const int &y) {
       if (h[x] == h[y]) return x > y;
       return h[x] < h[y];
       });

  for(int i = 1; i <= 4 * n; i++) prefix.lazy[i] = suffix.lazy[i] = make_pair(-1e9, 0);

  auto get_prefix = [&] (int pos) {
    pair<long long, long long> tmp = prefix.get(1, 0, n - 1, pos);
    if (tmp.first == -1e9) return tmp.second;
    return tmp.first * pos + tmp.second;
  };

  auto get_suffix = [&] (int pos) {
    pair<long long, long long> tmp = suffix.get(1, 0, n - 1, pos);
    if (tmp.first == -1e9) return tmp.second;
    return tmp.first * pos + tmp.second;
  };

  for(int i = 0; i < n; i++) pre[i] = i - 1, nxt[i] = i + 1;

  for(int cur = 0; cur < n; cur++) {
    int v = order[cur];
    int from = pre[v], to = nxt[v];
    if (from >= 0) nxt[from] = to;
    if (to < n) pre[to] = from;
    from++; to--;

//    cout << from << " " << to << " " << v << endl;

    prefix.up(1, 0, n - 1, v, v, make_pair(0, get_prefix(v - 1) + h[v]));
    suffix.up(1, 0, n - 1, v, v, make_pair(0, get_suffix(v + 1) + h[v]));


    for(int &j : query[v]) {
//      cout << j << " " << v << endl;
      assert(from <= L[j]);
      assert(R[j] <= to);
      if (j == 0) {
//        cout << get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v] << endl;
      }
      if (L[j] != v) ans[j] = min(ans[j], get_suffix(L[j]) + 1LL * (R[j] - v + 1) * h[v]);
      if (R[j] != v) ans[j] = min(ans[j], get_prefix(R[j]) + 1LL * (v - L[j] + 1) * h[v]);
    }

    long long left = get_prefix(v - 1);
    long long right = get_suffix(v + 1);

//    if (v == 2) cout << left << " " << right << endl;
//    cout << left << " " << right << endl;
//    cout << endl;

    int l, r, last;

    l = v + 1, r = to, last = v;

    while (l <= r) {
      int mid = l + r >> 1;
      if (left + h[v] * (mid - v + 1) <= h[v] * (v - from + 1)  + get_prefix(mid)) {
        last = mid;
        l = mid + 1;
      } else r = mid - 1;
    }

//    if (v == 2) cout << last << "@" << endl;

    if (v + 1 <= last) prefix.up(1, 0, n - 1, v + 1, last, make_pair(h[v], left - h[v] * (v - 1)));
    if (last + 1 <= to) prefix.up(1, 0, n - 1, last + 1, to, make_pair(-1e9, h[v] * (v - from + 1)));

    l = from, r = v - 1, last = v;

    while (l <= r) {
      int mid = l + r >> 1;
      if (right + h[v] * (v - mid + 1) <= h[v] * (to - v + 1) + get_suffix(mid)) {
        last = mid;
        r = mid - 1;
      } else l = mid + 1;
    }

    if (last <= v - 1) suffix.up(1, 0, n - 1, last, v - 1, make_pair(-h[v], right + h[v] * (v + 1)));
    if (from <= last - 1) suffix.up(1, 0, n - 1, from, last - 1, make_pair(-1e9, h[v] * (to - v + 1)));
    if (v == 2) {
//      cout << get_prefix(n - 1) << endl;
////      prefix.up(1, 0, n - 1, 0, 0, make_pair(0, 2));
//      cout << get_suffix(0) << endl;
//      cout << get_suffix(0) << endl;
//      cout << get_suffix(0) << endl;
    }
  }

  return ans;
}

#ifdef ngu
namespace {

int read_int() {
  int x;
  if (scanf("%d", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

int main() {
  freopen ("task.inp", "r", stdin);
  freopen ("task.out", "w", stdout);
  int N = read_int();
  int Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (int j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}
#endif // ngu

Compilation message

meetings.cpp: In member function 'void IT::up(int, int, int, int, int, std::pair<long long int, long long int>)':
meetings.cpp:35:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int mid = l + r >> 1;
      |             ~~^~~
meetings.cpp: In member function 'std::pair<long long int, long long int> IT::get(int, int, int, int)':
meetings.cpp:43:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |   int mid = l + r >> 1;
      |             ~~^~~
meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:69:57: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   69 |     sp[j][i] = best(sp[j - 1][i], sp[j - 1][i + (1 << j - 1)]);
      |                                                       ~~^~~
meetings.cpp:146:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |       int mid = l + r >> 1;
      |                 ~~^~~
meetings.cpp:161:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  161 |       int mid = l + r >> 1;
      |                 ~~^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29020 KB Output is correct
2 Correct 24 ms 54004 KB Output is correct
3 Correct 14 ms 54040 KB Output is correct
4 Correct 14 ms 53852 KB Output is correct
5 Correct 13 ms 54044 KB Output is correct
6 Correct 12 ms 53852 KB Output is correct
7 Correct 12 ms 53852 KB Output is correct
8 Correct 14 ms 53852 KB Output is correct
9 Correct 13 ms 53852 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29020 KB Output is correct
2 Correct 24 ms 54004 KB Output is correct
3 Correct 14 ms 54040 KB Output is correct
4 Correct 14 ms 53852 KB Output is correct
5 Correct 13 ms 54044 KB Output is correct
6 Correct 12 ms 53852 KB Output is correct
7 Correct 12 ms 53852 KB Output is correct
8 Correct 14 ms 53852 KB Output is correct
9 Correct 13 ms 53852 KB Output is correct
10 Correct 19 ms 56412 KB Output is correct
11 Correct 17 ms 56412 KB Output is correct
12 Correct 17 ms 56408 KB Output is correct
13 Correct 21 ms 56664 KB Output is correct
14 Correct 17 ms 56412 KB Output is correct
15 Correct 16 ms 56408 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29020 KB Output is correct
2 Correct 42 ms 59708 KB Output is correct
3 Correct 255 ms 85708 KB Output is correct
4 Correct 213 ms 85228 KB Output is correct
5 Correct 208 ms 84316 KB Output is correct
6 Correct 255 ms 87124 KB Output is correct
7 Correct 265 ms 85840 KB Output is correct

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29020 KB Output is correct
2 Correct 42 ms 59708 KB Output is correct
3 Correct 255 ms 85708 KB Output is correct
4 Correct 213 ms 85228 KB Output is correct
5 Correct 208 ms 84316 KB Output is correct
6 Correct 255 ms 87124 KB Output is correct
7 Correct 265 ms 85840 KB Output is correct
8 Correct 206 ms 85076 KB Output is correct
9 Correct 199 ms 85200 KB Output is correct
10 Correct 202 ms 85196 KB Output is correct
11 Correct 206 ms 84892 KB Output is correct
12 Correct 192 ms 85156 KB Output is correct
13 Correct 200 ms 85232 KB Output is correct
14 Correct 255 ms 85844 KB Output is correct
15 Correct 186 ms 84940 KB Output is correct
16 Correct 266 ms 85500 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 29020 KB Output is correct
2 Correct 24 ms 54004 KB Output is correct
3 Correct 14 ms 54040 KB Output is correct
4 Correct 14 ms 53852 KB Output is correct
5 Correct 13 ms 54044 KB Output is correct
6 Correct 12 ms 53852 KB Output is correct
7 Correct 12 ms 53852 KB Output is correct
8 Correct 14 ms 53852 KB Output is correct
9 Correct 13 ms 53852 KB Output is correct
10 Correct 19 ms 56412 KB Output is correct
11 Correct 17 ms 56412 KB Output is correct
12 Correct 17 ms 56408 KB Output is correct
13 Correct 21 ms 56664 KB Output is correct
14 Correct 17 ms 56412 KB Output is correct
15 Correct 16 ms 56408 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 42 ms 59708 KB Output is correct
18 Correct 255 ms 85708 KB Output is correct
19 Correct 213 ms 85228 KB Output is correct
20 Correct 208 ms 84316 KB Output is correct
21 Correct 255 ms 87124 KB Output is correct
22 Correct 265 ms 85840 KB Output is correct
23 Correct 206 ms 85076 KB Output is correct
24 Correct 199 ms 85200 KB Output is correct
25 Correct 202 ms 85196 KB Output is correct
26 Correct 206 ms 84892 KB Output is correct
27 Correct 192 ms 85156 KB Output is correct
28 Correct 200 ms 85232 KB Output is correct
29 Correct 255 ms 85844 KB Output is correct
30 Correct 186 ms 84940 KB Output is correct
31 Correct 266 ms 85500 KB Output is correct
32 Correct 2528 ms 232392 KB Output is correct
33 Correct 2256 ms 232272 KB Output is correct
34 Correct 2384 ms 234600 KB Output is correct
35 Correct 2589 ms 233824 KB Output is correct
36 Correct 2292 ms 232684 KB Output is correct
37 Correct 2435 ms 234636 KB Output is correct
38 Correct 2776 ms 238740 KB Output is correct
39 Correct 2333 ms 238544 KB Output is correct
40 Correct 1753 ms 234636 KB Output is correct
41 Correct 2899 ms 241320 KB Output is correct
42 Correct 2976 ms 242376 KB Output is correct
43 Correct 3079 ms 242252 KB Output is correct
44 Correct 3099 ms 238316 KB Output is correct