답안 #626307

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
626307 2022-08-11T11:24:20 Z Kaitokid 송신탑 (IOI22_towers) C++17
컴파일 오류
0 ms 0 KB
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1000000001;
extern struct nod*empty;
struct nod{
int val;
nod*l,*r;
nod()
{
    l=r=this;
    val=0;
}
nod(int x,nod*ll=empty,nod*rr=empty)
{
    val=x;
    l=ll,r=rr;
}
};
nod*empty=new nod();
nod*insert(nod*rt,int x,int st=0,int en=inf)
{
    if(st>x||en<x)return rt;
    if(st==en)return new nod(rt->val+1);
    int mid=(st+en)>>1;
    nod*s1=insert(rt->l,x,st,mid);
    nod*s2=insert(rt->r,x,mid+1,en);
    return new nod(s1->val+s2->val,s1,s2);
}
int cal(nod*rt1,nod*rt2,int l,int r,int st=0,int en=inf)
{
    if(st>r||en<l)return 0;
    if(st>=l && en<=r)return rt1->val-rt2->val;
    int mid=(st+en)/2;
    return cal(rt1->l,rt2->l,l,r,st,mid)+cal(rt1->r,rt2->r,l,r,mid+1,en);
}


nod*prs[100009];
int sg[4][400009];
int frs(int id,int l,int r,int d,int st,int en,int x=0)
{
    if(st>r||en<l)return -1;
    if(sg[id][x]<d)return -1;
    if(st==en)return st;
    int mid=(st+en)>>1;
    int u=frs(id,l,r,d,st,mid,(x<<1));
    if(u!=-1)return u;
    return frs(id,l,r,d,mid+1,en,(x<<1)|1);
}
int lst(int id,int l,int r,int d,int st,int en,int x=0)
{
    if(st>r||en<l)return -1;
    if(sg[id][x]<d)return -1;
    if(st==en)return st;
    int mid=(st+en)>>1;
    int u=lst(id,l,r,d,mid+1,en,(x<<1)|1);
    if(u!=-1)return u;
    return lst(id,l,r,d,st,mid,(x<<1));

}
int cal(int id,int l,int r,int st,int en,int x=0)
{
    if(st>r|| en<l)return 0;
    if(st>=l && en<=r)return sg[id][x];
    int mid=(st+en)/2;
    return max(cal(id,l,r,st,mid,(x<<1)),cal(id,l,r,mid+1,en,(x<<1)|1));
}
void build(int id,vector<int>&v,int st,int en,int x=0)
{
    if(st==en){sg[id][x]=v[st];return;}
    int mid=(st+en)>>1;
    build(id,v,st,mid,(x<<1));
    build(id,v,mid+1,en,(x<<1)|1);
    sg[id][x]=max(sg[id][(x<<1)],sg[id][(x<<1)|1]);

}
int sz;
void init(int N,vector<int> H)
 {
     sz=N;
     build(0,H,0,N-1);
     stack<int>st;
     vector<int>g;
    for(int i=0;i<N;i++)
    {
        while((!st.empty())&&(H[st.top()]>H[i]))st.pop();
        if(st.empty() ){g.push_back(inf);st.push(i);continue;}
        if(st.top()==i-1){g.push_back(0);st.push(i);continue;}int u=cal(0,st.top()+1,i-1,0,N-1);
        g.push_back(u-H[i]);
        st.push(i);
    }
    vector<int>f;
    while(!st.empty())st.pop();
    for(int i=N-1;i>=0;i--)
    {
        while((!st.empty())&&(H[st.top()]>H[i]))st.pop();
        if(st.empty() ){f.push_back(inf);st.push(i);continue;}
        if( st.top()==i+1){f.push_back(0);st.push(i);continue;}
        int u=cal(0,i+1,st.top()-1,0,N-1);
        f.push_back(u-H[i]);
        st.push(i);
    }
    build(1,f,0,N-1);
    build(2,g,0,N-1);
    prs[0]=empty;
    for(int i=0;i<N;i++)
        prs[i+1]=insert(prs[i],min(f[i],g[i]));
 }
 int max_tower(int L,int R,int D)
 {
     if(L==R)return 1;
     if(L==R-1)return 1;
     int u=frs(1,L,R,D,0,sz-1);
     int v=lst(2,L,R,D,0,sz-1);
     if(u==-1 || v==-1 || u>v)return 1;
     int ans=2+cal(prs[v],prs[u+1],D,inf);
     return ans;
 }
int main()
{

    return 0;
}

Compilation message

towers.cpp:14:18: error: reference to 'empty' is ambiguous
   14 | nod(int x,nod*ll=empty,nod*rr=empty)
      |                  ^~~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from towers.cpp:1:
/usr/include/c++/10/bits/range_access.h:281:5: note: candidates are: 'template<class _Tp> constexpr bool std::empty(std::initializer_list<_Tp>)'
  281 |     empty(initializer_list<_Tp> __il) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:272:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  272 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:263:5: note:                 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  263 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
towers.cpp:5:19: note:                 'nod* empty'
    5 | extern struct nod*empty;
      |                   ^~~~~
towers.cpp:14:31: error: reference to 'empty' is ambiguous
   14 | nod(int x,nod*ll=empty,nod*rr=empty)
      |                               ^~~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from towers.cpp:1:
/usr/include/c++/10/bits/range_access.h:281:5: note: candidates are: 'template<class _Tp> constexpr bool std::empty(std::initializer_list<_Tp>)'
  281 |     empty(initializer_list<_Tp> __il) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:272:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  272 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:263:5: note:                 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  263 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
towers.cpp:5:19: note:                 'nod* empty'
    5 | extern struct nod*empty;
      |                   ^~~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:106:12: error: reference to 'empty' is ambiguous
  106 |     prs[0]=empty;
      |            ^~~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from towers.cpp:1:
/usr/include/c++/10/bits/range_access.h:281:5: note: candidates are: 'template<class _Tp> constexpr bool std::empty(std::initializer_list<_Tp>)'
  281 |     empty(initializer_list<_Tp> __il) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:272:5: note:                 'template<class _Tp, long unsigned int _Nm> constexpr bool std::empty(const _Tp (&)[_Nm])'
  272 |     empty(const _Tp (&)[_Nm]) noexcept
      |     ^~~~~
/usr/include/c++/10/bits/range_access.h:263:5: note:                 'template<class _Container> constexpr decltype (__cont.empty()) std::empty(const _Container&)'
  263 |     empty(const _Container& __cont) noexcept(noexcept(__cont.empty()))
      |     ^~~~~
towers.cpp:20:5: note:                 'nod* empty'
   20 | nod*empty=new nod();
      |     ^~~~~