oj.uz

Submission #250336

# Submission time Handle Problem Language Result Execution time Memory
250336 2020-07-17T13:00:34 Z dvdg6566 Nivelle (COCI20_nivelle) C++14
110 / 110
 908 ms 314616 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1024 KB Output is correct
2 Correct 1 ms 896 KB Output is correct
3 Correct 1 ms 1024 KB Output is correct
4 Correct 1 ms 1024 KB Output is correct
5 Correct 1 ms 1024 KB Output is correct
6 Correct 1 ms 1024 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7040 KB Output is correct
2 Correct 17 ms 6960 KB Output is correct
3 Correct 19 ms 7040 KB Output is correct
4 Correct 21 ms 7040 KB Output is correct
5 Correct 16 ms 7040 KB Output is correct
6 Correct 19 ms 7032 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 682 ms 314464 KB Output is correct
2 Correct 636 ms 314616 KB Output is correct
3 Correct 632 ms 314456 KB Output is correct
4 Correct 659 ms 314392 KB Output is correct
5 Correct 699 ms 314476 KB Output is correct
6 Correct 732 ms 314488 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 645 ms 314488 KB Output is correct
2 Correct 678 ms 314488 KB Output is correct
3 Correct 658 ms 314488 KB Output is correct
4 Correct 639 ms 314488 KB Output is correct
5 Correct 653 ms 314488 KB Output is correct
6 Correct 628 ms 314444 KB Output is correct

Subtask #5
48.0 / 48.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 314596 KB Output is correct
2 Correct 701 ms 314424 KB Output is correct
3 Correct 608 ms 314488 KB Output is correct
4 Correct 771 ms 314480 KB Output is correct
5 Correct 850 ms 314420 KB Output is correct
6 Correct 579 ms 314488 KB Output is correct