Submission #1312181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312181		vtnoo	Cat Exercise (JOI23_ho_t4)	C++20	0 / 100	1 ms	716 KiB

Main

#include <bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); i++)
#define R(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define sz(a) ((int) a.size())
#define all(a) a.begin(), a.end()
#define vi vector<ll>
#define pb emplace_back
#define me(a, x) memset(a, x, sizeof(a))
#define fst first
#define snd second
#define ii pair<int, int>
using namespace std;
const int MAXN=2e5+5,INF=1e9;
int n;
vector<ii>st;
ii que(int l,int r){
	l+=n,r+=n;
	ii a={0,0};
	while(l<r){
		if(l%2)a=max(a,st[l++]);
		if(r%2)a=max(a,st[--r]);
		l/=2,r/=2;
	}
	return a;
}
int main(){
	ios::sync_with_stdio(false); 
	cin.tie(nullptr);
	cin>>n;
	vi p(n);
	L(i,0,n-1)cin>>p[i];
	L(i,0,n-2){
		int a,b;cin>>a>>b;
	}
	st.resize(n*2);
	L(i,0,n-1)st[i+n]={p[i],i};
	R(i,n-1,1)st[i]=max(st[i*2],st[i*2+1]);
	int l=-1,r=n;
	int ans=0;
	while(r-l>2){
		int m=que(l+1,r).snd;
		ii lc=que(l+1,m),rc=que(m+1,r);
		//~ cout<<"==========="<<endl;
		//~ cout<<m<<endl;
		//~ cout<<lc.snd<<" "<<rc.snd<<endl;
		if(m-lc.snd>rc.snd-m){
			//~ cout<<lc.snd<<" "<<m<<endl;
			ans+=m-lc.snd;
			r=m;
		}else{
			//~ cout<<rc.snd<<" "<<m<<endl;
			ans+=rc.snd-m;
			l=m;
		}
		//~ cout<<l<<" "<<r<<endl;
		//~ cout<<ans<<endl;
	}
	cout<<ans<<endl;
}

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