제출 #1111935

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1111935		SalihSahin	모임들 (IOI18_meetings)	C++14	0 / 100	19 ms	1892 KiB

meetings

#include <bits/stdc++.h>
#define pb push_back
//#define int long long
using namespace std;
#include "meetings.h"

const long long inf = 1e17;
/*
namespace {

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

}  // namespace
*/

vector<vector<int> > mx;
int M, K;
int query(int l, int r){
  int ind = 0;
  while((1 << (ind + 1)) <= (r - l + 1)){
    ind++;
  } 
  return max(mx[l][ind], mx[r - (1 << ind) + 1][ind]);
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  int n = H.size();
  vector<array<int, 3> > segments;
  int cnt = 0;
  for(int i = 0; i < n; i++){
    if(H[i] == 2){
      if(cnt > 0){
        segments.pb({i - cnt, i - 1, cnt});
      }
      cnt = 0;
    }
    else cnt++;
  }
  if(cnt > 0){
    segments.pb({n-cnt, n-1, cnt});
  }

  M = segments.size();
  K = 18;
  if(M > 0){
    mx.resize(M);
    for(int i = 0; i < M; i++){
      mx[i].resize(K);
      mx[i][0] = segments[i][2];
    }
    for(int i = 1; i < K; i++){
      for(int j = 0; j < M; j++){
        mx[j][i] = max(mx[j][i-1], mx[min(M-1, j + (1 << (i - 1)))][i-1]);
      }
    }
  }

  int Q = L.size();
  vector<long long> C(Q);
  for (int j = 0; j < Q; ++j) {
    long long ans = 2 * (R[j] - L[j] + 1);
    if(M > 0){
      int l = 0, r = M-1;
      while(l < r){
        int m = (l + r)/2;

        if(segments[m][1] >= L[j]) r = m;
        else l = m + 1;
      }

      int sol = l;
      l = 0, r = M-1;
      while(l < r){
        int m = (l + r + 1)/2;

        if(segments[m][0] <= R[j]) l = m;
        else r = m - 1;
      }
      int sag = l;

      int cik = 0;
      if(segments[sol][0] < L[j]){
        cik = max(cik, segments[sol][1] - L[j] + 1);
        sol++;
      }
      if(segments[sag][1] > R[j]){
        cik = max(cik, R[j] - segments[sag][0] + 1);
        sag--;
      }
      if(sol <= sag){
        cik = max(cik, query(sol, sag));
      }
      ans -= cik;
    }
    C[j] = ans;
  }

  return C;
}

/*
int main() {
  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;
}*/

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40