Submission #968729

#	Time	Username	Problem	Language	Result	Execution time	Memory
968729		vjudge1	Sequence (APIO23_sequence)	C++17	100 / 100	1136 ms	165252 KiB

sequence

#include "sequence.h"
#include <bits/stdc++.h>
using namespace std;

namespace Me{
	constexpr int N=5e5+5,INF{0x3f3f3f3f};
	struct Rg{
		int l,r;
		inline bool contain(int x)const{
			return x>=l&&x<=r;
		}
		Rg(int l,int r):l{l},r{r}{}
		Rg(int i):Rg(i,i){}
		Rg():Rg(0,0){}
	};
	inline Rg operator+(Rg a,Rg b){return Rg(a.l+b.l,a.r+b.r);}
	inline Rg operator-(Rg a,Rg b){return Rg(a.l-b.r,a.r-b.l);}
	inline Rg &operator+=(Rg &a,Rg b){return a=a+b;}
	inline Rg operator|(Rg a,Rg b){return Rg(min(a.l,b.l),max(a.r,b.r));}
	inline bool operator&(Rg a,Rg b){if(a.l>b.l)return b&a; return a.r>=b.l;}
	int n,a[N];
	vector<int> pos[N];
	struct Seg{
		int id;
		Seg(int _):id{_}{}
		struct{
			int l,r,lz;
			Rg rg;
			inline void init(int x){
				rg=Rg(x);
			}
		}tr[N<<2];
		inline void pup(int k){
			tr[k].rg=tr[k<<1].rg|tr[k<<1|1].rg;
		}
		inline void add(int k,int v){
			tr[k].rg+=Rg(v);
			tr[k].lz+=v;
		}
		inline void pdn(int k){
			if(tr[k].lz){
				add(k<<1,tr[k].lz),add(k<<1|1,tr[k].lz);
				tr[k].lz=0;
			}
		}
		void build(int k,int l,int r){
			tr[k].l=l,tr[k].r=r,tr[k].lz=0;
			if(tr[k].l==tr[k].r) tr[k].init(id==1?l:-l);
			else{
				int mi((l+r)>>1);
				build(k<<1,l,mi),build(k<<1|1,mi+1,r),pup(k);
			}
		}
		void modify(int k,int l,int r,int v){
			if(tr[k].l>=l&&tr[k].r<=r){
				return add(k,v);
			}
			pdn(k); int mi((tr[k].l+tr[k].r)>>1);
			if(l<=mi) modify(k<<1,l,r,v);
			if(r>mi) modify(k<<1|1,l,r,v);
			pup(k);
		}
		Rg query(int k,int l,int r){
			if(l>r) return Rg{INF,-INF};
			if(tr[k].l>=l&&tr[k].r<=r) return tr[k].rg;
			pdn(k); int mi((tr[k].l+tr[k].r)>>1);
			if(r<=mi) return query(k<<1,l,r);
			else if(l>mi) return query(k<<1|1,l,r);
			else return query(k<<1,l,r)|query(k<<1|1,l,r);
		}
	}segx(1),segy(2);
	struct Fwk{
		int n,s[N];
		inline void init(int _n){
			n=_n; memset(s+1,0x3f,n*sizeof(int));
		}
		inline void add(int x,int v){
			for(;x;x^=x&-x) s[x]=min(s[x],v);
		}
		inline void erase(int x){
			for(;x;x^=x&-x) s[x]=INF;
		}
		inline int query(int x){ int v{INF};
			for(;x<=n;x+=x&-x) v=min(v,s[x]);
			return v;
		}
	}fwk;

	struct Mdf{int y,v;};
	vector<Mdf> ads[N];
	vector<int> qs[N];
	int ans{0};
	void sweep(vector<tuple<int,int,int,int> > &ps){
		// 矩形 min
		sort(ps.begin(),ps.end(),
			[](const auto &a,const auto &b){
				if(get<1>(a)!=get<1>(b)) return get<1>(a) > get<1>(b); 
				return get<0>(a) < get<0>(b);
			}
		);
		auto disc=[&ps](){
			vector<int> vs;
			for(const auto &p:ps) vs.emplace_back(get<2>(p));
			sort(vs.begin(),vs.end()),vs.erase(unique(vs.begin(),vs.end()),vs.end());
			for(auto &p:ps) get<2>(p)=lower_bound(vs.begin(),vs.end(),get<2>(p))-vs.begin()+1;
			return (int)vs.size();
		};
		int mx{disc()};
		fwk.init(mx);
		for(const auto &p:ps){
			int t{get<0>(p)},y{get<2>(p)},v{get<3>(p)};
			if(t==1) fwk.add(y,v);
			else ans=max(ans,v-fwk.query(y));
		}
	}
	int solve(){
		fwk.init(n);
		for(int i{1};i<=n;++i){
			pos[a[i]].emplace_back(i);
		}
		segx.build(1,0,n),segy.build(1,0,n);
		for(int i{1};i<=n;++i){
			for(int j:pos[i-1]) segy.modify(1,j,n,+2);
			for(int j:pos[i]) segx.modify(1,j,n,-2);
			vector<tuple<int,int,int,int> > ps;
			pos[i].emplace_back(n+1);
			int k{0};
			for(int x{0};x<(int)pos[i].size();++x){
				int j{pos[i][x]};
				auto rgx=segx.query(1,k,j-1),rgy=segy.query(1,k,j-1);
				ps.emplace_back(1,rgx.r,rgy.r,x);
				ps.emplace_back(2,rgx.l,rgy.l,x);
				k=j;
			}
			pos[i].pop_back();
			sweep(ps);
		}
		return ans;
	}
}

int sequence(int N, std::vector<int> A){
    Me::n=N; for(int i{0};i<N;++i) Me::a[i+1]=A[i];
	return Me::solve();
}

• 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