Submission #615953

#	Time	Username	Problem	Language	Result	Execution time	Memory
615953		chirathnirodha	Meetings (IOI18_meetings)	C++17	36 / 100	511 ms	11404 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair 
#define F first 
#define S second 
#define P push 
typedef long long ll;

int n,q;

vector<ll> hei;
vector<ll> SUB_1_2(vector<int> L,vector<int> R) {
  vector<ll> C;
  for(int h=0;h<q;h++){
    ll ans=INT64_MAX;
    ll vall[n],valr[n];

    vector<int> v;
    ll cur=hei[L[h]];vall[L[h]]=cur;
    v.PB(L[h]);
    for(int i=L[h]+1;i<=R[h];i++){
      while(!v.empty()){
        int last=v.back();
        if(hei[last]>=hei[i])break;
        v.pop_back();
        if(v.empty())cur+=(hei[i]-hei[last])*(last-L[h]+1);
        else cur+=(hei[i]-hei[last])*(last-v.back());
      }
      v.PB(i);cur+=hei[i];
      vall[i]=cur;
    }

    v.clear();
    cur=hei[R[h]];valr[R[h]]=cur;
    v.PB(R[h]);
    for(int i=R[h]-1;i>=L[h];i--){
      while(!v.empty()){
        int last=v.back();
        if(hei[last]>=hei[i])break;
        v.pop_back();
        if(v.empty())cur+=(hei[i]-hei[last])*(R[h]-last+1);
        else cur+=(hei[i]-hei[last])*(v.back()-last);
      }
      v.PB(i);cur+=hei[i];
      valr[i]=cur;
    }
    for(int i=L[h];i<=R[h];i++){
      ans=min(ans,vall[i]+valr[i]-hei[i]);
    }
    C.PB(ans);
  }
  return C;
}

int pref[400010],suff[400010],seg[400010];
void buildseg(int a,int b,int c){
  if(a==b){
    if(hei[a]==1){
      seg[c]=pref[c]=suff[c]=1;
    }
    else{
      seg[c]=pref[c]=suff[c]=0;
    }
    return;
  }
  int m=(a+b)/2;
  buildseg(a,m,2*c);
  buildseg(m+1,b,2*c+1);
  seg[c]=max({seg[2*c],seg[2*c+1],suff[2*c]+pref[2*c+1]});
  pref[c]=pref[2*c];
  if(pref[2*c]==m-a+1)pref[c]+=pref[2*c+1];
  suff[c]=suff[2*c+1];
  if(suff[2*c+1]==b-m)suff[c]+=suff[2*c];
  return;
}
int findseg(int a,int b,int c,int x,int y){
  if(a==x && b==y)return seg[c];
  int m=(a+b)/2;
  if(y<=m)return findseg(a,m,2*c,x,y);
  else if(x>m)return findseg(m+1,b,2*c+1,x,y);
  int merge=min(pref[2*c+1],y-m)+min(suff[2*c],m-x+1);
  return max({findseg(a,m,2*c,x,m),findseg(m+1,b,2*c+1,m+1,y),merge});
}
vector<ll> SUB_3(vector<int> L,vector<int> R) {
  memset(seg,0,sizeof(seg));
  buildseg(0,n-1,1);
  vector<ll> C;
  for(int i=0;i<q;i++){
    int all=R[i]-L[i]+1;
    int ones=findseg(0,n-1,1,L[i],R[i]);
    ll val=ones+2*(all-ones);
    C.PB(val);
  }
  return C;
}
vector<ll> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
  n=H.size();q=L.size();
  for(int i=0;i<n;i++)hei.PB((ll)H[i]);
  if(n<=5000 && q<=5000)return SUB_1_2(L,R);
  else return SUB_3(L,R);

}

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