제출 #1032602

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1032602		HappyCapybara	모임들 (IOI18_meetings)	C++17	17 / 100	352 ms	27720 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int N;
vector<vector<int>> st;

vector<int> merge(vector<int> l, vector<int> r){
  vector<int> res(4, 0);
  res[0] = l[0]+r[0];
  res[1] = l[1];
  if (l[1] == l[0]) res[1] += r[1];
  res[2] = max(max(l[2], r[2]), l[3]+r[1]);
  res[3] = r[3];
  if (r[3] == r[0]) res[3] += l[3];
  return res;
}

void update(int pos, int val, int node=1, int tl=0, int tr=N-1){
  if (tl == tr){
    if (val == 1) st[node] = {1, 1, 1, 1};
    else st[node] = {1, 0, 0, 0};
    return;
  }
  int tm = (tl+tr)/2;
  if (pos <= tm) update(pos, val, node*2, tl, tm);
  else update(pos, val, node*2+1, tm+1, tr);
  st[node] = merge(st[node*2], st[node*2+1]);
}

vector<int> query(int l, int r, int node=1, int tl=0, int tr=N-1){
  if (l <= tl && tr <= r) return st[node];
  int tm = (tl+tr)/2;
  vector<int> res(4, 0);
  if (l <= tm) res = merge(res, query(l, r, node*2, tl, tm));
  if (tm+1 <= r) res = merge(res, query(l, r, node*2+1, tm+1, tr));
  return res;
}

vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
  int Q = L.size();
  N = H.size();
  st.resize(4*N, {0, 0, 0, 0});
  for (int i=0; i<N; i++){
    if (H[i] == 1) update(i, 1);
    else update(i, 2);
  }
  vector<ll> C(Q);
  for (int i=0; i<Q; i++) C[i] = 2*(R[i]-L[i]+1)-query(L[i], R[i])[2];
  return C;
}

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