제출 #916154

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
916154		GrindMachine	Gap (APIO16_gap)	C++17	70 / 100	52 ms	7600 KiB

gap

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

read some solutions a long time ago, slightly remember some ideas
may have still solved it if not for those ideas

*/

const int MOD = 1e9 + 7;
const int N = 4e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

#include "gap.h"

ll n;

ll go(ll l, ll r){
	if(l >= r) return 0;

	// split into B segs
	ll B = n-1;
	ll len = r-l+1;
	ll cnt1 = B;
	ll cnt2 = len%B;
	cnt1 -= cnt2;

	vector<pll> segs;
	ll ptr = l;

	rep1(i,cnt1){
		if(len >= B){
			segs.pb({ptr,ptr+len/B-1});
		}
		ptr += len/B;
	}

	rep1(i,cnt2){
		segs.pb({ptr,ptr+ceil2(len,B)-1});
		ptr += ceil2(len,B);
	}

	assert(ptr == r+1);

	vector<pll> seg_vals;
	ll ans = 0;

	rep(i,sz(segs)){
		ll mn,mx;
		auto [lx,rx] = segs[i];
		MinMax(lx,rx,&mn,&mx);
		seg_vals.pb({mn,mx});
	}

	ll last_active = -1;

	for(auto [mn,mx] : seg_vals){
		if(mn != -1){
			if(last_active != -1){
				amax(ans,mn-last_active);
			}
			last_active = mx;
		}
	}

	return ans;
}

long long findGap(int T, int n_)
{
	n = n_;
	ll mn,mx;
	MinMax(0,inf2,&mn,&mx);
	// ll ans = ceil2(mx-mn,n-1);

	ll ans = max(go(mn,mx),ceil2(mx-mn,n-1));
	return ans;
}

• Subtask 1: 0 / 30
• Subtask 2: 70 / 70