Submission #1210307

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210307		loiiii12358	Meetings (IOI18_meetings)	C++20	17 / 100	78 ms	16828 KiB

meetings

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

struct Segment{
  int l,r,m;
  bool full;
  Segment(){
    l=r=m=0;
    full=false;
  }
  Segment(int a,int b,int c,bool d){
    l=a;r=b;m=c;
    full=d;
  }
};
vector<int> h={0};
vector<Segment> seg;
void build(int id,int l,int r){
  // cout << id << ' ' << l << ' ' << r << endl;
  if(l==r){
    if(h[l]==1){
      seg[id]=Segment(1,1,1,true);
    }else{
      seg[id]=Segment(0,0,0,false);
    }
    return;
  }
  int m=l+(r-l)/2;
  build(id*2,l,m);
  build(id*2+1,m+1,r);
  seg[id]=Segment();
  if(seg[id*2].full){
    seg[id].l=seg[id*2].l+seg[id*2+1].l;
  }else{
    seg[id].l=seg[id*2].l;
  }
  if(seg[id*2+1].full){
    seg[id].r=seg[id*2+1].r+seg[id*2].r;
  }else{
    seg[id].r=seg[id*2+1].r;
  }
  seg[id].m=max(seg[id*2].r+seg[id*2+1].l,max(seg[id*2].m,seg[id*2+1].m));
  seg[id].full=seg[id*2].full&&seg[id*2+1].full;
}

Segment query(int id,int l,int r,int L,int R){
  if(r<L||l>R){
    return Segment(0,0,0,false);
  }else if(l>=L&&r<=R){
    return seg[id];
  }
  int m=l+(r-l)/2;
  Segment a=query(id*2,l,m,L,R),b=query(id*2+1,m+1,r,L,R),ans;
  if(a.full){
    ans.l=a.l+b.l;
  }else{
    ans.l=a.l;
  }
  if(b.full){
    ans.r=a.r+b.r;
  }else{
    ans.r=b.r;
  }
  ans.m=max(a.r+b.l,max(a.m,b.m));
  ans.full=a.full&&b.full;
  return ans;
}

std::vector<long long> minimum_costs(std::vector<int32_t> H, std::vector<int32_t> L,
                                     std::vector<int32_t> R) {
  int N=H.size(),Q = L.size(),cnt;
  Segment tmp;
  vector<long long> C(Q);
  for(int i=0;i<N;i++){
    h.push_back(H[i]);
  }
  seg.resize(4*N);
  build(1,1,N);
  for(int i=0;i<Q;i++){
    tmp=query(1,1,N,L[i]+1,R[i]+1);
    cnt=max(tmp.m,max(tmp.l,tmp.r));
    C[i]=(R[i]-L[i]+1)*2-cnt;
  }
  return C;
}

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