Submission #1135520

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135520		Unforgettablepl	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	368 ms	20208 KiB

Main

// #pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree {
    vector<int> tree;
    segtree():tree(524288){}
    int get(int a,int b) {
        a+=262144;b+=262144;
        int ans = 0;
        while(a<=b) {
            if(a&1)ans=max(ans,tree[a++]);
            if(b%2==0)ans=max(ans,tree[b--]);
            a/=2;b/=2;
        }
        return ans;
    }
    void update(int k,int x) {
        k+=262144;
        tree[k]=x;
        while(k/=2)tree[k]=max(tree[2*k],tree[2*k+1]);
    }
};

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> P(n+1);
    segtree seg;
    vector<int> lookup(n+1);
    for(int i=1;i<=n;i++) {
        cin>>P[i];
        lookup[P[i]]=i;
        seg.update(i,P[i]);
    }
    vector<vector<int>> adj(n+1);
    for(int i=1;i<n;i++) {
        int a,b;cin>>a>>b;
        adj[a].emplace_back(b);
        adj[b].emplace_back(a);
    }
    vector<int> DP(n+1);
    for(int i=n;i;i--) {
        int idx = lookup[i];
        int r = idx-1;
        for(int jump=(1<<17);jump;jump/=2) {
            if(r+jump<=n and seg.get(idx,r+jump)==i)r+=jump;
        }
        r++;
        if(r==n+1)r=idx;
        int l = idx+1;
        for(int jump=(1<<17);jump;jump/=2) {
            if(l-jump>=1 and seg.get(l-jump,idx)==i)l-=jump;
        }
        l--;
        if(l==0)l=idx;
        DP[idx]=max(DP[r]+r-idx,DP[l]+idx-l);
    }
    cout << *max_element(DP.begin(),DP.end()) << '\n';
}

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