Submission #1088823

#	Time	Username	Problem	Language	Result	Execution time	Memory
1088823		peacebringer1667	Cat Exercise (JOI23_ho_t4)	C++17	51 / 100	167 ms	26960 KiB

Main

#include<bits/stdc++.h>
#define ll long long
#define ldb long double
#define fi first
#define se second
#define sza(a) (int)a.size()
#define pir pair<int,int>
#define pirll pair<ll,ll>
using namespace std;
const int maxn = 2e5 + 5;

vector <vector<int>> vec(maxn);
int a[maxn];

int input(int n){
	int root = 0;
	for (int i = 1 ; i <= n ; i++){
		cin >> a[i];
		if (a[i] == n) root = i;
	}
	
	for (int i = 1 ; i < n ; i++){
		int u,v;
		cin >> u >> v;
		vec[u].push_back(v);
		vec[v].push_back(u);
	}
	return root;
}

namespace sub_1_2_3_4{
	bool check(int n){
		return (n <= 5000);
	}
	const int N = 5090;
	
	int node[N],dp[N];
	
	int dfs(int u,int par,int len,int cap){
		int res = dp[u] + len;
		
		for (int v : vec[u])
		  if (v != par && a[v] < cap)
		    res = max(res,dfs(v,u,len + 1,cap));
		return res;
	}
	
	ll solve(int n,int root){
		for (int i = 1 ; i <= n ; i++)
		  node[a[i]] = i;
	    
	    for (int i = 1 ; i <= n ; i++)
	       dp[node[i]] = dfs(node[i],node[i],0,i);
	    
	    return dp[root];
	}
}

namespace sub5{
	const ll inf = 1e17;
	struct segment_tree{
		ll seg[4*maxn];
		
		void init(int l,int r,int v){
			seg[v] = -inf;
		    if (l == r) return;
			
			int w = (l + r)/2;
			init(l,w,2*v + 1);
			init(w + 1,r,2*v + 2);	
		}
		
		void update(int l,int r,int v,int p,ll val){
			if (l > p || r < p) return;
			if (l == r){
				seg[v] = val;
				return;
			}
			
			int w = (l + r)/2;
			update(l,w,2*v + 1,p,val);
			update(w + 1,r,2*v + 2,p,val);
			seg[v] = max(seg[2*v + 1],seg[2*v + 2]);
		}
		
		ll calc(int l,int r,int v,int lx,int rx){
			if (l > rx || r < lx) return -inf;
			if (l >= lx && r <= rx) return seg[v];
			
			int w = (l + r)/2;
			return max(calc(l,w,2*v + 1,lx,rx),calc(w + 1,r,2*v + 2,lx,rx));
		}
	};
	segment_tree U,D;
	
	int node[maxn],nxt[maxn],lst[maxn];
	ll dp[maxn];
	
	void prepare(int n){
		U.init(1,n,0);
		D.init(1,n,0);
		
		for (int i = 1 ; i <= n ; i++){
			nxt[i] = n + 1;
            node[a[i]] = i;
		}
		U.update(1,n,0,node[1],node[1]);
		D.update(1,n,0,node[1],-node[1]);
		
		deque <int> dq;
		for (int i = 1 ; i <= n ; i++){
			while (dq.size() && a[dq.back()] < a[i]) dq.pop_back();
			
			lst[i] = (!dq.size()) ? 1 : (dq.back() + 1);
			dq.push_back(i);
		}
		
		dq.clear();
		for (int i = n ; i > 0 ; i--){
			while (dq.size() && a[dq.back()] < a[i]) dq.pop_back();
			
			nxt[i] = (!dq.size()) ? n : (dq.back() - 1);
	        dq.push_back(i);
		}
	}
	
	ll solve(int n,int root){
	    prepare(n);
	    ll res = 0;
	    
		for (int i = 2 ; i <= n ; i++){
			int p = node[i];
			
			ll v = max(U.calc(1,n,0,p,nxt[p]) - p,D.calc(1,n,0,lst[p],p) + p);
			v = max(v,0LL);
			
			U.update(1,n,0,p,v + p);
			D.update(1,n,0,p,v - p);
			
			res = max(res,v);
		}
	    
	    return res;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
//	freopen("CAT.inp","r",stdin);
//	freopen("CAT.out","w",stdout);
	int n;
	cin >> n;
	int root = input(n);
	
	if (sub_1_2_3_4::check(n)){
	  cout << sub_1_2_3_4::solve(n,root);
      return 0;
	}
	

	cout << sub5::solve(n,root);

	return 0;
}

• Subtask 1: 7 / 7
• Subtask 2: 7 / 7
• Subtask 3: 7 / 7
• Subtask 4: 10 / 10
• Subtask 5: 20 / 20
• Subtask 6: 0 / 23
• Subtask 7: 0 / 26