Submission #1220987

#	Time	Username	Problem	Language	Result	Execution time	Memory
1220987		abdelhakim	Meetings (IOI18_meetings)	C++20	0 / 100	49 ms	24004 KiB

meetings

#include "meetings.h"
#include <bits/stdc++.h>
#define ll long long
#define inf (ll)1e17
#define dbg(x) cerr<< #x << ' ' << x << endl;
using namespace std;
ll maxn=1e5;
vector<vector<ll>> tree(4*maxn+3,vector<ll>(3));
vector<vector<ll>> lr;
void merge(ll node, ll l, ll r)
{
  tree[node][0]=max({tree[node*2+1][0],tree[node*2+2][0],tree[node*2+1][2]+tree[node*2+2][1]});
  if(lr[l][1]!=-1)
  {
    tree[node][1]=(lr[l][1]-l)+1;
  }
  if(lr[r][0]!=-1)
  {
    tree[node][0]=r-lr[r][0]+1;
  }
  tree[node][1]=min(tree[node][1],r-l+1);
  tree[node][0]=min(tree[node][0],r-l+1);
}
void update(ll node, ll l, ll r, ll pos)
{

  if(pos < l || pos > r)return;
  if(l==r)
  {
    tree[node]={1,1,1};
    return;
  }
  ll mid=(l+r)>>1;
  update(node*2+1,l,mid,pos);
  update(node*2+2,mid+1,r,pos);
  merge(node,l,r);
}
ll query(ll node, ll l, ll r, ll x, ll y)
{
  if(max(l,x) > min(r,y)) return 0;
  if(x<=l && r<=y)
  {
    return tree[node][0];
  }
  ll mid=(l+r)>>1;
  ll qr1=query(node*2+1,l,mid,x,y);
  ll qr2=query(node*2+2,mid+1,r,x,y);
  ll val1=0;
  ll val2=0;
  if(lr[mid][0]!=-1)
  {
    val1=min(mid-l+1,mid-lr[mid][0]+1);
  }
  if(lr[mid+1][1]!=-1)
  {
    val2=min(r-mid,lr[mid+1][1]-mid);
  }
  return max({val1+val2,qr1,qr2});
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,std::vector<int> R) 
{
  ll n=H.size();
  ll q=L.size();
  ll l=-1;
  ll r=-1;
  lr.assign(n,vector<ll>(2,-1));
  for (int i=0;i<n;i++)
  {
    if(H[i]==1 && (i==0 || H[i-1]==2))
    {
      l=i;
    }
    if(H[i]==1 && (i==n-1 || H[i+1]==2))
    {
      r=i;
    }
    if(l==-1 || r==-1)continue;
    for (int j=l;j<=r;j++)
    {
      lr[j][0]=l;
      lr[j][1]=r;
    }
    l=-1;
    r=-1;
  }
  for (int i=0;i<n;i++)
  {
    if(H[i]==1)
    {
      update(0,0,n-1,i);
    }
  }
  vector<ll> ans(q);
  for (int i=0;i<q;i++)
  {
    ans[i]=2*(R[i]-L[i]+1)-query(0,0,n-1,L[i],R[i]);
  }
  return ans;
}

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