제출 #446587

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446587		dxz05	모임들 (IOI18_meetings)	C++14	36 / 100	702 ms	432008 KiB

meetings

#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 / 4
• Subtask 2: 15 / 15
• Subtask 3: 17 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40