제출 #1221005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1221005		abdelhakim	Meetings (IOI18_meetings)	C++20	17 / 100	204 ms	31348 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;
vector<int> h;
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][2]=r-lr[r][0]+1;
  }
  tree[node][1]=min(tree[node][1],r-l+1);
  tree[node][2]=min(tree[node][2],r-l+1);
}
void update(ll node, ll l, ll r, ll pos)
{
  if(l==r)
  {
    if(h[l]==1)tree[node]={1,1,1};
    if(l==1) dbg(tree[node][0]);
    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);
}
vector<ll> query(ll node, ll l, ll r, ll x, ll y)
{
  if(max(l,x) > min(r,y)) return {0,0,0};
  if(x<=l && r<=y)
  {
    return tree[node];
  }
  ll mid=(l+r)>>1;
  vector<ll> qr1=query(node*2+1,l,mid,x,y);
  vector<ll> qr2=query(node*2+2,mid+1,r,x,y);
  ll val1=0;
  ll val2=0;
  vector<ll> an(3);
  an[0]=max({qr1[0],qr2[0],qr1[2]+qr2[1]});
  if(h[l]==1&& l>=x)
  {
    an[1]=min(y,lr[l][1])-l+1;
  }
  if(h[r]==1 && r<=y)
  {
    an[2]=r-max(x,lr[r][0])+1;
  }
  return an;
  // 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));
  h=H;
  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;
  }
  update(0,0,n-1,0);
  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])[0];
  }
  return ans;
}

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