Submission #614114

#	Time	Username	Problem	Language	Result	Execution time	Memory
614114		chirathnirodha	Meetings (IOI18_meetings)	C++17	19 / 100	584 ms	4364 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 seg[400010];
void update(int a,int b,int c,int x,int y){
  if(seg[c]==b-a+1)return;
  if(a==b){
    seg[c]=max(seg[c],y-x+1);
    return;
  }
  int m=(a+b)/2;
  if(y<=m)update(a,m,2*c,x,y);
  else if(x>m)update(m+1,b,2*c+1,x,y);
  else {
    update(a,m,2*c,x,m);
    update(m+1,b,2*c+1,m+1,y);
  }
  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);
  else return max(findseg(a,m,2*c,x,m),findseg(m+1,b,2*c+1,m+1,y));
}
vector<ll> SUB_3(vector<int> L,vector<int> R) {
  memset(seg,0,sizeof(seg));
  int cur=-1;
  for(int i=0;i<n;i++){
    if(hei[i]==2){
      if(cur+1<=i-1)update(0,n-1,1,cur+1,i-1);
      cur=i;
    }
  }
  if(cur+1<=n-1)update(0,n-1,1,cur+1,n-1);
  vector<ll> C;
  for(int i=0;i<q;i++){
    int ones=findseg(0,n-1,1,L[i],R[i]);
    ll val=ones+2*(R[i]-L[i]+1-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: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40