Submission #299126

#	Time	Username	Problem	Language	Result	Execution time	Memory
299126		DanerZein	Meetings (IOI18_meetings)	C++14	19 / 100	1038 ms	2420 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;
typedef pair<iii,ll> iiii;
int n;
int val[100010],tma[400010],tl[400010],tr[400010],l1[400010],r1[400010];
void init(int node,int a,int b){
  if(a==b){
    l1[node]=r1[node]=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);
  tma[node]=max(tma[2*node+1],tma[2*node+2]);
  if(tr[2*node+1]==1 and tl[2*node+2]==1){
    tma[node]=max(tma[node],r1[2*node+1]+l1[2*node+2]);
  }
  if(tl[2*node+1]==1 and tr[2*node+1]==1 and tma[2*node+1]==abs(a-mid)+1){
    l1[node]=l1[2*node+1]+l1[2*node+2];
  }
  else l1[node]=l1[2*node+1];
  if(tr[2*node+2]==1 and tl[2*node+2]==1 and tma[2*node+2]==abs((mid+1)-b)+1){
    r1[node]=r1[2*node+1]+r1[2*node+2];
  }
  else r1[node]=r1[2*node+2];
  tl[node]=tl[2*node+1];
  tr[node]=tr[2*node+2];
}
iiii query(int node,int a,int b,int l,int r){
  // cout<<node<<endl;
  if(a>r or b<l) return iiii(iii(ii(0,0),ii(0,0)),-MAX);
  if(l<=a and r>=b){
    return iiii(iii(ii(tl[node],l1[node]),ii(tr[node],r1[node])),tma[node]);
  }
  int mid=(a+b)/2;
  iiii 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 ma=-1;
  ll al,ar,a1,b1;
  ma=max(le.second,ri.second);
  if(le.first.second.first==1 and ri.first.first.first==1){
    ma=max(ma,le.first.second.second+ri.first.first.second);
  }
  if(le.first.first.first==1 and le.first.second.first==1 and le.second==(mid-a)+1){
    a1=le.first.first.second+ri.first.first.second;
  }
  else a1=le.first.first.second;
  if(ri.first.first.first==1 and ri.first.second.first==1 and ri.second==(b-(mid+1))+1){
    b1=le.first.second.second+ri.first.second.second;
  }
  else b1=le.first.second.second;
  al=le.first.first.first;
  ar=ri.first.second.first;
  return iiii(iii(ii(al,a1),ii(ar,b1)),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<17;i++){
      cout<<i<<": "<<tl[i]<<" "<<l1[i]<<" "<<tr[i]<<" "<<r1[i]<<" "<<tma[i]<<endl;
    }*/
    for(int i=0;i<L.size();i++){
      iiii no=query(0,0,n-1,L[i],R[i]);
      ll ret=((R[i]-L[i])+1)-no.second;
      //  cout<<no.second<<endl;
      C.push_back(no.second+(2*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:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(int i=0;i<H.size();i++){
      |               ~^~~~~~~~~
meetings.cpp:75:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |     for(int i=0;i<L.size();i++){
      |                 ~^~~~~~~~~
meetings.cpp:134:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for(int i=0;i<L.size();i++){
      |                 ~^~~~~~~~~

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