oj.uz

Submission #446587

# Submission time Handle Problem Language Result Execution time Memory
446587 2021-07-22T14:00:33 Z dxz05 Meetings (IOI18_meetings) C++14
36 / 100
 702 ms 432008 KB 
#include "meetings.h"
#include <bits/stdc++.h>

using namespace std;
const int maxn = 5555;
const int maxnn = 1111111;
const int INF = 1000000007;

long long pref[maxn][maxn];
long long MAX[maxn][maxn];

struct node{
  long long seg;
  long long prf;
  long long sff;
  long long sum;
};

node combine(node a, node b){
  node c;
  c.seg = max(a.sff + b.prf, max(a.seg, b.seg));
  c.prf = max(a.prf, a.sum + b.prf);
  c.sff = max(b.sff, b.sum + a.sff);
  c.sum = a.sum + b.sum;
  return c;
}

int a[maxnn];
node t[maxnn];

void build(int v, int tl, int tr){
  if (tl == tr) {
    node ttt;
    ttt.seg = ttt.prf = ttt.sff = max(0, a[tl]);
    ttt.sum = a[tl];
    t[v] = ttt;
    return;
  }
  int tm = (tl + tr) >> 1;
  build(v+v, tl, tm);
  build(v+v+1, tm+1, tr);
  t[v] = combine(t[v+v], t[v+v+1]);
}

node get(int v, int tl, int tr, int l, int r){
  if (tl >= l && tr <= r) return t[v];
  if (tl > r || tr < l){
    node c;
    c.prf = c.sff = c.seg = -INF;
    c.sum = 0;
    return c;
  }
  int tm = (tl + tr) >> 1;
  return combine(get(v+v, tl, tm, l, r), get(v+v+1, tm+1, tr, l, r));
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L, std::vector<int> R) {
  int Q = L.size();
  std::vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    C[j] = H[L[j]];
  }

  int N = H.size();

  if (*max_element(H.begin(), H.end()) > 2 && N <= 5000){
    for (int l = 0; l < N; l++){
      long long mx = H[l];
      for (int r = l; r < N; r++){
        mx = max(mx, 1ll * H[r]);
        MAX[l][r] = mx;
      }
      mx = H[l];
      for (int i = l - 1; i >= 0; i--){
        mx = max(mx, 1ll * H[i]);
        MAX[l][i] = mx;
      }
    }

    for (int i = 0; i < N; i++){
      pref[i][0] = MAX[i][0];
      for (int j = 1; j < N; j++){
        pref[i][j] = pref[i][j - 1] + MAX[i][j];
      }
    }

    for (int i = 0; i < Q; i++){
      int l = L[i], r = R[i];
      long long ans = 1e18;
      for (int x = l; x <= r; x++){
        long long k = pref[x][r];
        if (l > 0) k -= pref[x][l - 1];
        ans = min(ans, k);
      }
      C[i] = ans;
    }
  } else {
    for (int i = 0; i < N; i++){
      a[i + 1] = 1;
      if (H[i] == 2) a[i + 1] = -INF;
    }
    build(1, 1, N);
    for (int i = 0; i < Q; i++){
      int l = L[i], r = R[i];
      ++l, ++r;
      long long x = get(1, 1, N, l, r).seg;
      long long y = (r - l + 1) - x;
      C[i] = x + 2 * y;
      //cout << x << ' ' << y << endl;
    }
  }

  return C;
}
/*
7 5
1 2 1 1 2 2 1
1 1
1 4
3 6
6 6
0 6
*/

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 104 ms 165404 KB Output is correct
3 Correct 108 ms 165324 KB Output is correct
4 Correct 103 ms 165332 KB Output is correct
5 Correct 104 ms 165316 KB Output is correct
6 Correct 102 ms 165400 KB Output is correct
7 Correct 104 ms 165316 KB Output is correct
8 Correct 105 ms 165316 KB Output is correct
9 Correct 106 ms 165304 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 104 ms 165404 KB Output is correct
3 Correct 108 ms 165324 KB Output is correct
4 Correct 103 ms 165332 KB Output is correct
5 Correct 104 ms 165316 KB Output is correct
6 Correct 102 ms 165400 KB Output is correct
7 Correct 104 ms 165316 KB Output is correct
8 Correct 105 ms 165316 KB Output is correct
9 Correct 106 ms 165304 KB Output is correct
10 Correct 421 ms 431956 KB Output is correct
11 Correct 700 ms 431948 KB Output is correct
12 Correct 416 ms 431948 KB Output is correct
13 Correct 702 ms 431956 KB Output is correct
14 Correct 429 ms 431952 KB Output is correct
15 Correct 413 ms 432008 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 49 ms 2768 KB Output is correct
3 Correct 147 ms 14016 KB Output is correct
4 Correct 139 ms 14020 KB Output is correct
5 Correct 105 ms 14128 KB Output is correct
6 Correct 132 ms 14000 KB Output is correct
7 Correct 151 ms 14040 KB Output is correct

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 49 ms 2768 KB Output is correct
3 Correct 147 ms 14016 KB Output is correct
4 Correct 139 ms 14020 KB Output is correct
5 Correct 105 ms 14128 KB Output is correct
6 Correct 132 ms 14000 KB Output is correct
7 Correct 151 ms 14040 KB Output is correct
8 Incorrect 147 ms 14036 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 104 ms 165404 KB Output is correct
3 Correct 108 ms 165324 KB Output is correct
4 Correct 103 ms 165332 KB Output is correct
5 Correct 104 ms 165316 KB Output is correct
6 Correct 102 ms 165400 KB Output is correct
7 Correct 104 ms 165316 KB Output is correct
8 Correct 105 ms 165316 KB Output is correct
9 Correct 106 ms 165304 KB Output is correct
10 Correct 421 ms 431956 KB Output is correct
11 Correct 700 ms 431948 KB Output is correct
12 Correct 416 ms 431948 KB Output is correct
13 Correct 702 ms 431956 KB Output is correct
14 Correct 429 ms 431952 KB Output is correct
15 Correct 413 ms 432008 KB Output is correct
16 Correct 0 ms 204 KB Output is correct
17 Correct 49 ms 2768 KB Output is correct
18 Correct 147 ms 14016 KB Output is correct
19 Correct 139 ms 14020 KB Output is correct
20 Correct 105 ms 14128 KB Output is correct
21 Correct 132 ms 14000 KB Output is correct
22 Correct 151 ms 14040 KB Output is correct
23 Incorrect 147 ms 14036 KB Output isn't correct
24 Halted 0 ms 0 KB -