Submission #730512

#	Time	Username	Problem	Language	Result	Execution time	Memory
730512		kym	Passport (JOI23_passport)	C++14	48 / 100	68 ms	51640 KiB

passport

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define FOR(i,s,e) for(int i = s; i <= (int)e; ++i)
#define DEC(i,s,e) for(int i = s; i >= (int)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#define reach cerr << "LINE: " << __LINE__ << "\n";
#else
#define reach 
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
typedef pair <int, int> pi;
typedef tuple<int,int,int> ti3;
typedef tuple<int,int,int,int> ti4;
int rand(int a, int b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (long long)1e18 + 500;
template <typename T> void chmax(T& a, const T b) { a=max(a,b); }
template <typename T> void chmin(T& a, const T b) { a=min(a,b); }
const int MAXN = 2505;
int n;
pi A[MAXN];
int M[MAXN];
int lf[MAXN];
int rg[MAXN];
struct minnode {
	int s,e,m;
	pi val;
	minnode *l, *r;
	minnode (int _s, int _e) {
		s=_s;e=_e;m=(s+e)/2;
		if(s!=e){
			l=new minnode(s,m);
			r=new minnode(m+1,e);
		}
	}
	void set(int x, pi nval) {
		if(s==e){
			val=nval;
			return;
		}
		if(x>m)r->set(x,nval);
		else l->set(x,nval);
		val=min(l->val,r->val);
	}
	pi query(int x, int y) {
		if(s==x&&e==y)return val;
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return min(l->query(x,m), r->query(m+1,y));
	}
} *seglf;
struct maxnode {
	int s,e,m;
	pi val;
	maxnode *l, *r;
	maxnode (int _s, int _e) {
		s=_s;e=_e;m=(s+e)/2;
		if(s!=e){
			l=new maxnode(s,m);
			r=new maxnode(m+1,e);
		}
	}
	void set(int x, pi nval) {
		if(s==e){
			val=nval;
			return;
		}
		if(x>m)r->set(x,nval);
		else l->set(x,nval);
		val=max(l->val,r->val);
	}
	pi query(int x, int y) {
		if(s==x&&e==y)return val;
		if(x>m)return r->query(x,y);
		else if(y<=m)return l->query(x,y);
		else return max(l->query(x,m), r->query(m+1,y));
	}
} *segrg;
int depthl[MAXN];
int depthr[MAXN];
int memo[MAXN][MAXN];
int q;

struct SparseTable {
	vector<vector<int>> ST;
	int N,K;
	inline int msb(unsigned int x) { return 32-__builtin_clz(x); }
	SparseTable(int _N, int a[]){
		N=_N;
		K=msb(n);
		ST.resize(K);
		ST[0]=vector<int>(a,a+N);
		FOR(k,1,K){
			for(int i=0;i+(1<<k)<=N;++i){
				ST[k].pb(min(ST[k-1][i], ST[k-1][i+(1<<(k-1))]));
			}
		}
	}
	int query(int x, int y){ 
		int k=msb(y-x+1)-1;
		return min(ST[k][x],ST[k][y-(1<<k)+1]);
	}
} *mostL,*mostR,*bestM;
int dpdp(int l, int r){
	if(~memo[l][r])return memo[l][r];
	db2(l,r);
	if(l==1&&r==n)return 0;

	int &ans=memo[l][r];
	ans=oo;
	ans=min({
		1+dpdp(mostL->query(l,r),r),
		1+dpdp(l,-mostR->query(l,r)),
		1+bestM->query(l,r)
	});
	return ans;
}
int LL[MAXN], RR[MAXN];
int32_t main() 
{
	IAMSPEED
	cin >> n;
	FOR(i,1,n)cin>>A[i].f>>A[i].s;
	FOR(i,1,n)LL[i]=A[i].f;
	FOR(i,1,n)RR[i]=-A[i].s;
	mostL=new SparseTable(n+1,LL);
	mostR=new SparseTable(n+1,RR);
	seglf=new minnode(0,n);
	segrg=new maxnode(0,n);
	seglf->set(1,{1,1});
	FOR(i,2,n){
		if(A[i].f==1){
			lf[i]=1;
			depthl[i]=1;
		}
		else {
			if(A[i].f>i-1){
				depthl[i]=oo;
				lf[i]=n+1;
			} else{ // L[i]<=i-1
				pi res=seglf->query(A[i].f,i-1);
				lf[i]=res.s;
				depthl[i]=depthl[res.s]+1;
			}
		}
		seglf->set(i,{lf[i],i});
	}

	segrg->set(n,pi(n,n));
	DEC(i,n-1,1){
		if(A[i].s==n){
			rg[i]=n;
			depthr[i]=1;
		}
		else {
			if(i+1>A[i].s){
				depthr[i]=oo;
				rg[i]=0;
			} else{
				pi res=segrg->query(i+1,A[i].s);
				rg[i]=res.s;
				depthr[i]=depthr[res.s]+1;
			}
		}
		segrg->set(i,{rg[i],i});
	}
	dba(lf,1,n);
	dba(rg,1,n);
	dba(depthl,1,n);
	dba(depthr,1,n);
	SparseTable TL=SparseTable(n+1,depthl);
	SparseTable TR=SparseTable(n+1,depthr);
	FOR(i,1,n){
		db3(i,A[i].f,A[i].s);
		M[i]=TL.query(A[i].f,A[i].s)+TR.query(A[i].f,A[i].s);
	}
	
	bestM=new SparseTable(n+1,M);
	cin>>q;
	memset(memo,-1,sizeof memo);
	while(q--){
		int x; cin >> x;
		int res=dpdp(x,x);
		if(res>=oo)cout<<-1<<'\n';
		else cout<<res<<'\n';
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 8 / 8
• Subtask 5: 0 / 46