Submission #1208859

#	Time	Username	Problem	Language	Result	Execution time	Memory
1208859		kitkat12	Cat Exercise (JOI23_ho_t4)	C++20	41 / 100	140 ms	36300 KiB

Main

// Problem URL: https://oj.uz/problem/view/JOI23_ho_t4
// Start Time: 5/27/2025, 9:44:51 PM

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define debug(x) std::cout << #x << ": " << x << "\n"
#define all(v) v.begin(), v.end()
#define li(i,a,b) for (int i = a; i < b; i++)
#define endl '\n'
#define mem(name,val) memset(name,val,sizeof(name))
#define max(a,b) max<ll>(a,b)
#define min(a,b) min<ll>(a,b)

const int nmax = 2e5+3;
vector<int> adj[nmax];
int p[nmax], pos[nmax];
int n;

int t[2*nmax]; // promeni u sparse table jer nema update
void build(){for(int x = n-1; x>0; x--)t[x]=max(t[2*x],t[2*x+1]);}
int get (int l, int r){
    int res = -1;
    for(l+=n,r+=n;l<r;l>>=1,r>>=1){
        if(l&1)res=max(res,t[l++]);
        if(r&1)res=max(res,t[--r]);
    }
    return res;
}

set<int> obst;

ll maxmoves(int mn){ 
    if(obst.count(mn-1) && obst.count(mn+1))return 0; // base case

    auto it = obst.upper_bound(mn);
    int rb = *it; 
    it--;
    int lb = *it;

    int hl = get(lb+1-1, mn-1);   
    int l  = (hl == -1 ? mn : pos[hl]);

    int hr = get(mn+1-1, rb-1);
    int r  = (hr == -1 ? mn : pos[hr]);

    ll left = 0, right = 0;
    obst.insert(mn);
    if(l!=mn)
        left = abs<ll>(mn-l) + maxmoves(l);
    if(r!=mn)
        right = abs<ll>(r-mn)+ maxmoves(r);

    return max(left,right);
}

int main() 
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin>>n;
    li(i,1,n+1){
        cin>>p[i];
        t[i+n-1] = p[i];
        pos[p[i]]=i;
    }
    build();
    li(i,0,n-1){
        int a,b;
        cin>>a>>b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    obst.insert(0);
    obst.insert(n+1);

    cout<<maxmoves(pos[n]);

    return 0;
}

• 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