Submission #299338

#	Time	Username	Problem	Language	Result	Execution time	Memory
299338		DanerZein	Meetings (IOI18_meetings)	C++14	36 / 100	5506 ms	14864 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define MAX 1000000000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ii> iii;
int n;
ll val[100010],tma[400010],tl[400010],tr[400010],len[400010];
void init(int node,int a,int b){
  if(a==b){
    len[node]=1;
    tl[node]=tr[node]=tma[node]=(val[a]==1);
    return;
  }
  ll mid=(a+b)/2;
  init(2*node+1,a,mid);
  init(2*node+2,mid+1,b);
  len[node]=(b-a)+1;
  if(tma[2*node+1]==len[2*node+1]){
    tl[node]=tl[2*node+1]+tl[2*node+2];
  }
  else tl[node]=tl[2*node+1];
  if(tma[2*node+2]==len[2*node+2]){
    tr[node]=tr[2*node+2]+tr[2*node+1];
  }
  else tr[node]=tr[2*node+2];
  tma[node]=max(max(tma[2*node+1],tma[2*node+2]),tr[2*node+1]+tl[2*node+2]);
}
iii query(int node,int a,int b,int l,int r){
  if(a>r or b<l) return iii(ii(0,0),ii(0,-MAX));
  if(l<=a and r>=b){
    return iii(ii(tl[node],tr[node]),ii(len[node],tma[node]));
  }
  int mid=(a+b)/2;
  iii le=query(2*node+1,a,mid,l,r),ri=query(2*node+2,mid+1,b,l,r);
  /*cout<<node<<endl;
  cout<<le.first.first.first<<" "<<le.first.first.second<<" "<<le.first.second.first<<" "<<le.first.second.second<<" "<<le.second<<endl;
  cout<<ri.first.first.first<<" "<<ri.first.first.second<<" "<<ri.first.second.first<<" "<<ri.first.second.second<<" "<<ri.second<<endl;*/
  ll tm=le.second.first+ri.second.first,l1,r1,ma;
  if(le.second.second==le.second.first){
    l1=le.second.second+ri.first.first;
  }
  else l1=le.first.first;
  if(ri.second.second==ri.second.first){
    r1=ri.second.second+le.first.second;
  }
  else r1=ri.first.second;
  ma=max(max(le.second.second,ri.second.second),le.first.second+ri.first.first);
  return iii(ii(l1,r1),ii(tm,ma));
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
                                     std::vector<int> R) {
  bool sw=0;
  for(int i=0;i<H.size();i++){
    if(H[i]>2){
      sw=1;
      break;
    }
    else val[i]=H[i];
  }
  vector<long long> C;
  if(sw==1){
    for(int i=0;i<L.size();i++){
      stack<ii> sl;
      vector<ll> le,ri;
      ll c=0;
      le.push_back(0);
      sl.push(ii(H[L[i]],1));
      for(int j=L[i]+1;j<=R[i];j++){
	ll co=0,t=le.size()-1;
	c=le[t]+H[j-1];
	while(true){
	  if(sl.empty() or sl.top().first>H[j]){
	    sl.push(ii(H[j],co+1));
	    c+=(H[j]*co);
	    break;
	  }
	  co+=sl.top().second;
	  c-=(sl.top().first*sl.top().second);
	  sl.pop();
	}
	le.push_back(c);
      }
      while(!sl.empty()) sl.pop();
      c=0;
      ll t=(R[i]-L[i]);
      ri.resize(t+1);
      ri[t]=0;
      sl.push(ii(H[R[i]],1));
      for(int j=R[i]-1;j>=L[i];j--){
	ll co=0;
	t--;
	c=ri[t+1]+H[j+1];
	while(true){
	  if(sl.empty() or sl.top().first>H[j]){
	    sl.push(ii(H[j],co+1));
	    c+=(H[j]*co);
	    break;
	  }
	  co+=sl.top().second;
	  c-=(sl.top().first*sl.top().second);
	  sl.pop();
	}
	ri[t]=c;
      }
      ll res=MAX;
      t=0;
      for(int j=L[i];j<=R[i];j++){
	ll aux=ll(le[t]+ri[t]+H[j]);
	res=min(res,aux);
	t++;
      }
      C.push_back(res);
    }
  }
  else{
    n=H.size();
    init(0,0,n-1);
    /* for(int i=0;i<25;i++){
      cout<<tl[i]<<" "<<tr[i]<<" "<<len[i]<<" "<<tma[i]<<endl;
    }*/
    for(int i=0;i<L.size();i++){
      iii no=query(0,0,n-1,L[i],R[i]);
      ll ret=((R[i]-L[i])+1)-no.second.second;
      // cout<<no.second.second<<endl;
      ret=no.second.second+(2*ret);
      C.push_back(ret);
    }
  }
  return C;
}

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:55:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   for(int i=0;i<H.size();i++){
      |               ~^~~~~~~~~
meetings.cpp:64:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for(int i=0;i<L.size();i++){
      |                 ~^~~~~~~~~
meetings.cpp:123:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |     for(int i=0;i<L.size();i++){
      |                 ~^~~~~~~~~

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