Submission #1052787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052787		Itamar	Meetings (IOI18_meetings)	C++14	17 / 100	62 ms	13748 KiB

meetings

using namespace std;
#include <vector>
#define ll long long
#define vll vector<ll>
#include <bits/stdc++.h>
vll h;
struct node{
  int l,r,mid,ones,pref,suf;
  node* sl,*sr;
  node(int li, int ri){
    l = li, r = ri, mid = (l+r)/2;
    if(l<r){
      sl = new node(l,mid);
      sr = new node(mid+1,r);
      if(sl->ones == mid-l+1)pref = mid-l+1 + sr->pref;
      else pref = sl->pref;
      if(sr->ones == r-mid)suf = r-mid+sl->suf;
      else suf = sr->suf;
      ones = max({sl->ones,sr->ones,sl->suf+sr->pref});
    }else{
      ones = h[l]%2;
      pref=ones, suf = pref;
    }
  }
  int query(int a, int b){
    if(a > r || b < l)return 0;
    if(a <= l && b>=r)return ones;
    if(a > mid)return sr->query(a,b);
    if(b <= mid)return sl->query(a,b);
    return max({sl->query(a,b),sr->query(a,b),min(sl->suf,mid-a+1)+min(sr->pref,b-mid)});
  } 
};
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  for(int hi :H)h.push_back(hi);
  int Q = L.size();
  std::vector<ll> ans(Q);
  int N= H.size();
  node* seg = new node(0,N-1);
  for (int j = 0; j < Q; ++j) {
    ans[j] = 2*(R[j]-L[j]+1) -seg->query(L[j],R[j]); 
  }
  return ans;
}

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