oj.uz

Submission #971808

# Submission time Handle Problem Language Result Execution time Memory
971808 2024-04-29T10:41:15 Z nguyentunglam Measures (CEOI22_measures) C++17
100 / 100
 176 ms 32516 KB 
#include<bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define endl "\n"
using namespace std;

const int N = 4e5 + 30;

int n, m, d;

int a[N];

long long T[4][N << 2];

void up(int s, int l, int r, int pos, int val) {
  if (l == r) {
    T[0][s] = 1;
    T[1][s] = val;
    T[2][s] = d -val;
    return;
  }
  int mid = l + r >> 1;
  if (pos <= mid) up(s << 1, l, mid, pos, val);
  else up(s << 1 | 1, mid + 1, r, pos, val);
  T[0][s] = T[0][s << 1] + T[0][s << 1 | 1];
  T[1][s] = max(T[1][s << 1 | 1], T[1][s << 1] + T[0][s << 1 | 1] * d);
  T[2][s] = max(T[2][s << 1], T[2][s << 1 | 1] + T[0][s << 1] * d);
  T[3][s] = max({T[3][s << 1], T[3][s << 1 | 1], T[1][s << 1] + T[2][s << 1 | 1]});
}

int32_t main() {
  #define task ""

  cin.tie(0) -> sync_with_stdio(0);

  if (fopen("task.inp", "r")) {
    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);
  }

  if (fopen(task".inp", "r")) {
    freopen (task".inp", "r", stdin);
    freopen (task".out", "w", stdout);
  }

  cin >> n >> m >> d;

  for(int i = 1; i <= n; i++) cin >> a[i];

  for(int i = n + 1; i <= n + m; i++) cin >> a[i];

  vector<pair<int, int> > rrh;

  for(int i = 1; i <= n + m; i++) rrh.emplace_back(a[i], i);

  sort(all(rrh));
  rrh.resize(unique(all(rrh)) - rrh.begin());

  for(int i = 1; i <= 4 * (n + m); i++) T[1][i] = T[2][i] = -1e18;

  auto update = [&] (int i) {
    int pos = upper_bound(all(rrh), make_pair(a[i], i)) - rrh.begin();
//    cout << pos << " " << i << endl;
    up(1, 1, n + m, pos, a[i]);
  };

  for(int i = 1; i <= n; i++) update(i);

  for(int i = n + 1; i <= n + m; i++) {
    update(i);
    cout << T[3][1] / 2;
    if (T[3][1] % 2) cout << ".5";
    cout << " ";
  }
}

Compilation message

Main.cpp: In function 'void up(int, int, int, int, int)':
Main.cpp:21:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |   int mid = l + r >> 1;
      |             ~~^~~
Main.cpp: In function 'int32_t main()':
Main.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen("task.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:37:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     freopen("task.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:41:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |     freopen (task".inp", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:42:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |     freopen (task".out", "w", stdout);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 1 ms 6744 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 2 ms 6492 KB Output is correct
6 Correct 2 ms 6492 KB Output is correct
7 Correct 2 ms 6492 KB Output is correct
8 Correct 2 ms 6492 KB Output is correct
9 Correct 147 ms 30724 KB Output is correct
10 Correct 121 ms 29128 KB Output is correct
11 Correct 61 ms 29380 KB Output is correct
12 Correct 82 ms 29352 KB Output is correct
13 Correct 57 ms 28724 KB Output is correct
14 Correct 68 ms 29100 KB Output is correct
15 Correct 127 ms 28520 KB Output is correct
16 Correct 59 ms 29376 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28784 KB Output is correct
2 Correct 85 ms 32460 KB Output is correct
3 Correct 82 ms 32196 KB Output is correct
4 Correct 69 ms 29964 KB Output is correct
5 Correct 84 ms 31256 KB Output is correct
6 Correct 70 ms 30408 KB Output is correct
7 Correct 78 ms 31432 KB Output is correct
8 Correct 73 ms 30208 KB Output is correct
9 Correct 73 ms 30064 KB Output is correct
10 Correct 76 ms 32456 KB Output is correct
11 Correct 72 ms 30916 KB Output is correct
12 Correct 74 ms 31844 KB Output is correct
13 Correct 72 ms 30148 KB Output is correct
14 Correct 77 ms 32108 KB Output is correct
15 Correct 80 ms 31732 KB Output is correct
16 Correct 75 ms 29640 KB Output is correct
17 Correct 72 ms 31296 KB Output is correct

Subtask #4
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28784 KB Output is correct
2 Correct 85 ms 32460 KB Output is correct
3 Correct 82 ms 32196 KB Output is correct
4 Correct 69 ms 29964 KB Output is correct
5 Correct 84 ms 31256 KB Output is correct
6 Correct 70 ms 30408 KB Output is correct
7 Correct 78 ms 31432 KB Output is correct
8 Correct 73 ms 30208 KB Output is correct
9 Correct 73 ms 30064 KB Output is correct
10 Correct 76 ms 32456 KB Output is correct
11 Correct 72 ms 30916 KB Output is correct
12 Correct 74 ms 31844 KB Output is correct
13 Correct 72 ms 30148 KB Output is correct
14 Correct 77 ms 32108 KB Output is correct
15 Correct 80 ms 31732 KB Output is correct
16 Correct 75 ms 29640 KB Output is correct
17 Correct 72 ms 31296 KB Output is correct
18 Correct 157 ms 30460 KB Output is correct
19 Correct 176 ms 31776 KB Output is correct
20 Correct 77 ms 32068 KB Output is correct
21 Correct 99 ms 29632 KB Output is correct
22 Correct 111 ms 30404 KB Output is correct
23 Correct 81 ms 30272 KB Output is correct
24 Correct 155 ms 32516 KB Output is correct
25 Correct 72 ms 30024 KB Output is correct
26 Correct 142 ms 30116 KB Output is correct
27 Correct 143 ms 32440 KB Output is correct
28 Correct 100 ms 30404 KB Output is correct
29 Correct 119 ms 31832 KB Output is correct
30 Correct 98 ms 29472 KB Output is correct
31 Correct 102 ms 32000 KB Output is correct
32 Correct 83 ms 31688 KB Output is correct
33 Correct 137 ms 29640 KB Output is correct
34 Correct 100 ms 31432 KB Output is correct