Submission #547521

#	Time	Username	Problem	Language	Result	Execution time	Memory
547521		farhan132	Xylophone (JOI18_xylophone)	C++17	100 / 100	97 ms	444 KiB

xylophone

#include "xylophone.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 5005;

ll a[N] , slope[N] , pre[N];

ll sign(ll x){
	if(x < 0) return -1;
	return 1;
}


void solve(int n) {
	pre[1] = 0;
	slope[2] = pre[2] = query(1, 2);
	for(ll i = 3; i <= n; i++){
		ll k1 = query(i-1,i);
		ll k2 = query(i-2,i);
		if(abs(k1) + abs(slope[i - 1]) == abs(k2)) slope[i] = sign(slope[i-1]) * k1;
		else slope[i] = sign(-slope[i-1]) * k1;
		pre[i] = pre[i - 1] + slope[i];
	}
	ii mn = {1e9, 0} , mx = {-1e9, 0};
	for(ll i = 1; i <= n; i++){
		mn = min(mn, {pre[i], i});
		mx = max(mx, {pre[i], i});
	}
	ll s = 1, cur;
	if(mn.ss < mx.ss){
		cur = 1 + abs(mn.ff);
	}else{
		s = -1;
		//cout << mx.ff << '\n';
		cur = 1 +  mx.ff;
	}
	for(ll i = 1; i <= n; i++){
		pre[i] *= s;
		answer(i, cur + pre[i]);
	}
}

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