Submission #250336

#	Time	Username	Problem	Language	Result	Execution time	Memory
250336		dvdg6566	Nivelle (COCI20_nivelle)	C++14	110 / 110	908 ms	314616 KiB

nivelle

#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 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 lst[26];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>S;
	N=SZ(S);
	memset(n,-1,sizeof(n));
	memset(lst,-1,sizeof(lst));
	for(int i=0;i<N;++i){
		int c=S[i]-'a';
		int t=lst[c];
		if(t!=-1)n[t]=i;
		p[i]=t;
		lst[c]=i;
	}
	ld l=0;
	ld u=1;
	while(u>l+1e-7){
		// assert(ask(u).f!=-1);
		ld m=(l+u)/2;
		pi t=ask(m);
		if(t.f==-1)l=m;
		else u=m;
	}
	// assert(ask(u).f!=-1);
	pi x=ask(u);
	cout<<x.f+1<<' '<<x.s+1<<'\n';
}

• Subtask 1: 7 / 7
• Subtask 2: 17 / 17
• Subtask 3: 13 / 13
• Subtask 4: 25 / 25
• Subtask 5: 48 / 48