Submission #1143794

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143794		bekzhan29	Xylophone (JOI18_xylophone)	C++20	100 / 100	27 ms	448 KiB

xylophone

#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5100;
ll a[N];
ll querry(ll l, ll r)
{
	// cout<<"query: "<<l<<" "<<r<<endl;
	ll ans=query(l,r);
	// cout<<"answer: "<<ans<<endl;
	return ans;
}
void solve(int n) {
	a[1]=0;
	a[2]=querry(1,2);
	for(ll i=3;i<=n;i++)
	{
		ll x=querry(i-1,i);
		if(a[i-2]<a[i-1])
		{
			if(querry(i-2,i)==a[i-1]-a[i-2]+x)
				a[i]=a[i-1]+x;
			else
				a[i]=a[i-1]-x;
		}
		else
		{
			if(querry(i-2,i)==a[i-2]-a[i-1]+x)
				a[i]=a[i-1]-x;
			else
				a[i]=a[i-1]+x;
		}
	}
	ll mn=1,mx=1;
	// for(ll i=1;i<=n;i++)
	// 	cout<<a[i]<<" ";
	// cout<<endl;
	for(ll i=2;i<=n;i++)
	{
		if(a[mn]>a[i])
			mn=i;
		if(a[mx]<a[i])
			mx=i;
	}
	if(mn>mx)
	{
		for(ll i=1;i<=n;i++)
			a[i]*=-1;
		swap(mn,mx);
	}
	mx=a[mn];
	// for(ll i=1;i<=n;i++)
	// 	cout<<a[i]-mx+1<<" ";
	// cout<<endl;
	for(ll i=1;i<=n;i++)
		answer(i,a[i]-mx+1);
}
/*
5
2 1 5 3 4

*/

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53