#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
//#pragma GCC optimize("Ofast") //#pragma GCC optimize "unroll-loops" //#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,avx2,fma,mmx,popcnt,tune=native" //#pragma GCC optimize "prefetch-loop-arrays"
using namespace std; using namespace __gnu_pbds;
#define foru(i,a,b) for(int i=(a);i<(b);i++)
#define ford(i,a,b) for(int i=(a);i>=(b);i--)
#define fori(a,b) foru(i,a,b)
#define forj(a,b) foru(j,a,b)
#define fork(a,b) foru(k,a,b)
#define seto(x,i) memset(x,i,sizeof x)
#define pf first
#define ps second
#define pb push_back
#define eb emplace_back
#define em emplace
#define mp make_pair
#define mt make_tuple
#define popcount __builtin_popcount
#define popcountll __builtin_popcountll
#define clz __builtin_clz
#define clzll __builtin_clzll
#define ctz __builtin_ctz
#define ctzll __builtin_ctzll
#define P2(x) (1LL<<(x))
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
#if __SIZEOF_INT128__
typedef __int128_t i128; typedef __uint128_t ui128;
#else
typedef int64_t i128; typedef uint64_t ui128;
#endif
typedef long long ll; typedef uint64_t ull; typedef int8_t byte; typedef long double lld;
typedef pair<int,int> pii; typedef pair<ll,ll> pll; typedef pair<lld,lld> pdd;
template<class T1,class T2> using ordered_map=tree<T1,T2,less<T1>,rb_tree_tag,tree_order_statistics_node_update>; template<class T1> using ordered_set=ordered_map<T1,null_type>;
template<class T> using minpq=std::priority_queue<T,vector<T>,greater<T>>; template<class T> using maxpq=std::priority_queue<T,vector<T>,less<T>>;
template<class T> using minpairingheap=__gnu_pbds::priority_queue<T,greater<T>,pairing_heap_tag>; template<class T>using maxpairingheap=__gnu_pbds::priority_queue<T,less<T>,pairing_heap_tag>;
const int inf=0x3f3f3f3f,MOD=1e9+7; const ll INF=0x3f3f3f3f3f3f3f3f; const lld PI=acos((lld)-1);
const ll SEED=443214^chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count();
mt19937 randgen(SEED); int randint(int a, int b){return uniform_int_distribution<int>(a,b)(randgen);} ll randll(ll a, ll b){return uniform_int_distribution<ll>(a,b)(randgen);}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll fpow(ll a,ll b){ll ret=1;for(;b;b>>=1){if(b&1) ret=ret*a%MOD;a=a*a%MOD;}return ret;}
template<class T1,class T2>constexpr const auto _min(const T1&x,const T2&y){return x<y?x:y;} template<class T,class...Ts>constexpr auto _min(const T&x,const Ts&...xs){return _min(x,_min(xs...));}
template<class T1,class T2>constexpr const auto _max(const T1&x,const T2&y){return x>y?x:y;} template<class T,class...Ts>constexpr auto _max(const T&x,const Ts&...xs){return _max(x,_max(xs...));}
#define min(...) _min(__VA_ARGS__)
#define max(...) _max(__VA_ARGS__)
template<class T1,class T2>constexpr bool ckmin(T1&x,const T2&y){return x>y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmin(T&x,const Ts&...xs){return ckmin(x,min(xs...));}
template<class T1,class T2>constexpr bool ckmax(T1&x,const T2&y){return x<y?x=y,1:0;} template<class T,class...Ts>constexpr bool ckmax(T&x,const Ts&...xs){return ckmax(x,max(xs...));}
struct chash{
static ll splitmix64(ll x){x+=0x9e3779b97f4a7c15; x=(x^(x>>30))*0xbf58476d1ce4e5b9; x=(x^(x>>27))*0x94d049bb133111eb; return x^(x>>31);}
template<class T> size_t operator()(const T &x) const{return splitmix64(hash<T>()(x)+SEED);}
template<class T1,class T2> size_t operator()(const pair<T1,T2>&x)const{return 31*operator()(x.first)+operator()(x.second);}};
void fIn(string s){freopen(s.c_str(),"r",stdin);} void fOut(string s){freopen(s.c_str(),"w",stdout);} void fIO(string s){fIn(s+".in"); fOut(s+".out");}
string to_string(char c){return string(1,c);} string to_string(char* s){return (string)s;} string to_string(string s){return s;}
template<class T> string to_string(complex<T> c){stringstream ss; ss<<c; return ss.str();} template<class T1,class T2> string to_string(pair<T1,T2> p){return "("+to_string(p.pf)+","+to_string(p.ps)+")";}
template<size_t SZ> string to_string(bitset<SZ> b){string ret=""; fori(0,SZ) ret+=char('0'+b[i]); return ret;}
template<class T> string to_string(T v){string ret="{"; for(const auto& x:v) ret+=to_string(x)+","; return ret+"}";}
void DBG(){cerr<<"]"<<endl;} template<class T,class... Ts> void DBG(T x,Ts... xs){cerr<<to_string(x); if(sizeof...(xs)) cerr<<", "; DBG(xs...);}
#ifdef LOCAL_PROJECT
#define dbg(...) cerr<<"Line("<< __LINE__<<") -> ["<<#__VA_ARGS__<<"]: [", DBG(__VA_ARGS__)
#else
#define dbg(...) 0
#endif
#define nl "\n"
const int N=0,M=MOD;
int T,n;
ll l,r,B,a,b,c,ans,op,x;
#ifdef LOCAL_PROJECT
vector<ll> ANS;
void MinMax(ll l,ll r,ll &mn,ll &mx){
assert(mn<=mx); op++; assert(op*2<=(n+1));
if(lower_bound(all(ANS),l)==upper_bound(all(ANS),r)){
mn=mx=-1;
return;
}
mn=*lower_bound(all(ANS),l);
mx=*prev(upper_bound(all(ANS),r));
if(mx==INF) mx=-1;
}
#else
#include "gap.h"
#endif
ll findGap(int T,int n){
MinMax(0,INF-1,&l,&r);
if(T==1){
x=2;
while(x<n&&l+1<=r-1){
MinMax(l+1,r-1,&a,&b); x+=2;
if(a==-1||b==-1) break;
ckmax(ans,a-l,r-b);
l=a; r=b;
}
ckmax(ans,r-l);
return ans;
}//*
B=(r-l-1)/(n-1); c=l;
for(ll i=l+1;i<r;i+=B+1){
MinMax(i,i+B,&a,&b);
if(a!=-1&&c!=-1) ckmax(ans,a-c);
if(b!=-1) c=b;
}
if(c!=-1) ckmax(ans,r-c);//*/
return ans;
}
#ifdef LOCAL_PROJECT
int main(){
cin.tie(0)->sync_with_stdio(0); //fIn("1_03.in");
cin>>T>>n; ANS.resize(n+2); ANS[0]=-1;
fori(1,n+1) cin>>ANS[i];
ANS[n+1]=INF;
cout<<findGap(T,n);
return 0;
}
#endif
/**
(m-n)/(n-1)
1 15
26822012613602297 83016336616322262 240236403235204784 251263501103080046 267418872581278273 283465011506182121 387188614324429897 405999856871910796 621222868183510412 705139383465288123 737738410068055892 825642738416654428 854722383986606367 855077944176184296 908358416490444978
215223011311599616
*/
Compilation message
gap.cpp: In function 'void fIn(std::string)':
gap.cpp:54:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
54 | void fIn(string s){freopen(s.c_str(),"r",stdin);} void fOut(string s){freopen(s.c_str(),"w",stdout);} void fIO(string s){fIn(s+".in"); fOut(s+".out");}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
gap.cpp: In function 'void fOut(std::string)':
gap.cpp:54:78: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
54 | void fIn(string s){freopen(s.c_str(),"r",stdin);} void fOut(string s){freopen(s.c_str(),"w",stdout);} void fIO(string s){fIn(s+".in"); fOut(s+".out");}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
0 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
380 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
2 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
13 ms |
492 KB |
Output is correct |
| 17 |
Correct |
11 ms |
492 KB |
Output is correct |
| 18 |
Correct |
11 ms |
492 KB |
Output is correct |
| 19 |
Correct |
12 ms |
588 KB |
Output is correct |
| 20 |
Correct |
10 ms |
492 KB |
Output is correct |
| 21 |
Correct |
57 ms |
1132 KB |
Output is correct |
| 22 |
Correct |
48 ms |
1260 KB |
Output is correct |
| 23 |
Correct |
45 ms |
1260 KB |
Output is correct |
| 24 |
Correct |
52 ms |
1260 KB |
Output is correct |
| 25 |
Correct |
40 ms |
1132 KB |
Output is correct |
| 26 |
Correct |
51 ms |
1132 KB |
Output is correct |
| 27 |
Correct |
45 ms |
1260 KB |
Output is correct |
| 28 |
Correct |
45 ms |
1132 KB |
Output is correct |
| 29 |
Correct |
50 ms |
1132 KB |
Output is correct |
| 30 |
Correct |
36 ms |
1180 KB |
Output is correct |
| 31 |
Correct |
1 ms |
364 KB |
Output is correct |
| 32 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
0 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
0 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
0 ms |
364 KB |
Output is correct |
| 10 |
Correct |
0 ms |
364 KB |
Output is correct |
| 11 |
Correct |
2 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
364 KB |
Output is correct |
| 15 |
Correct |
1 ms |
364 KB |
Output is correct |
| 16 |
Correct |
17 ms |
492 KB |
Output is correct |
| 17 |
Correct |
18 ms |
668 KB |
Output is correct |
| 18 |
Correct |
15 ms |
492 KB |
Output is correct |
| 19 |
Correct |
17 ms |
492 KB |
Output is correct |
| 20 |
Correct |
8 ms |
492 KB |
Output is correct |
| 21 |
Correct |
62 ms |
1132 KB |
Output is correct |
| 22 |
Correct |
61 ms |
1152 KB |
Output is correct |
| 23 |
Correct |
61 ms |
1132 KB |
Output is correct |
| 24 |
Correct |
63 ms |
1132 KB |
Output is correct |
| 25 |
Correct |
59 ms |
1132 KB |
Output is correct |
| 26 |
Correct |
62 ms |
1184 KB |
Output is correct |
| 27 |
Correct |
61 ms |
1196 KB |
Output is correct |
| 28 |
Correct |
62 ms |
1260 KB |
Output is correct |
| 29 |
Correct |
73 ms |
1132 KB |
Output is correct |
| 30 |
Correct |
36 ms |
1084 KB |
Output is correct |
| 31 |
Correct |
1 ms |
364 KB |
Output is correct |
| 32 |
Correct |
1 ms |
364 KB |
Output is correct |
