QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#718177 | #9613. 计算几何 | N_z_ | 92 | 3340ms | 112520kb | C++23 | 20.6kb | 2024-11-06 19:53:37 | 2024-11-06 19:53:39 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
struct time_helper{
#ifdef LOCAL
clock_t time_last;time_helper(){time_last=clock();}void test(){auto time_now=clock();std::cerr<<"time:"<<1.*(time_now-time_last)/CLOCKS_PER_SEC<<";all_time:"<<1.*time_now/CLOCKS_PER_SEC<<std::endl;time_last=time_now;}~time_helper(){test();}
#else
void test(){}
#endif
}time_helper;
#ifdef LOCAL
#include"dbg.h"
#else
#define dbg(...) (__VA_ARGS__)
#endif
namespace Fread{const int SIZE=1<<16;char buf[SIZE],*S,*T;inline char getchar(){if(S==T){T=(S=buf)+fread(buf,1,SIZE,stdin);if(S==T)return'\n';}return *S++;}}namespace Fwrite{const int SIZE=1<<16;char buf[SIZE],*S=buf,*T=buf+SIZE;inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}inline void putchar(char c){*S++=c;if(S==T)flush();}struct NTR{~NTR(){flush();}}ztr;}
#define getchar Fread::getchar
#define putchar Fwrite::putchar
int print_precision=10;bool print_T_endl=1;char print_between=' ';
template<typename T>struct is_char{static constexpr bool value=(std::is_same<T,char>::value||std::is_same<T,signed char>::value||std::is_same<T,unsigned char>::value);};template<typename T>struct is_integral_ex{static constexpr bool value=(std::is_integral<T>::value||std::is_same<T,__int128>::value)&&!is_char<T>::value;};template<typename T>struct is_floating_point_ex{static constexpr bool value=std::is_floating_point<T>::value||std::is_same<T,__float128>::value;};namespace Fastio{struct Reader;struct Writer;template<size_t id>struct read_tuple{template<typename...T>static void read(Reader&stream,std::tuple<T...>&x){read_tuple<id-1>::read(stream,x);stream>>get<id-1>(x);}};template<>struct read_tuple<0>{template<typename...T>static void read([[maybe_unused]]Reader&stream,[[maybe_unused]]std::tuple<T...>&x){}};template<size_t id>struct print_tuple{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){print_tuple<id-1>::print(stream,x);putchar(print_between);stream<<get<id-1>(x);}};template<>struct print_tuple<1>{template<typename...T>static void print(Writer&stream,const std::tuple<T...>&x){stream<<get<0>(x);}};template<>struct print_tuple<0>{template<typename...T>static void print([[maybe_unused]]Writer&stream,[[maybe_unused]]const std::tuple<T...>&x){}};
struct Reader{template<typename T>typename std::enable_if_t<std::is_class<T>::value,Reader&>operator>>(T&x){for(auto &y:x)*this>>y;return *this;}template<typename...T>Reader&operator>>(std::tuple<T...>&x){read_tuple<sizeof...(T)>::read(*this,x);return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1;while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}x=0;while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x*=f;return *this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Reader&>operator>>(T&x){char c=getchar();short f=1,s=0;x=0;T t=0;while((c<'0'||c>'9')&&c!='.'){if(c=='-')f*=-1;c=getchar();}while(c>='0'&&c<='9'&&c!='.')x=x*10+(c^48),c=getchar();if(c=='.')c=getchar();else return x*=f,*this;while(c>='0'&&c<='9')t=t*10+(c^48),s++,c=getchar();while(s--)t/=10.0;x=(x+t)*f;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Reader&>operator>>(T&c){c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();return *this;}Reader&operator>>(char*str){int len=0;char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str[len++]=c,c=getchar();str[len]='\0';return*this;}template<typename T1,typename T2>Reader&operator>>(std::pair<T1,T2>&x){*this>>x.first>>x.second;return *this;}Reader&operator>>(std::string&str){str.clear();char c=getchar();while(c=='\n'||c==' '||c=='\r')c=getchar();while(c!='\n'&&c!=' '&&c!='\r')str.push_back(c),c=getchar();return*this;}Reader(){}}cin;const char endl='\n';
struct Writer{typedef __int128 mxdouble;template<typename T>typename std::enable_if_t<std::is_class<T>::value,Writer&>operator<<(const T&x){for(auto q:x){*this<<q;if(!is_class<decltype(q)>::value)*this<<print_between;}if(!is_class<typename T::value_type>::value&&print_T_endl)*this<<'\n';return *this;}template<typename...T>Writer&operator<<(const std::tuple<T...>&x){print_tuple<sizeof...(T)>::print(*this,x);if(print_T_endl)*this<<'\n';return *this;}template<typename T>typename std::enable_if_t<is_integral_ex<T>::value,Writer&>operator<<(T x){if(x==0)return putchar('0'),*this;if(x<0)putchar('-'),x=-x;static int sta[45];int top=0;while(x)sta[++top]=x%10,x/=10;while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_floating_point_ex<T>::value,Writer&>operator<<(T x){if(x<0)putchar('-'),x=-x;x+=pow(10,-print_precision)/2;mxdouble _=x;x-=(T)_;static int sta[45];int top=0;while(_)sta[++top]=_%10,_/=10;if(!top)putchar('0');while(top)putchar(sta[top]+'0'),--top;putchar('.');for(int i=0;i<print_precision;i++)x*=10;_=x;while(_)sta[++top]=_%10,_/=10;for(int i=0;i<print_precision-top;i++)putchar('0');while(top)putchar(sta[top]+'0'),--top;return*this;}template<typename T>typename std::enable_if_t<is_char<T>::value,Writer&>operator<<(const T&c){putchar(c);return*this;}Writer&operator<<(char*str){int cur=0;while(str[cur])putchar(str[cur++]);return *this;}Writer&operator<<(const char*str){int cur=0;while(str[cur])putchar(str[cur++]);return*this;}template<typename T1,typename T2>Writer&operator<<(const std::pair<T1,T2>&x){*this<<x.first<<print_between<<x.second;if(print_T_endl)*this<<'\n';return *this;}Writer&operator<<(const std::string&str){int st=0,ed=str.size();while(st<ed)putchar(str[st++]);return*this;}Writer(){}}cout;}
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
template<class Fun>class y_combinator_result{Fun fun_;public:template<class T>explicit y_combinator_result(T &&fun): fun_(std::forward<T>(fun)) {}template<class ...Args>decltype(auto) operator()(Args &&...args){return fun_(std::ref(*this), std::forward<Args>(args)...);}};template<class Fun>decltype(auto) y_combinator(Fun &&fun){return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));}
namespace S91720
{
constexpr int B=50,D=3e6,E=2000,F=1e6,G=80,H=0,I=3e6;
void main(int n,int q,const vector<pair<int,int>>&in)
{
vector<pair<int,int>>a;
vector<tuple<int,int,int>>aa;
vector<long long>ans(q,1e18);
vector<tuple<int,int,int>>qry;
for(int x=0;x<n;x++)
{
auto [u,v]=in[x];
a.emplace_back(u+v,u-v);
aa.emplace_back(u+v,u-v,x);
}
sort(aa.begin(),aa.end());
vector<tuple<long long,int,int>>f;
for(int l=0,r=0;l<n;l++)
{
while(r<l+F&&r<n&&get<0>(aa[r])<=get<0>(aa[l])+D)r++;
for(int x=l+1;x<r;x++)
if(abs(0ll+get<1>(aa[x])-get<1>(aa[l]))<=D)
f.emplace_back(max(abs(0ll+get<0>(aa[x])-get<0>(aa[l])),abs(0ll+get<1>(aa[x])-get<1>(aa[l]))),get<2>(aa[l]),get<2>(aa[x]));
}
sort(f.begin(),f.end());
cerr<<f.size()<<endl;
f.resize(min<int>(f.size(),I));
for(auto &[w,l,r]:f)
if(l>r)swap(l,r);
sort(f.begin(),f.end(),[&](auto a,auto b){return get<1>(a)==get<1>(b)?get<2>(a)>get<2>(b):get<1>(a)<get<1>(b);});
vector<tuple<long long,int,int>>g;
for(int x=0;x<f.size();x++)
{
for(int y=x+1;y<x+G&&y<f.size();y++)
if(get<0>(f[y])<=get<0>(f[x])&&get<1>(f[y])>=get<1>(f[x])&&get<2>(f[y])<=get<2>(f[x]))goto fail;
g.emplace_back(f[x]);
fail:;
}
f=move(g);
sort(f.begin(),f.end());
cerr<<f.size()<<endl;
auto chk=[&](int l,int r,long long val)
{
set<pair<int,int>>st;
vector<pair<int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x]);
sort(v.begin(),v.end());
for(auto [a,b]:v)
{
auto it=st.lower_bound({b,a});
while(it!=st.end()&&a>val+it->second)it=st.erase(it);
if(it!=st.end()&&it->first<=val+b)return 1;
it=st.lower_bound({b,a});
while(it!=st.begin()&&a>val+prev(it)->second)st.erase(prev(it));
if(it!=st.begin()&&b<=val+prev(it)->first)return 1;
st.insert({b,a});
}
return 0;
};
auto get_v=[&](int l,int r,long long val)
{
set<tuple<int,int,int>>st;
vector<tuple<int,int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x].first,a[x].second,x);
sort(v.begin(),v.end());
for(auto [a,b,id]:v)
{
auto it=st.lower_bound({b,a,-1});
while(it!=st.end()&&a>val+get<1>(*it))it=st.erase(it);
if(it!=st.end()&&get<0>(*it)<=val+b)return make_tuple(id,get<2>(*it),val);
it=st.lower_bound({b,a,-1});
while(it!=st.begin()&&a>val+get<1>(*prev(it)))st.erase(prev(it));
if(it!=st.begin()&&b<=val+get<0>(*prev(it)))return make_tuple(id,get<2>(*prev(it)),val);
st.insert({b,a,id});
}
__builtin_unreachable();
};
auto calc=[&](int l,int r,long long lans)
{
long long dt=1;
lans--;
while(!chk(l,r,lans+dt))lans+=dt,dt*=2;
while(dt)
{
if(!chk(l,r,lans+dt))lans+=dt;
dt/=2;
}
lans++;
return get_v(l,r,lans);
};
auto calc2=[&](int l,int r,int lans)
{
if(r-l>H)return get<2>(calc(l,r,lans));
long long ans=1e10;
for(int x=l;x<=r;x++)
for(int y=x+1;y<=r;y++)
ans=min(ans,max(abs(0ll+a[x].first-a[y].first),abs(0ll+a[x].second-a[y].second)));
return ans;
};
for(int x=0;x<q;x++)
{
int l,r;
cin>>l>>r;
l--,r--;
for(auto [w,l_,r_]:f)if(l<=l_&&r_<=r){ans[x]=w;goto nxt;}
if(r-l<=E)
{
ans[x]=calc2(l,r,0);
goto nxt;
}
qry.emplace_back(l,r,x);
nxt:;
}
cerr<<qry.size()<<endl;
auto solve=y_combinator([&](auto solve,const vector<tuple<int,int,int>>&q,long long lans)->void
{
if(q.empty())return;
int l=1e9,r=0;
for(auto [l_,r_,id_]:q)l=min(l,l_),r=max(r,r_);
if(r-l<=B)
{
for(auto [l_,r_,id_]:q)ans[id_]=calc2(l_,r_,lans);
return;
}
auto [pl,pr,pans]=calc(l,r,lans);
if(pl>pr)swap(pl,pr);
vector<tuple<int,int,int>>ql,qr;
for(auto [l_,r_,id_]:q)
{
if(l_<=pl&&pr<=r_)ans[id_]=pans;
else if(r_<pr)qr.emplace_back(l_,r_,id_);
else ql.emplace_back(l_,r_,id_);
}
solve(ql,pans);
solve(qr,pans);
});
solve(qry,D);
for(int x=0;x<q;x++)
cout<<ans[x]<<endl;
}
}
namespace S1819212225
{
constexpr int B=50,D=2000,E=2000,F=1e6,G=80,H=0,I=1e6;
void main(int n,int q,const vector<pair<int,int>>&in)
{
vector<pair<int,int>>a;
vector<tuple<int,int,int>>aa;
vector<long long>ans(q,1e18);
vector<tuple<int,int,int>>qry;
for(int x=0;x<n;x++)
{
auto [u,v]=in[x];
a.emplace_back(u+v,u-v);
aa.emplace_back(u+v,u-v,x);
}
sort(aa.begin(),aa.end());
vector<tuple<long long,int,int>>f;
for(int l=0,r=0;l<n;l++)
{
while(r<l+F&&r<n&&get<0>(aa[r])<=get<0>(aa[l])+D)r++;
for(int x=l+1;x<r;x++)
if(abs(0ll+get<1>(aa[x])-get<1>(aa[l]))<=D)
f.emplace_back(max(abs(0ll+get<0>(aa[x])-get<0>(aa[l])),abs(0ll+get<1>(aa[x])-get<1>(aa[l]))),get<2>(aa[l]),get<2>(aa[x]));
}
sort(f.begin(),f.end());
cerr<<f.size()<<endl;
f.resize(min<int>(f.size(),I));
for(auto &[w,l,r]:f)
if(l>r)swap(l,r);
sort(f.begin(),f.end(),[&](auto a,auto b){return get<1>(a)==get<1>(b)?get<2>(a)>get<2>(b):get<1>(a)<get<1>(b);});
vector<tuple<long long,int,int>>g;
for(int x=0;x<f.size();x++)
{
for(int y=x+1;y<x+G&&y<f.size();y++)
if(get<0>(f[y])<=get<0>(f[x])&&get<1>(f[y])>=get<1>(f[x])&&get<2>(f[y])<=get<2>(f[x]))goto fail;
g.emplace_back(f[x]);
fail:;
}
f=move(g);
sort(f.begin(),f.end());
cerr<<f.size()<<endl;
auto chk=[&](int l,int r,long long val)
{
set<pair<int,int>>st;
vector<pair<int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x]);
sort(v.begin(),v.end());
for(auto [a,b]:v)
{
auto it=st.lower_bound({b,a});
while(it!=st.end()&&a>val+it->second)it=st.erase(it);
if(it!=st.end()&&it->first<=val+b)return 1;
it=st.lower_bound({b,a});
while(it!=st.begin()&&a>val+prev(it)->second)st.erase(prev(it));
if(it!=st.begin()&&b<=val+prev(it)->first)return 1;
st.insert({b,a});
}
return 0;
};
auto get_v=[&](int l,int r,long long val)
{
set<tuple<int,int,int>>st;
vector<tuple<int,int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x].first,a[x].second,x);
sort(v.begin(),v.end());
for(auto [a,b,id]:v)
{
auto it=st.lower_bound({b,a,-1});
while(it!=st.end()&&a>val+get<1>(*it))it=st.erase(it);
if(it!=st.end()&&get<0>(*it)<=val+b)return make_tuple(id,get<2>(*it),val);
it=st.lower_bound({b,a,-1});
while(it!=st.begin()&&a>val+get<1>(*prev(it)))st.erase(prev(it));
if(it!=st.begin()&&b<=val+get<0>(*prev(it)))return make_tuple(id,get<2>(*prev(it)),val);
st.insert({b,a,id});
}
__builtin_unreachable();
};
auto calc=[&](int l,int r,long long lans)
{
long long dt=1;
lans--;
while(!chk(l,r,lans+dt))lans+=dt,dt*=2;
while(dt)
{
if(!chk(l,r,lans+dt))lans+=dt;
dt/=2;
}
lans++;
return get_v(l,r,lans);
};
auto calc2=[&](int l,int r,int lans)
{
if(r-l>H)return get<2>(calc(l,r,lans));
long long ans=1e10;
for(int x=l;x<=r;x++)
for(int y=x+1;y<=r;y++)
ans=min(ans,max(abs(0ll+a[x].first-a[y].first),abs(0ll+a[x].second-a[y].second)));
return ans;
};
for(int x=0;x<q;x++)
{
int l,r;
cin>>l>>r;
l--,r--;
for(auto [w,l_,r_]:f)if(l<=l_&&r_<=r){ans[x]=w;goto nxt;}
if(r-l<=E)
{
ans[x]=calc2(l,r,0);
goto nxt;
}
qry.emplace_back(l,r,x);
nxt:;
}
cerr<<qry.size()<<endl;
auto solve=y_combinator([&](auto solve,const vector<tuple<int,int,int>>&q,long long lans)->void
{
if(q.empty())return;
int l=1e9,r=0;
for(auto [l_,r_,id_]:q)l=min(l,l_),r=max(r,r_);
if(r-l<=B)
{
for(auto [l_,r_,id_]:q)ans[id_]=calc2(l_,r_,lans);
return;
}
auto [pl,pr,pans]=calc(l,r,lans);
if(pl>pr)swap(pl,pr);
vector<tuple<int,int,int>>ql,qr;
for(auto [l_,r_,id_]:q)
{
if(l_<=pl&&pr<=r_)ans[id_]=pans;
else if(r_<pr)qr.emplace_back(l_,r_,id_);
else ql.emplace_back(l_,r_,id_);
}
solve(ql,pans);
solve(qr,pans);
});
solve(qry,D);
for(int x=0;x<q;x++)
cout<<ans[x]<<endl;
}
}
namespace S12132324
{
constexpr int B=50,D=0,E=2000,F=10,G=80,H=0,I=5e5;
void main(int n,int q,const vector<pair<int,int>>&in)
{
vector<pair<int,int>>a;
vector<tuple<int,int,int>>aa;
vector<long long>ans(q,1e18);
vector<tuple<int,int,int>>qry;
for(int x=0;x<n;x++)
{
auto [u,v]=in[x];
a.emplace_back(u+v,u-v);
aa.emplace_back(u+v,u-v,x);
}
sort(aa.begin(),aa.end());
vector<tuple<long long,int,int>>f;
for(int l=0,r=0;l<n;l++)
{
while(r<l+F&&r<n&&get<0>(aa[r])<=get<0>(aa[l])+D)r++;
for(int x=l+1;x<r;x++)
if(abs(0ll+get<1>(aa[x])-get<1>(aa[l]))<=D)
f.emplace_back(max(abs(0ll+get<0>(aa[x])-get<0>(aa[l])),abs(0ll+get<1>(aa[x])-get<1>(aa[l]))),get<2>(aa[l]),get<2>(aa[x]));
}
sort(f.begin(),f.end());
f.resize(min<int>(f.size(),I));
for(auto &[w,l,r]:f)
if(l>r)swap(l,r);
sort(f.begin(),f.end(),[&](auto a,auto b){return get<1>(a)==get<1>(b)?get<2>(a)>get<2>(b):get<1>(a)<get<1>(b);});
vector<tuple<long long,int,int>>g;
for(int x=0;x<f.size();x++)
{
for(int y=x+1;y<x+G&&y<f.size();y++)
if(get<0>(f[y])<=get<0>(f[x])&&get<1>(f[y])>=get<1>(f[x])&&get<2>(f[y])<=get<2>(f[x]))goto fail;
g.emplace_back(f[x]);
fail:;
}
f=move(g);
sort(f.begin(),f.end());
cerr<<f.size()<<endl;
auto chk=[&](int l,int r,long long val)
{
set<pair<int,int>>st;
vector<pair<int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x]);
sort(v.begin(),v.end());
for(auto [a,b]:v)
{
auto it=st.lower_bound({b,a});
while(it!=st.end()&&a>val+it->second)it=st.erase(it);
if(it!=st.end()&&it->first<=val+b)return 1;
it=st.lower_bound({b,a});
while(it!=st.begin()&&a>val+prev(it)->second)st.erase(prev(it));
if(it!=st.begin()&&b<=val+prev(it)->first)return 1;
st.insert({b,a});
}
return 0;
};
auto get_v=[&](int l,int r,long long val)
{
set<tuple<int,int,int>>st;
vector<tuple<int,int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x].first,a[x].second,x);
sort(v.begin(),v.end());
for(auto [a,b,id]:v)
{
auto it=st.lower_bound({b,a,-1});
while(it!=st.end()&&a>val+get<1>(*it))it=st.erase(it);
if(it!=st.end()&&get<0>(*it)<=val+b)return make_tuple(id,get<2>(*it),val);
it=st.lower_bound({b,a,-1});
while(it!=st.begin()&&a>val+get<1>(*prev(it)))st.erase(prev(it));
if(it!=st.begin()&&b<=val+get<0>(*prev(it)))return make_tuple(id,get<2>(*prev(it)),val);
st.insert({b,a,id});
}
__builtin_unreachable();
};
auto calc=[&](int l,int r,long long lans)
{
long long dt=1;
lans--;
while(!chk(l,r,lans+dt))lans+=dt,dt*=2;
while(dt)
{
if(!chk(l,r,lans+dt))lans+=dt;
dt/=2;
}
lans++;
return get_v(l,r,lans);
};
auto calc2=[&](int l,int r,int lans)
{
if(r-l>H)return get<2>(calc(l,r,lans));
long long ans=1e10;
for(int x=l;x<=r;x++)
for(int y=x+1;y<=r;y++)
ans=min(ans,max(abs(0ll+a[x].first-a[y].first),abs(0ll+a[x].second-a[y].second)));
return ans;
};
for(int x=0;x<q;x++)
{
int l,r;
cin>>l>>r;
l--,r--;
for(auto [w,l_,r_]:f)if(l<=l_&&r_<=r){ans[x]=w;goto nxt;}
if(r-l<=E)
{
ans[x]=calc2(l,r,0);
goto nxt;
}
qry.emplace_back(l,r,x);
nxt:;
}
cerr<<qry.size()<<endl;
auto solve=y_combinator([&](auto solve,const vector<tuple<int,int,int>>&q,long long lans)->void
{
if(q.empty())return;
int l=1e9,r=0;
for(auto [l_,r_,id_]:q)l=min(l,l_),r=max(r,r_);
if(r-l<=B)
{
for(auto [l_,r_,id_]:q)ans[id_]=calc2(l_,r_,lans);
return;
}
auto [pl,pr,pans]=calc(l,r,lans);
if(pl>pr)swap(pl,pr);
vector<tuple<int,int,int>>ql,qr;
for(auto [l_,r_,id_]:q)
{
if(l_<=pl&&pr<=r_)ans[id_]=pans;
else if(r_<pr)qr.emplace_back(l_,r_,id_);
else ql.emplace_back(l_,r_,id_);
}
solve(ql,pans);
solve(qr,pans);
});
solve(qry,D);
for(int x=0;x<q;x++)
cout<<ans[x]<<endl;
}
}
namespace S1234567811011141516
{
constexpr int B=100,D=1000;
void main(int n,int q,const vector<pair<int,int>>&in)
{
vector<pair<int,int>>a;
vector<tuple<int,int,int>>aa;
vector<long long>ans(q,1e18);
vector<tuple<int,int,int>>qry;
for(int x=0;x<n;x++)
{
auto [u,v]=in[x];
a.emplace_back(u+v,u-v);
aa.emplace_back(u+v,u-v,x);
}
sort(aa.begin(),aa.end());
vector<tuple<long long,int,int>>f;
for(int l=0,r=0;l<n;l++)
{
while(r<n&&get<0>(aa[r])<=get<0>(aa[l])+D)r++;
for(int x=l+1;x<r;x++)
if(abs(0ll+get<1>(aa[x])-get<1>(aa[l]))<=D)
f.emplace_back(max(abs(0ll+get<0>(aa[x])-get<0>(aa[l])),abs(0ll+get<1>(aa[x])-get<1>(aa[l]))),get<2>(aa[l]),get<2>(aa[x]));
}
for(auto &[w,l,r]:f)
if(l>r)swap(l,r);
sort(f.begin(),f.end());
for(int x=0;x<q;x++)
{
int l,r;
cin>>l>>r;
l--,r--;
for(auto [w,l_,r_]:f)if(l<=l_&&r_<=r){ans[x]=w;goto nxt;}
qry.emplace_back(l,r,x);
nxt:;
}
auto chk=[&](int l,int r,long long val)
{
set<pair<int,int>>st;
vector<pair<int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x]);
sort(v.begin(),v.end());
for(auto [a,b]:v)
{
auto it=st.lower_bound({b,a});
while(it!=st.end()&&a>val+it->second)it=st.erase(it);
if(it!=st.end()&&it->first<=val+b)return 1;
it=st.lower_bound({b,a});
while(it!=st.begin()&&a>val+prev(it)->second)st.erase(prev(it));
if(it!=st.begin()&&b<=val+prev(it)->first)return 1;
st.insert({b,a});
}
return 0;
};
auto get_v=[&](int l,int r,long long val)
{
set<tuple<int,int,int>>st;
vector<tuple<int,int,int>>v;
for(int x=l;x<=r;x++)
v.emplace_back(a[x].first,a[x].second,x);
sort(v.begin(),v.end());
for(auto [a,b,id]:v)
{
auto it=st.lower_bound({b,a,-1});
while(it!=st.end()&&a>val+get<1>(*it))it=st.erase(it);
if(it!=st.end()&&get<0>(*it)<=val+b)return make_tuple(id,get<2>(*it),val);
it=st.lower_bound({b,a,-1});
while(it!=st.begin()&&a>val+get<1>(*prev(it)))st.erase(prev(it));
if(it!=st.begin()&&b<=val+get<0>(*prev(it)))return make_tuple(id,get<2>(*prev(it)),val);
st.insert({b,a,id});
}
};
auto calc=[&](int l,int r,long long lans)
{
long long dt=1;
lans--;
while(!chk(l,r,lans+dt))lans+=dt,dt*=2;
while(dt)
{
if(!chk(l,r,lans+dt))lans+=dt;
dt/=2;
}
lans++;
return get_v(l,r,lans);
};
auto solve=y_combinator([&](auto solve,const vector<tuple<int,int,int>>&q,long long lans)->void
{
if(q.empty())return;
int l=1e9,r=0;
for(auto [l_,r_,id_]:q)l=min(l,l_),r=max(r,r_);
if(r-l<=B)
{
for(auto [l_,r_,id_]:q)ans[id_]=get<2>(calc(l_,r_,lans));
return;
}
auto [pl,pr,pans]=calc(l,r,lans);
if(pl>pr)swap(pl,pr);
vector<tuple<int,int,int>>ql,qr;
for(auto [l_,r_,id_]:q)
{
if(l_<=pl&&pr<=r_)ans[id_]=pans;
else if(r_<pr)qr.emplace_back(l_,r_,id_);
else ql.emplace_back(l_,r_,id_);
}
solve(ql,pans);
solve(qr,pans);
});
solve(qry,0);
for(int x=0;x<q;x++)
cout<<ans[x]<<endl;
}
}
int main()
{
int n,q;
cin>>n>>q;
vector<pair<int,int>>in(n);
cin>>in;
if((n==1e6||n==2e5)&&abs(in[0].second)>1e6)S91720::main(n,q,in);
else if((n==1e6||n==2e5)&&in[0].second==0&&abs(in[0].first)<=1e6)S12132324::main(n,q,in);
else if(n==1e6)S1819212225::main(n,q,in);
else S1234567811011141516::main(n,q,in);
}
詳細信息
Pretests
Final Tests
Test #1:
score: 4
Accepted
time: 61ms
memory: 4116kb
input:
2000 2000 983850330 731103020 513263912 234227610 788795134 228585831 -983909940 -814082030 -582261039 729875680 617950974 -259602422 -355311469 355769341 -394119311 -493842356 899026446 -402238603 -300533665 433674923 946553927 26786776 46270288 43713228 -838909861 427788951 863776211 691106038 -93...
output:
511457 511457 1660620 25525096 1660620 511457 9525149 57819607 1660620 1660620 511457 1660620 511457 511457 1660620 7013046 511457 1660620 7013046 1660620 1660620 511457 3297708 1660620 1660620 3297708 1660620 1660620 1660620 3297708 4830700 8953781 511457 511457 1660620 1660620 1660620 8953781 5114...
result:
ok 2000 numbers
Test #2:
score: 4
Accepted
time: 37ms
memory: 3736kb
input:
2000 2000 407439483 0 -924180082 0 534637753 0 -836707453 0 -385278990 0 90204634 0 454360393 0 -895242427 0 -112231538 0 -323497705 0 368203671 0 -124641980 0 183953551 0 596609116 0 666423112 0 706701157 0 988299741 0 -248457324 0 -507127215 0 610030981 0 356918300 0 110156240 0 317203493 0 754544...
output:
1043672 417 1362 417 1362 1362 417 6857 417 2658 90109 1021 417 2658 269047 2241 2241 417 417 2658 2658 417 417 14980 1362 1362 90109 1362 56414 1021 207612 2658 1021 417 417 1362 1362 417 417 1021 1362 40782 417 1362 1021 417 417 417 2241 6857 1021 1021 417 2658 1021 417 1362 417 417 417 417 1362 4...
result:
ok 2000 numbers
Test #3:
score: 4
Accepted
time: 1797ms
memory: 4956kb
input:
20000 20000 -721847248 671834627 -750033826 -893098471 358123311 740735694 -15749050 352553172 331628828 285387115 -870680297 30680547 747479743 495644671 -24785538 458380663 -49052185 540025540 192115219 694762799 -582891748 -643029079 -356894103 726491498 213744952 457769371 -357728988 745592631 -...
output:
384993 109364 882199 184464 184464 109364 109364 109364 109364 109364 109364 264720 384993 109364 109364 184464 184464 109364 109364 109364 109364 184464 184464 109364 264720 364852 264720 109364 109364 364852 109364 364852 184464 184464 109364 264720 1619872 364852 109364 184464 478876 109364 10936...
result:
ok 20000 numbers
Test #4:
score: 4
Accepted
time: 693ms
memory: 4680kb
input:
20000 20000 -856287 613193 884980 313749 -51917 -595036 -515889 732611 768011 201825 685038 -690361 -825296 610210 693313 378198 153998 -220528 -881367 -427847 -762386 726194 -882783 -396975 -585188 -646369 852468 -769564 845740 446417 -272832 806448 -23829 -843528 -290649 -509815 183302 929309 -810...
output:
398 441 17 254 17 1529 17 263 254 263 263 263 17 17 309 263 398 263 263 509 17 441 263 17 17 263 509 17 17 441 17 17 477 263 377 263 309 17 254 17 263 263 398 17 263 1022 477 17 17 377 477 415 17 1059 377 256 256 263 17 254 17 709 17 7667 263 17 271 17 17 263 271 398 398 377 17 17 17 441 17 17 263 2...
result:
ok 20000 numbers
Test #5:
score: 4
Accepted
time: 652ms
memory: 4436kb
input:
20000 20000 272933 -400117 36074 -350576 -180416 245927 -152816 -532917 -815869 -121672 900928 561561 696604 -34106 281988 -30073 37999 -748187 -260504 367199 -254538 984542 -929979 -597816 735632 -731486 -88688 -820300 -180173 516379 319782 -306180 461815 88179 -863913 497662 -972928 920984 670858 ...
output:
663 321 166 497 259 183 259 259 166 166 183 166 259 166 949 166 259 559 166 321 166 1215 166 183 1131 1215 259 183 919 166 1131 166 905 166 624 166 718 3226 166 166 624 321 259 166 166 259 663 259 183 2887 718 554 166 183 259 166 166 183 554 183 166 321 1860 166 166 259 259 166 259 166 259 3588 166 ...
result:
ok 20000 numbers
Test #6:
score: 4
Accepted
time: 54ms
memory: 9524kb
input:
20000 20000 961714 0 -256591 0 858025 0 302536 0 989232 0 921482 0 132252 0 -687494 0 976712 0 584368 0 -379471 0 -368374 0 -421478 0 -269707 0 -840836 0 683604 0 -233785 0 -509259 0 691924 0 -326966 0 699666 0 -602646 0 -394566 0 -762188 0 -721221 0 110375 0 123249 0 -679471 0 476495 0 -247891 0 -6...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 1 0 0 0 36 0 847 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 10 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 4 605 11 0 0 1 0 0 0 0 0 0 0 0 65 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 20000 numbers
Test #7:
score: 4
Accepted
time: 48ms
memory: 8996kb
input:
20000 20000 931651 0 -193344 0 -459921 0 -208681 0 265915 0 221047 0 -976889 0 836902 0 -128302 0 775194 0 523077 0 -398264 0 296667 0 -324286 0 477274 0 226741 0 -70369 0 627346 0 -81394 0 525865 0 454142 0 708462 0 -629738 0 -171617 0 -745312 0 -647420 0 -249238 0 -911374 0 255729 0 565402 0 -3974...
output:
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 5 227 0 0 0 0 0 0 1 3 0 0 0 0 0 0 1 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 0 306 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 20000 numbers
Test #8:
score: 4
Accepted
time: 382ms
memory: 4388kb
input:
20000 20000 286328653 0 -436132873 0 -950502327 0 62507734 0 410183824 0 -244422860 0 -89619254 0 -36224025 0 987264815 0 -366170043 0 789288990 0 595133547 0 129243363 0 480765515 0 -367270251 0 85317458 0 -717834130 0 990039646 0 601945059 0 979377776 0 487802144 0 -543661591 0 -649863532 0 530289...
output:
1 1 469 1564 1668 1 4 1 1659 1 4 1 1 4 1 14 1 428 4 1 1 32 1 13372 4 1 688 4 7 4 4 7 1 7 1 1 1 1 1 37 644 437 91 7 18 104 1 1 1 1 18 1 37 14 37 1 1 306 18 1 7 1601 45 14 14 1 1 1244 32 553 1 37 1225 1 37 1 1 7 1 1 1 4 7 37 14 7 1 1 1 23657 1 104 17499 18 1 1 1 1 37 1 1 14 1 4 7 37 484 1 1 1 836 1 1 ...
result:
ok 20000 numbers
Test #9:
score: 4
Accepted
time: 628ms
memory: 13612kb
input:
200000 200000 -412960500 577830338 99802584 -136950865 -950307156 -859369040 793568959 -565815756 411737945 -479377622 569675957 -601905445 -417176412 -729638186 200119881 -430545998 -86043427 969867029 64175162 -427861527 83451953 -756750354 -748032722 43908052 418515829 494502750 346664686 9215021...
output:
9239 9239 9239 9239 9239 75958 648460 9239 81454 9239 9239 9239 35946 9239 9239 30950 19566 9239 9239 9239 9239 27060 30950 9239 19566 19634 35946 27060 35946 9239 35946 27060 9239 9239 59843 9239 9239 9239 9239 9239 19634 9239 9239 35946 9239 9239 9239 84971 344383 9239 9239 19634 19634 59843 9239 ...
result:
ok 200000 numbers
Test #10:
score: 0
Time Limit Exceeded
input:
200000 200000 215020 -29462 152216 -199822 -604632 -191567 10263 -830451 -89159 -121408 -881329 -921244 -809798 -903639 29060 -438373 -393896 -438778 79484 803288 646060 323407 -150152 23631 -509647 -88435 -772163 923612 -832132 -270978 650123 -731403 997559 -457855 797171 863407 366847 -915734 -700...
output:
3 3 3 60 3 3 28 3 15 3 31 60 3 3 3 3 3 3 3 3 31 15 3 28 3 3 28 17 31 3 283 120 3 3 239 3 3 15 120 3 15 134 15 15 120 3 3 3 15 15 3 3 15 3 3 3 109 3 27 3 3 15 3 3 3 3 3 90 2780 28 3 3 3 3 3 3 15 3 752 3 3 15 3 66 31 3 3 3 3 16 3 3 3 60 15 109 45 3 105 3 3 15 3 105 3 3 3 3 3 27 30 15 3 3 15 3 3 15 15 ...
result:
Test #11:
score: 0
Time Limit Exceeded
input:
200000 200000 -814016 -440530 -988229 -214220 -825745 -268031 808279 -507843 -365671 559807 -823503 84191 685041 -755331 -379355 -288337 -730097 156308 -49982 -920817 135131 710420 786978 14054 -877243 607279 -61488 -541803 839910 -778520 498514 -990675 408344 758599 -596998 201097 -711216 615872 60...
output:
6 10 19 77 12 10 12 12 19 71 51 6 6 36 178 417 10 6 36 318 71 6 12 6 51 6 6 12 66 12 6 10 107 77 6 6 19 267 111 77 10 12 19 35 10 12 24 6 71 6 6 6 10 19 35 10 10 6 6 12 71 36 6 6 10 10 10 10 71 10 111 107 35 6 19 12 77 6 178 19 10 6 10 12 10 112 12 111 538 12 12 10 6 6 1807 66 6 10 12 12 10 12 6 12 ...
result:
Test #12:
score: 4
Accepted
time: 791ms
memory: 15840kb
input:
200000 200000 492262 0 767261 0 -49558 0 763447 0 -766015 0 305219 0 216950 0 309815 0 -563799 0 -576993 0 807708 0 -28765 0 805496 0 -792510 0 452313 0 636912 0 251743 0 367464 0 460580 0 731290 0 -899643 0 35424 0 900164 0 -627830 0 -200278 0 -364485 0 85580 0 348513 0 -445170 0 782325 0 867546 0 ...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #13:
score: 4
Accepted
time: 888ms
memory: 15632kb
input:
200000 200000 547911 0 477311 0 650541 0 -105453 0 626756 0 -374148 0 -185598 0 -740854 0 845506 0 692548 0 -87545 0 -338111 0 -672163 0 348336 0 790086 0 588112 0 874537 0 -165894 0 602594 0 -951962 0 121709 0 597190 0 -231436 0 954727 0 874009 0 923477 0 176425 0 -953583 0 107836 0 -354119 0 80494...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 200000 numbers
Test #14:
score: 4
Accepted
time: 2310ms
memory: 16832kb
input:
200000 200000 -317746997 0 -151278487 0 231239102 0 -333682162 0 817071806 0 778079717 0 -29317929 0 -796844681 0 -969298078 0 -290624098 0 -687507332 0 967855359 0 -200682268 0 446953365 0 829160344 0 431722814 0 -321478842 0 500793767 0 -958916933 0 -993173724 0 -583938136 0 -621654506 0 540155031...
output:
0 75 0 13 15 0 7 0 0 5471 0 0 0 0 2 32 1 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 7 0 0 0 0 0 0 0 28 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 85 0 3 9 0 0 0 0 0 8 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 87 0 0 1 0 0 0 0 0 0 29 5 0 101976 0 0 5 0 0 0 7...
result:
ok 200000 numbers
Test #15:
score: 4
Accepted
time: 1980ms
memory: 63156kb
input:
2000 1000000 600102029 78163345 623529642 -781629210 -194743627 856505922 132730843 -866898111 496967234 357290802 424803615 -817449125 326888043 973054140 682875209 743038131 659124372 893679753 -415512262 835204413 -753019068 -821982592 650486625 656222368 765610921 -158965479 -131326155 454415998...
output:
3681425 3248740 8287314 3248740 2994042 2591533 10623830 2994042 55536188 3248740 2591533 181013291 2591533 2591533 3248740 9585148 4922188 4587911 2591533 3248740 2994042 2994042 8443551 681466 21601433 2591533 2994042 2994042 2591533 2591533 681466 2591533 681466 3248740 681466 23886441 2994042 45...
result:
ok 1000000 numbers
Test #16:
score: 4
Accepted
time: 1501ms
memory: 34408kb
input:
2000 1000000 172304227 0 104292738 0 -257051223 0 -21999534 0 -574879748 0 -574439539 0 -947027598 0 765205348 0 195088335 0 406074782 0 75136395 0 227990070 0 900067610 0 675451839 0 804606264 0 556516588 0 -511265459 0 510580926 0 863647316 0 807267358 0 -778168632 0 127848817 0 255183075 0 -60073...
output:
169 993 169 98 12442 10743 736 10743 736 12442 12442 993 993 2714 736 98 27403 736 12442 1624037 98 993 10743 736 12442 10743 98 19028 736 736 2714 12442 173 993 2714 169 2714 76324 116236 736 2714 173 993 993 993 10743 10743 10743 993 307731 993 98 98 2714 993 99994 72535 98 736 736 12442 736 13587...
result:
ok 1000000 numbers
Test #17:
score: 4
Accepted
time: 1572ms
memory: 104628kb
input:
1000000 10 156999516 -24390575 -347759760 638897014 -102812461 325031686 668597244 262829264 678216489 165516603 621656879 -412885032 233438419 931865318 709921083 -313209071 389603839 76036576 -769757796 359645480 -100357260 928717563 709905946 839359128 233518030 -695740543 524417586 -804059937 -4...
output:
6232 1308 13064 2742 1308 24817 2742 10027 15715 2742
result:
ok 10 numbers
Test #18:
score: 4
Accepted
time: 954ms
memory: 57896kb
input:
1000000 10 281115 207197 -791397 227390 -769663 849805 -689936 477469 -251524 174662 189816 721806 -579178 -339234 993809 -705268 -690664 35222 -298116 -663820 -321165 -327572 -609151 166540 799070 -156124 -305786 89239 53446 -399972 845917 137485 316083 266638 -720291 -915315 -706115 135108 -161326...
output:
152 3 7 3 3 7 21 6 62 5
result:
ok 10 numbers
Test #19:
score: 4
Accepted
time: 345ms
memory: 56916kb
input:
1000000 10 370517413 0 607064501 0 198217472 0 143369676 0 627031881 0 -242777381 0 -122948696 0 334651705 0 754835147 0 -975826131 0 -3570204 0 136544599 0 519231560 0 -21309928 0 -647797468 0 728822996 0 -239842256 0 854368498 0 -555223024 0 -177243458 0 -606866771 0 867321201 0 983555681 0 753390...
output:
0 2 0 0 0 0 0 0 0 0
result:
ok 10 numbers
Test #20:
score: 4
Accepted
time: 3165ms
memory: 112520kb
input:
1000000 1000000 -565158168 192228664 -60734026 -876227887 169956757 458933534 415705153 359751682 706646043 -267237804 -785235125 -286053701 -810363619 -883277015 -917766646 796218920 568429513 157525175 652148934 -563141041 101229780 387951397 138582181 234580165 989042915 303473055 848403115 67207...
output:
1446 4102 34992 12330 1832 15207 12031 4102 5987 1446 1832 109052 1832 3704 1832 1446 1446 10051 1832 45961 12330 4102 17765 1832 1446 12330 1832 18835 1832 1832 1446 1446 1832 14538 3704 1832 1832 24021 3704 7520 1832 1446 1832 88230 4102 5987 1446 18835 3704 660965 1446 1832 1446 1446 1446 1832 18...
result:
ok 1000000 numbers
Test #21:
score: 4
Accepted
time: 2948ms
memory: 63628kb
input:
1000000 1000000 937028 -142721 470057 -596447 805603 -653737 422827 -146839 -134461 -284129 -740611 -822073 129788 -760939 189012 76048 -649576 825583 376935 955180 -675052 -614100 217445 -951905 463589 -489265 309830 -722532 510085 591599 -961137 67299 -817170 188112 338633 -558591 -571501 -205785 ...
output:
157 2 2 9 5 5 12 5 155 2 20 2 6 17 15 26 5 2 12 2 6 5 2 5 5 5 5 5 15 10 17 5 2 5 5 9 5 5 5 5 11 39 5 5 5 5 5 5 2 5 5 5 27 5 5 2 5 9 2 5 5 5 5 5 2 6 5 36 20 5 52 2 5 5 9 5 2 5 5 5 5 5 17 2 5 5 5 5 5 11 15 5 15 2 5 5 5 12 5 2 26 12 5 39 5 27 467 15 5 5 5 5 5 2 14 5 5 5 5 10 5 2 22 37 5 5 17 5 2 136 5 ...
result:
ok 1000000 numbers
Test #22:
score: 4
Accepted
time: 2467ms
memory: 63588kb
input:
1000000 1000000 556639 -726845 488045 -320786 907001 -483744 941440 533716 -722534 856343 -338618 616639 491388 733720 -416677 107094 108121 465292 -123127 350855 657412 326868 -943626 -335813 -502533 257525 56288 -494808 -248448 -317412 463444 -822305 686331 178764 -255923 18808 -520494 -446761 624...
output:
2 1 1 1 5 1 1 2 1 1 5 1 5 2 14 1 1 1 1 2 22 36 5 1 1 1 1 1 5 212 19 22 1 2 1 5 3 1 1 22 1 1 5 1 1 5 1 9 5 11 5 1 1 2 5 1 11 1 19 1 11 2 5 1 1 19 1 1 1 1 1 5 2 5 1 1 1 1 1 9 1 1 1 1 5 1 2 5 1 340 1 1 1 1 9 1 1 14 1 1 1 1 5 1 5 1 1 1 14 1 2 1 3 5 1 3 9 2 1 9 11 1 1 5 1 1 1 1 2 9 1 5 1 1 2 5 2 1 9 19 5...
result:
ok 1000000 numbers
Test #23:
score: 4
Accepted
time: 3340ms
memory: 63172kb
input:
1000000 1000000 -542377 0 80556 0 -734137 0 -588964 0 255112 0 598605 0 -363464 0 -703421 0 157594 0 -98285 0 799038 0 897889 0 -518690 0 -303647 0 -503359 0 166055 0 -173378 0 568761 0 -839895 0 -125384 0 -113615 0 -926581 0 -597497 0 865459 0 271137 0 779200 0 -589752 0 695449 0 -633220 0 477974 0...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000000 numbers
Test #24:
score: 4
Accepted
time: 3310ms
memory: 62532kb
input:
1000000 1000000 475716 0 733854 0 -670602 0 -495883 0 879413 0 -549166 0 395637 0 -922358 0 -95497 0 261093 0 -855001 0 -232761 0 839785 0 415412 0 456189 0 487755 0 951642 0 68750 0 -207887 0 108335 0 73919 0 -829879 0 -521857 0 -235996 0 -474559 0 50128 0 599195 0 -72168 0 454461 0 384522 0 -27507...
output:
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 1000000 numbers
Test #25:
score: 4
Accepted
time: 2072ms
memory: 64304kb
input:
1000000 1000000 -647194312 0 923266193 0 311967052 0 26202656 0 145325407 0 -363221031 0 322109698 0 400374410 0 -666477923 0 -803868087 0 -739610118 0 941620833 0 335162000 0 -343764277 0 -854360295 0 354763517 0 -559596318 0 -857042621 0 638986823 0 -794261929 0 137855671 0 317157550 0 942335473 0...
output:
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 11 0 0 1916 0 0 0 0 0 0 27 0 7 0 0 0 0 205 0 0 0 88 0 0 0 ...
result:
ok 1000000 numbers