Submission #250294

#TimeUsernameProblemLanguageResultExecution timeMemory
250294dvdg6566Nivelle (COCI20_nivelle)C++14
Compilation error
0 ms0 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<ll> vi; typedef pair<ll,ll> pi; typedef vector<pi> vpi; typedef long double ld; #define pb emplace_back #define mp make_pair #define lb lower_bound #define ub upper_bound #define ALL(x) x.begin(), x.end() #define SZ(x) (ll)x.size() #define f first #define s second const ll MAXN=100001; const ll MAXK=1000001; const ll INF = 1e9; const ll MOD = 1e9+7; string S; int A[MAXN]; int p[MAXN]; int n[MAXN]; int N; typedef pair<ld,int> pli; struct node{ int s,e,m,lz; node *l,*r; pli v; node(int _s,int _e,ld M):s(_s),e(_e){ m=(s+e)/2;v=mp(-(e+1)*M,e); // cerr<<v.f<<' '<<v.s<<'\n'; if(s!=e){ l=new node(s,m,M); r=new node(m+1,e,M); } } void up(int x,int y,int val){ if(s==x&&e==y){lz+=val;return;} if(y<=m)l->up(x,y,val); else if(x>m)r->up(x,y,val); else {l->up(x,m,val);r->up(m+1,y,val);} pli lh=l->v;lh.f+=l->lz; pli rh=r->v;rh.f+=r->lz; v=min(lh,rh); } pli ask(int x,int y){ if(s==x&&e==y){ return mp(v.f+lz,v.s); } pli ans; if(y<=m)ans=l->ask(x,y); else if (x>m)ans=r->ask(x,y); else ans=min(l->ask(x,m),r->ask(m+1,y)); ans.f+=lz; return ans; } }*root; pi ask(ld X){ root=new node(0,N-1,X); for(int i=0;i<N;++i)if(p[i]==-1){ root->up(i,N-1,1); } pli c=root->ask(0,N-1); if(c.f<=0)return mp(0,c.s); for(int i=1;i<N;++i){ root->up(i-1,N-1,-1); if(n[i-1]!=-1){ // cerr<<"Sec "<<n[i-1]<<'\n'; root->up(n[i-1],N-1,1); } pli tt=root->ask(i,N-1); tt.f+=(ld)i*X; if(tt.f<=0)return mp(i,tt.s); } return mp(-1,-1); } int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>N>>S; memset(n,-1,sizeof(n)); ll r=0; for(int i=0;i<26;++i){ int x=-1; for(int t=0;t<N;++t)if(S[t]-'a'==i){ p[t]=x; if(x!=-1)n[x]=t; else ++r; x=t; } } ld l=0; ld u=max((ld)r/(ld)N,0.01); while(u>l+1e-7){ ld m=(l+u)/2; pi t=ask(m); if(t.f==-1)l=m; else u=m; } pi x=ask(u); cout<<x.f+1<<' '<<x.s+1<<'\n'; }

Compilation message (stderr)

nivelle.cpp: In function 'int main()':
nivelle.cpp:97:27: error: no matching function for call to 'max(ld, double)'
  ld u=max((ld)r/(ld)N,0.01);
                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from nivelle.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:219:5: note: candidate: template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)
     max(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:219:5: note:   template argument deduction/substitution failed:
nivelle.cpp:97:27: note:   deduced conflicting types for parameter 'const _Tp' ('long double' and 'double')
  ld u=max((ld)r/(ld)N,0.01);
                           ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from nivelle.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:265:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)
     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:265:5: note:   template argument deduction/substitution failed:
nivelle.cpp:97:27: note:   deduced conflicting types for parameter 'const _Tp' ('long double' and 'double')
  ld u=max((ld)r/(ld)N,0.01);
                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from nivelle.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3462:5: note: candidate: template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)
     max(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
nivelle.cpp:97:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'long double'
  ld u=max((ld)r/(ld)N,0.01);
                           ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from nivelle.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3468:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)
     max(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
nivelle.cpp:97:27: note:   mismatched types 'std::initializer_list<_Tp>' and 'long double'
  ld u=max((ld)r/(ld)N,0.01);
                           ^