| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 250294 | dvdg6566 | Nivelle (COCI20_nivelle) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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';
}