Submission #1089013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089013		Math4Life2020	Sequence (APIO23_sequence)	C++17	100 / 100	1128 ms	87064 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 524288; const ll E = 19;
const ll INF = 1e18;
ll stmax[2*Nm];
ll stmin[2*Nm];
ll stsum[2*Nm];

ll v2(ll x) {
	if (x==0) {
		return 100;
	}
	return __builtin_ctz(x);
}

ll l2(ll x) {
	return (31-__builtin_clz(x));
}

void wipe() {
	for (ll i=0;i<(2*Nm);i++) {
		stmax[i]=0;
		stmin[i]=0;
		stsum[i]=0;
	}
}

void upd(ll x, ll d) {
	//updates value at x to d
	ll p = Nm+x;
	stsum[p]=d;
	stmax[p]=d;
	stmin[p]=d;
	p=p/2;
	while (p>0) {
		stsum[p]=stsum[2*p]+stsum[2*p+1];
		stmax[p]=max(stmax[2*p],stsum[2*p]+stmax[2*p+1]);
		stmin[p]=min(stmin[2*p],stsum[2*p]+stmin[2*p+1]);
		p=p/2;
	}
}

ll sum(ll x) {
	if (x<0) {
		return 0;
	}
	ll lx = v2(x+1);
	return (stsum[(x>>lx)+(1LL<<(E-lx))]+sum(x-(1LL<<lx)));
}

ll minr(ll a, ll lL) { //first index, log2 of length
	return (sum(a-1)+stmin[(a>>lL)+(1LL<<(E-lL))]);
}

ll maxr(ll a, ll lL) { //see above
	return (sum(a-1)+stmax[(a>>lL)+(1LL<<(E-lL))]);
}

ll qmin(ll a, ll b) {
	if (a>b) {
		return INF;
	}
	ll la = v2(a); ll lb = v2(b+1);
	if (la<=lb) {
		return min(minr(a,la),qmin(a+(1LL<<la),b));
	} else {
		return min(qmin(a,b-(1LL<<lb)),minr(((b>>lb)<<lb),lb));
	}
}

ll qmax(ll a, ll b) {
	if (a>b) {
		return -INF;
	}
	ll la = v2(a); ll lb = v2(b+1);
	if (la<=lb) {
		return max(maxr(a,la),qmax(a+(1LL<<la),b));
	} else {
		return max(qmax(a,b-(1LL<<lb)),maxr(((b>>lb)<<lb),lb));
	}
}

ll bsmin(ll a, ll b, ll mv) { //find largest index value in this range with array value <=mv
	if (a==b) {
		return a;
	}
	ll lg = min(v2(b+1),l2(b-a));
	if (minr(((b>>lg)<<lg),lg)<=mv) {
		return bsmin(b-(1LL<<lg)+1,b,mv);
	} else {
		return bsmin(a,b-(1LL<<lg),mv);
	}
}

ll bsmax(ll a, ll b, ll mv) {
	if (a==b) {
		return a;
	}
	ll lg = min(v2(b+1),l2(b-a));
	if (maxr(((b>>lg)<<lg),lg)>=mv) {
		return bsmax(b-(1LL<<lg)+1,b,mv);
	} else {
		return bsmax(a,b-(1LL<<lg),mv);
	}
}

int sequence(int N, vector<int> A) {
	ll ans = 1;
	wipe();
	for (ll i=0;i<N;i++) {
		upd(i,-1);
	}
	map<ll,vector<ll>> m0; //map: value -> index positions
	for (ll i=0;i<N;i++) {
		m0[A[i]].push_back(i);
	}
	for (auto PTR: m0) {
		//cout << "processing number "<<PTR.first<<"\n";
		vector<ll> v0 = PTR.second;
		map<ll,ll> indv;
		ll K = v0.size();
		for (ll k=0;k<K;k++) {
			indv[v0[k]]=k;
		}
		ll fval[K];
		ll prev = -1;
		for (ll k=0;k<K;k++) {
			ll MV = qmax(prev,v0[k]);
			ll xmin=v0[k]; ll xmax=N-1;
			/*while (xmin != xmax) {
				ll xq = (xmin+xmax+1)/2;
				if (MV>=qmin(xq,N-1)) {
					xmin=xq;
				} else {
					xmax=xq-1;
				}
			}*/
			xmin = bsmin(xmin,Nm-1,MV); //find largest index with value <=MV
			//cout << "k="<<k<<", bsmin="<<xmin<<"\n";
			auto PT2 = indv.upper_bound(xmin);
			PT2--;
			fval[k]=((*PT2).second)+1-k;
			//cout << "k="<<k<<", MV="<<MV<<"\n";
			prev=v0[k];
		}
		for (ll k=0;k<K;k++) {
			upd(v0[k],1);
		}
		prev = -1;
		for (ll k=0;k<K;k++) {
			ll MV = qmin(prev,v0[k]);
			ll xmin=v0[k]; ll xmax=N-1;
			/*while (xmin != xmax) {
				ll xq = (xmin+xmax+1)/2;
				if (MV<=qmax(xq,N-1)) {
					xmin=xq;
				} else {
					xmax=xq-1;
				}
			}*/
			//cout << "k="<<k<<", xmin="<<xmin<<"\n";
			xmin = bsmax(xmin,Nm-1,MV); //find largest index with value >=MV
			auto PT2 = indv.upper_bound(xmin);
			PT2--;
			ans=max(ans,min(((*PT2).second)+1-k,fval[k]));
			prev=v0[k];
		}
	}
	return ans;
}

Compilation message (stderr)

sequence.cpp: In function 'int sequence(int, std::vector<int>)':
sequence.cpp:130:22: warning: unused variable 'xmax' [-Wunused-variable]
  130 |    ll xmin=v0[k]; ll xmax=N-1;
      |                      ^~~~
sequence.cpp:153:22: warning: unused variable 'xmax' [-Wunused-variable]
  153 |    ll xmin=v0[k]; ll xmax=N-1;
      |                      ^~~~

• Subtask 1: 11 / 11
• Subtask 2: 17 / 17
• Subtask 3: 7 / 7
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 22 / 22
• Subtask 7: 18 / 18