Submission #292307

#	Time	Username	Problem	Language	Result	Execution time	Memory
292307		kimbj0709	Meetings (IOI18_meetings)	C++14	17 / 100	362 ms	12288 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define maxn 100050
vector<int> sum(maxn*4,0);
vector<int> prefix(maxn*4,0);
vector<int> suffix(maxn*4,0);
vector<int> maximum(maxn*4,0);
vector<int> vect1;
void build(int node,int start,int end){
  if(start==end){
    if(vect1[start]==1){
      prefix[node] = suffix[node] = sum[node] = 1;
    }
    else{
        sum[node] = 1;
    }
    return;
  }
  int mid = (start+end)/2;
  build(node*2+1,start,mid);
  build(node*2+2,mid+1,end);
  if(prefix[node*2+1]==sum[node*2+1]){
    prefix[node] = prefix[node*2+1]+prefix[node*2+2];
  }
  else{
    prefix[node] = prefix[node*2+1];
  }
  if(suffix[node*2+2]==sum[node*2+2]){
    suffix[node] = suffix[node*2+2]+suffix[node*2+1];
  }
  else{
    suffix[node] = suffix[node*2+2];
  }
  sum[node] = sum[node*2+2]+sum[node*2+1];
  maximum[node] = max(prefix[node*2+2]+suffix[node*2+1],max(maximum[node*2+1],maximum[node*2+2]));
}
int an = 0;
vector<int> query(int node,int start,int end,int rangemin,int rangemax){
  //cout << start << " " << end << endl;
  if(start>rangemax||end<rangemin){
    return {0,0,0};
  }
  if(start>=rangemin&&end<=rangemax){
    an = max(an,maximum[node]);
    return {prefix[node],suffix[node],sum[node]};
  }
  int mid = (start+end)/2;
  vector<int> a = query(node*2+1,start,mid,rangemin,rangemax);
  vector<int> b = query(node*2+2,mid+1,end,rangemin,rangemax);
  if(a[0]==-1){
    return b;
  }
  if(b[0]==-1){
    return a;
  }
  an = max(an,a[1]+b[0]);
  vector<int> ret(3);
  ret[2] = a[2]+b[2];
  if(a[0]==a[2]){
    ret[0] = a[0]+b[0];
  }
  else{
    ret[0] = a[0];
  }
  if(b[1]==b[2]){
    ret[1] = b[1]+a[1];
  }
  else{
    ret[1] = b[1];
  }
  //cout << start << " " << end << " " << ret[0] << " " << ret[1] << " " << ret[2] << "\n";
  return ret;
}

std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  vector<long long int> ans(L.size());
  vect1 = H;
  build(0,0,vect1.size()-1);
  for(int i=0;i<L.size();i++){
    query(0,0,vect1.size()-1,L[i],R[i]);
    //cout << an << "\n";
    ans[i] = (R[i]-L[i]+1)*2-an;
    an = 0;
  }
  return ans;
}

Compilation message (stderr)

meetings.cpp: In function 'std::vector<long long int> minimum_costs(std::vector<int>, std::vector<int>, std::vector<int>)':
meetings.cpp:81:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int i=0;i<L.size();i++){
      |               ~^~~~~~~~~

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