Submission #790746

#	Time	Username	Problem	Language	Result	Execution time	Memory
790746		Amylopectin	Meetings (IOI18_meetings)	C++14	0 / 100	0 ms	212 KiB

meetings

#include "meetings.h"
#include <vector>
#include <algorithm>
using namespace std;
const long long mxn = 1e6 + 10,mxi = 1e9 + 10;
long long hei[mxn] = {}, pos[mxn] = {},val[mxn] = {},h[mxn] = {},se[mxn] = {}
,ran[mxn] = {},stt[mxn] = {},enn[mxn] = {};
vector <long long> ans;
long long fimi(long long l,long long r)
{
  if(l < r)
  {
    return l;
  }
  return r;
}
long long fima(long long l,long long r)
{
  if(l > r)
  {
    return l;
  }
  return r;
}
long long bui(long long cl,long long cr,long long no)
{
    if(cl == cr)
    {
        se[no] = ran[cl];
        return 0;
    }
    long long mid = (cl+cr) / 2;
    bui(cl,mid,no*2);
    bui(mid+1,cr,no*2+1);
    se[no] = fima(se[no*2],se[no*2+1]);
    return 0;
}
long long fii(long long cl,long long cr,long long no,long long tl,long long tr)
{
    if(cl > tr || cr < tl)
    {
        return 0;
    }
    if(cl >= tl && cr <= tr)
    {
        return se[no];
    }
    long long mid = (cl+cr) / 2;
    return fima(fii(cl,mid,no*2,tl,tr),fii(mid+1,cr,no*2+1,tl,tr));
}
std::vector<long long> minimum_costs(std::vector<int> hh, std::vector<int> ll,
                                     std::vector<int> rr) {
  long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
  n = hh.size();
  q = ll.size();
  for(i=0; i<n; i++)
  {
    h[i] = hh[i];
  }
  ru = 0;
  of = 2;
  for(i=0; i<n; i++)
  {
    if(of == 2 && h[i] == 1)
    {
        of = 1;
        stt[ru] = i;
    }
    else if(of == 1 && h[i] == 2)
    {
        of = 2;
        enn[ru] = i-1;
        ran[ru] = enn[ru] - stt[ru] + 1;
        ru ++;
    }
  }
  if(of == 1)
  {
     of = 2;
        enn[ru] = n-1;
        ran[ru] = enn[ru] - stt[ru] + 1;
        ru ++;
  }
  if(ru == 0)
  {
    for(i=0; i<q; i++)
    {
        ans.push_back((rr[i] - ll[i]) * 2);
    }
    return ans;
  }
  bui(0,ru-1,1);
  for(i=0; i<q; i++)
  {
    cmi = 0;
    cn = ll[i];
    cl = 0;
    cr = ru-1;
    while(cl < cr)
    {
        mid = (cl+cr) / 2 + (cl+cr) % 2;
        if(cn >= stt[mid])
        {
            cl = mid;
        }
        else 
        {
            cr = mid-1;
        }
    }
    if(cl == 0 && cn < stt[0])
    {
        fl = 0;
        rel = cl-1;
    }
    else 
    {
        rel = cl;
        if(cn <= enn[cl])
        {
            cmi = fima(cmi,enn[cl] - cn + 1);
        }
        fl = cl + 1;
    }
    cn = rr[i];
    cl = 0;
    cr = ru-1;
    while(cl < cr)
    {
        mid = (cl+cr) / 2 + (cl+cr) % 2;
        if(cn >= stt[mid])
        {
            cl = mid;
        }
        else 
        {
            cr = mid-1;
        }
    }
    if(cl == 0 && cn < stt[0])
    {
        fr = -1;
        rer = cl-1;
    }
    else 
    {
        rer = cl;
        if(cn <= enn[cl])
        {
            cmi = fima(cmi,cn - stt[cl] + 1);
            fr = cl-1;
        }
        else 
        {
            fr = cl;
        }
    }
    if(fl <= fr)
    {
        cmi = fima(cmi,fii(0,ru-1,1,fl,fr));
    }
    else if(rel == rer)
    {
        cmi = 0;
        if(rel >= 0)
        {
            if(enn[rel] < ll[i])
            {
                cmi = 0;
            }
            else if(enn[rel] < rr[i])
            {
                cmi = enn[rel] - ll[i];
            }
            else 
            {
                cmi = rr[i] - ll[i];
            }
        }
    }
    cl = ll[i];
    cr = rr[i];
    cva = 2 * (cr-cl+1) - cmi;
    ans.push_back(cva);
  }
  return ans;
  // int Q = L.size();
  // std::vector<long long> C(Q);
  // for (int j = 0; j < Q; ++j) {
  //   C[j] = H[L[j]];
  // }
  // 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:53:15: warning: unused variable 'j' [-Wunused-variable]
   53 |   long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
      |               ^
meetings.cpp:53:19: warning: unused variable 'm' [-Wunused-variable]
   53 |   long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
      |                   ^
meetings.cpp:53:26: warning: unused variable 'cm' [-Wunused-variable]
   53 |   long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
      |                          ^~
meetings.cpp:53:29: warning: unused variable 'fn' [-Wunused-variable]
   53 |   long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
      |                             ^~
meetings.cpp:53:32: warning: unused variable 'fm' [-Wunused-variable]
   53 |   long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
      |                                ^~
meetings.cpp:53:42: warning: unused variable 'cpo' [-Wunused-variable]
   53 |   long long i,j,n,m,q,cn,cm,fn,fm,ru,cva,cpo,cmi,of = 2,cl,cr,mid,fl,fr,rel,rer;
      |                                          ^~~

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