제출 #1237472

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1237472		noyancanturk	모임들 (IOI18_meetings)	C++20	17 / 100	44 ms	11336 KiB

meetings

#include "meetings.h"

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

#define int long long
#define pb push_back

using pii=pair<int,int>;

vector<int>minimum_costs(vector<signed>h,vector<signed>l,vector<signed>r){
  int n=h.size();
  int q=l.size();
  for(int i=0;i<n;i++){
    assert(h[i]<=2);
    h[i]-=1;
  }
  int last[n]{};
  int suf[n]{};
  for(int i=n-1;0<=i;i--){
    last[i]=i;
    if(i+1<n&&!h[i+1])last[i]=last[i+1];
    if(!h[i]){
      suf[i]=1;
      if(i+1<n)suf[i]+=suf[i+1];
    }
  }
  int pref[n]{};
  for(int i=0;i<n;i++){
    if(!h[i]){
      pref[i]=1;
      if(i){
        pref[i]+=pref[i-1];
      }
    }
  }
  vector<int>c(q,0);
  vector<int>inds[n];
  for(int i=0;i<q;i++){
    inds[l[i]].pb(i);
  }
  deque<pii>ranges;
  for(int i=n-1;0<=i;i--){
    if(pref[i]==1){
      pii toad={i+suf[i]-1,suf[i]};
      while(ranges.size()&&ranges[0].second<suf[i])ranges.pop_front();
      ranges.push_front(toad);
    }
    for(int id:inds[i]){
      auto p=upper_bound(ranges.begin(),ranges.end(),pii{r[id],INT_MAX});
      if(p!=ranges.begin()){
        p--;
        c[id]=p->second;
      }
      if(!h[r[id]]){
        c[id]=max(c[id],pref[r[id]]);
      }
      if(!h[i]){
        c[id]=max(c[id],suf[i]);
      }
      c[id]=min<int>(c[id],r[id]-i+1);
      c[id]=2*(r[id]-i+1)-c[id];
    }
  }
  return c;
}

// 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]];
//   }
//   return C;
// }

#undef int

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