제출 #250290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
250290		dvdg6566	Nivelle (COCI20_nivelle)	C++14	62 / 110	1085 ms	393340 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 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=200001;
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));
	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;
			x=t;
		}
	}
	// for(int i=0;i<N;++i)cout<<n[i]<<' ';cerr<<'\n';
	ld l=0;
	ld u=1;
	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';
}

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