Submission #1089007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089007		Math4Life2020	Sequence (APIO23_sequence)	C++17	50 / 100	2076 ms	83540 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);
}

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 mem[Nm];
void upd(ll x, ll v) {
	mem[x]=v;
}
ll sum(ll x) {
	ll v = 0;
	for (ll i=0;i<=x;i++) {
		v += mem[i];
	}
	return v;
}
ll qmin(ll a, ll b) {
	ll ans = INF;
	for (ll i=a;i<=b;i++) {
		ans = min(ans,sum(i));
	}
	return ans;
}
ll qmax(ll a, ll b) {
	ll ans = -INF;
	for (ll i=a;i<=b;i++) {
		ans = max(ans,sum(i));
	}
	return ans;
}*/

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;
				}
			}
			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";
			auto PT2 = indv.upper_bound(xmin);
			PT2--;
			ans=max(ans,min(((*PT2).second)+1-k,fval[k]));
			prev=v0[k];
		}
	}
	return ans;
}

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