QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#46515 | #3581. Ancient Towers | pechpo | AC ✓ | 6039ms | 4068kb | C++20 | 19.7kb | 2022-08-29 22:39:42 | 2022-08-29 22:39:43 |
Judging History
answer
#include <set>
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
//acos返回0~pi,asin返回-pi/2~pi/2。axx系列精度不好,慎用
namespace geo_2d{
const double INF=1e18, PI=3.14159265358979323846, eps=1e-9;
struct V{ //向量及其运算是几何基础,点也可以用向量表示
LL x, y;
V():x(0),y(0){}
V(const V &a){ *this=a; }
V(const LL &a, const LL &b):x(a),y(b){}
void read(){ scanf("%lld%lld", &x, &y); }
void prLL(){ printf("%lld %lld\n", x, y); }
}O, corner(-1e6-PI, -1e6-2*PI); //三个vector参数abc表示以a为顶点的角bac/cab
inline bool zero(const double &x){ return abs(x)<eps; }
inline bool equal(const double &a, const double &b){ return zero(a-b); }
inline bool less(const double &a, const double &b){ return a<b-eps; } //更严格
inline bool greater(const double &a, const double &b){ return a>b+eps; }
LL pre(LL i, LL n){ return i==0?n-1:i-1; }
LL nxt(LL i, LL n){ return i==n-1?0:i+1; }
template <typename Iterator, typename Container>
Iterator pre(Iterator a, Container &S){
return a==S.begin()?S.end():--a;
}
template <typename Iterator, typename Container>
Iterator nxt(Iterator a, Container &S){
return ++a==S.end()?S.end():a;
}
inline LL sqr(const LL &x){ return x*x; }
inline bool cmp1(const V &a, const V &b){ return a.x<b.x; }
inline bool cmp2(const V &a, const V &b){ return a.y<b.y; }
inline bool cmp3(const V &a, const V &b){ return a.x>b.x||a.x==b.x&&a.y<b.y; } //先x后y升序排序
inline bool cmp4(const V &a, const V &b){ return a.x<b.x||a.x==b.x&&a.y>b.y; } //先x后y升序排序
struct cmp5{
bool operator()(const V &a, const V &b){ return cmp3(a, b); }
};
struct cmp6{
bool operator()(const V &a, const V &b){ return cmp4(a, b); }
};
inline V operator-(const V &a){ return V(-a.x, -a.y); }
inline V operator+(const V &a, const V &b){ return V(a.x+b.x, a.y+b.y); }
inline V operator-(const V &a, const V &b){ return V(a.x-b.x, a.y-b.y); }
inline V operator*(const LL &x, const V &a){ return V(a.x*x, a.y*x); }
inline V operator*(const V &a, const LL &x){ return V(a.x*x, a.y*x); }
inline V operator/(const V &a, const LL &x){ return V(a.x/x, a.y/x); }
inline bool operator==(const V &a, const V &b){ return a.x==b.x&&a.y==b.y;}
inline bool operator!=(const V &a, const V &b){ return !(a==b); }
inline LL operator*(const V &a, const V &b){ return a.x*b.x+a.y*b.y; }
inline LL operator^(const V &a, const V &b){ return a.x*b.y-a.y*b.x; }
inline double len(const V &a){ return sqrt(a.x*a.x+a.y*a.y); }
inline double dis(const V &a, const V &b){ return len(a-b); }
inline V c_wise(const V &a){ return V(a.y, -a.x); }
inline double S_tri(const V &a, const V &b, const V &c){ return abs((b-a)^(c-a))/2; }
inline LL S_tri2(const V &a, const V &b, const V &c){ return abs((b-a)^(c-a)); }
inline double S_iso(const LL &l, const double &theta){ return 0.5*l*l*sin(theta); }
inline double S_roundtable(const LL &r, const LL &R, const LL &h){ //圆台体积
return PI*h*(sqr(r)+r*R+sqr(R))/3;
}
bool equal_sign(LL a, LL b){
return a>0&&b>0||a<0&&b<0;
}
bool contra_sign(LL a, LL b){
return a>0&&b<0||a<0&&b>0;
}
/*inline bool operator<(const V &a, const V&b){ //二元组排序
return less(a.x, b.x)||(equal(a.x, b.x)&&less(a.y, b.y));
}*/
inline double angle(const LL &a, const LL &b, const LL &c){ //余弦定理
return acos((sqr(b)+sqr(c)-sqr(a))/(2*b*c));
}
inline double angle(const V &a, const V &b){ //向量夹角
if ((a^b)==0) return 0;
return acos(a*b/len(a)/len(b));
} //0~pi
inline double angle2(const V &a, const V &b){ //-pi~pi,叉乘决定符号,与向量顺序有关
return (a^b)>=0?angle(a, b):-angle(a, b);
}
inline bool obtuse(const V &a, const V &b, const V &c){ return (b-a)*(c-a)<0; } //∠bac
inline bool acute(const V &a, const V &b, const V &c){ return (b-a)*(c-a)>0; }
inline bool right(const V &a, const V &b, const V &c){ return (b-a)*(c-a)==0; }
struct L{ //记录单位方向向量+两点,也可以用来表示线段
V d, a, b;
L(){}
L(const V &x1, const V &x2, const V &x3):d(x1),a(x2),b(x3){}
L(const V &x, const V &y){ *this=L(y-x, x, y); }
L(const V &d){ *this=L(d, V(0,0), d); }
};
inline L get_L(const V &d, const V &p){ return L(d, p, p+d); }
inline double angle(const V &v){ //从x轴开始算
double tmp=atan2(v.y, v.x);
return tmp>=0?tmp:tmp+2*PI;
}
inline double angle(const L &l){
return angle(l.d);
}
inline bool on_line(const V &p, const L &l){
return (l.d^(p-l.a))==0;
}
inline bool on_seg(const V &p, const L &l){
return (dis(p, l.a)+dis(p, l.b)-dis(l.a, l.b))==0;
}
inline double dis(const V &p, const L &l){
return 1.0*abs((p-l.a)^(p-l.b))/dis(l.a, l.b);
}
inline double dis2(const V &p, const L &l){ //带符号距离
return 1.0*((p-l.a)^(p-l.b))/dis(l.a, l.b);
}
inline bool collinear(const V &a, const V &b){ return (a^b)==0; }
inline bool orthogonal(const V &a, const V &b){ return a*b==0; }
inline bool parallel(const L &l1, const L &l2){ return (l1.d^l2.d)==0; }
inline bool orthogonal(const L &l1, const L &l2){ return (l1.d*l2.d)==0; }
inline bool straddle(const L &l1, const L &l2){ //l1跨立在l2上
LL f1=(l1.a-l2.a)^l2.d;
LL f2=(l1.b-l2.a)^l2.d;
if (f1*f2<=0) return true;
else return false;
}
inline bool is_LLersect2(const L &l1, const L &l2){ //线与线段相交,l1为线
LL a=(l2.a-l1.a)^l1.d, b=(l2.b-l1.a)^l1.d;
if (a>=0&&b<=0) return true;
if (a<=0&&b>=0) return true;
return false;
}
inline bool is_LLersect(const L &l1, const L &l2){ //线段相交
if ((min(l1.a.x, l1.b.x)>=max(l2.a.x, l2.b.x))||
(max(l1.a.x, l1.b.x)<=min(l2.a.x, l2.b.x))||
(min(l1.a.y, l1.b.y)>=max(l2.a.y, l2.b.y))||
(max(l1.a.y, l1.b.y)<=min(l2.a.y, l2.b.y)))
return false;
//以上是快速排斥
return straddle(l1, l2)&&straddle(l2, l1);
} //先考虑l1跨立在l2上,再考虑l2跨立在l1上
//为方便操作直接传数组,以O为原点
inline double L_polygen(const V *a, const LL &n){
double res=0;
for (LL i=0; i<n; ++i) res+=dis(a[i], a[(i+1)%n]);
return res;
}
inline LL S2_polygen(const V *a, const LL &n){
LL res=0;
for (LL i=0; i<n; ++i) res+=(a[i]^a[(i+1)%n]);
return res;
}
inline void read_polygen(V *a, LL &n, bool with_n){
if (with_n) scanf("%lld", &n);
for (LL i=0; i<n; ++i) a[i].read();
}
inline void prLL_polygen(V *a, LL &n, bool with_n){
if (with_n) printf("%lld\n", n);
for (LL i=0; i<n; ++i) a[i].prLL();
}
inline bool is_convex(const V *a, const LL &n){
LL j, k, d=0, nd; LL o;
for (LL i=0; i<n; ++i){
j=(i+1)%n, k=(i+2)%n;
o=(a[j]-a[i])^(a[k]-a[j]);
if (o==0) continue;
nd=o<0?-1:1;
if (!d) d=nd;
else if (d!=nd) return false;
}
return true;
}
inline bool cmp(const V &a, const V &b){
LL dot=(a-O)^(b-O);
if (dot>0) return true;
return false;
}
inline LL rshort(const V &a, const V &b){ //极角排序(找正确的基准点以极角为指标排序)比较函数
LL dot=(a-O)^(b-O);
if (dot>0) return 2; //左返回0,等返回1,右返回2
if (dot==0) return dis(a, O)<=dis(b, O); //全共线情况
return 0;
}
inline LL lshort(const V &a, const V &b){
LL dot=(a-O)^(b-O);
if (dot>0) return 0; //左返回2,等返回1,右返回0
if (dot==0) return dis(a, O)<dis(b, O);
return 2;
}
inline bool in_poly(const V &p, const V *a, const LL &n){
double x; LL j, res=0;
for (LL i=0; i<n; ++i){
j=(i+1)%n;
if (a[i].y==a[j].y) continue;
if (max(a[i].y, a[j].y)<p.y) continue;
if (min(a[i].y, a[j].y)>=p.y) continue;
x=a[i].x+1.0*(p.y-a[i].y)/(a[j].y-a[i].y)*(a[j].x-a[i].x);
if (x<p.x) res^=1;
}
return res?true:false;
}
inline LL in_convex(const V &p, const V *a, const LL &n){ //已经去边界极角排序,满足a[0]在最下方
O=a[0];
if (lshort(a[1], p)||rshort(a[n-1], p)) return 0;
LL x=upper_bound(a+1, a+n, p, cmp)-a-1;
O=a[x]; //2包含 1在边上 0在凸包外
return lshort(p, a[(x+1)%n]);
}
inline V find_lowest(V *a, const LL &n){
LL id=0;
for (LL i=0; i<n; ++i)
if (a[i].y<a[id].y||
a[i].y==a[id].y&&a[i].x<a[id].x) id=i;
return a[id];
}
inline void polar_sort(V *a, const LL &n, const V &origin){
O=origin;
sort(a, a+n, rshort); //以在右侧或者共线且距离小为小
LL m; //最后的共线部分要反转,以便边上点要保留的情况
for (m=n-1; m>=0; --m) if (!((a[m]-a[0])^(a[n-1]-a[0]))) break;
if (~m) reverse(a+m+1, a+n); //如果是一条直线就不用反转了
O=V(0, 0);
}
bool cmp_A(const V &a, const V &b){
double a1=angle(a-O), a2=angle(b-O);
return a1<a2||a1==a2&&dis(a, O)<dis(b, O);
}
inline void polar_sort2(V *a, const LL &n, const V &origin){ //真·极角排序
O=origin;
sort(a, a+n, cmp_A);
O=V(0, 0);
}
inline bool turn_right(const V &p1, const V &p2, const V &p3){ //p1指向p2,p2指向p3,前面乘后面
return ((p2-p1)^(p3-p2))<0;
}
inline bool turn_left(const V &p1, const V &p2, const V &p3){
return ((p2-p1)^(p3-p2))>0;
}
inline bool turn_right2(const V &O, const V &A, const V &B){ //OA到OB
return ((A-O)^(B-O))<0;
}
inline bool turn_left2(const V &O, const V &A, const V &B){
return ((A-O)^(B-O))>0;
}
inline void graham(V *a, LL &n, bool include_on_edge){
LL cnt=0, id1, id2;
LL *s=new LL[n];
for (LL i=0; i<=n; ++i){
while (cnt>=2){
id1=s[cnt-1]; id2=s[cnt-2];
if (include_on_edge){
if (a[id1]!=a[i%n]&&!turn_right(a[id2], a[id1], a[i%n])) break;
} else if (turn_left(a[id2], a[id1], a[i%n])) break;
if (i==n&&cnt==2) break; //特判点都在一条直线上的情况
--cnt;
}
if (i<n) s[cnt++]=i;
}
//if (a[s[0]]==a[s[cnt-1]]) cnt=1; //特判只有一个点的情况,不出现重复点
n=cnt;
for (LL i=0; i<n; ++i) a[i]=a[s[i]];
delete []s;
}
inline void andrew(V *a, LL &n, bool include_on_edge){
LL cnt=0, id1, id2;
LL *s=new LL[n];
for (LL i=0; i<n; ++i){
while (cnt>=2){
id1=s[cnt-1]; id2=s[cnt-2];
if (include_on_edge){
if (!turn_right(a[id2], a[id1], a[i%n])) break;
} else if (turn_left(a[id2], a[id1], a[i%n])) break;
--cnt;
}
if (i<n) s[cnt++]=i;
}
n=cnt;
for (LL i=0; i<n; ++i) a[i]=a[s[i]];
delete []s;
}
inline void merge_2(V *a, LL &n, V *b, LL &m, V *c, LL &N){
N=0;
for (LL i=0; i<n; ++i) c[N++]=a[i];
for (LL i=1; i<m-1; ++i) c[N++]=b[i];
}
inline void merge_convex(V *a, LL &n, V *b, LL &m, V *c, LL &N, bool include_on_edge, bool (*cmp)(const V &a, const V &b)){
LL cnta=0, cntb=0; N=0;
while (N<n+m){
while ((cntb==m||cmp(a[cnta], b[cntb]))&&cnta<n) c[N++]=a[cnta++];
while ((cnta==n||!cmp(a[cnta], b[cntb]))&&cntb<m) c[N++]=b[cntb++];
}
andrew(c, N, include_on_edge);
}
template <typename cmp> using Iter=typename multiset<V, cmp>::iterator;
template <typename cmp, typename Iter>
inline bool in_dynavex(Iter iter, multiset<V, cmp> &S){
if (iter==S.begin()||iter==--S.end()) return false;
if (!turn_left(*pre(iter, S), *iter, *nxt(iter, S))) return true;
return false;
}
template <typename cmp>
inline bool in_dynavex(V &p, multiset<V, cmp>&S){
auto iter=S.find(p);
if (iter!=S.end()) return true;
iter=S.insert(p);
bool flag=in_dynavex(iter, S);
S.erase(iter);
return flag;
}
template <typename maLLain_type> //对关于边的数据进行动态维护
inline void maLLain1(maLLain_type &obj, const V &a, const V &b){ //加边
obj+=dis(a, b);
}
template <typename maLLain_type>
inline void maLLain2(maLLain_type &obj, const V &a, const V &b){ //删边
obj-=dis(a, b);
}
template <typename cmp, typename maLLain_type>
inline void dynavex_insert(const V &p, multiset<V, cmp> &S, maLLain_type &obj){
auto iter=S.insert(p);
if (S.siz()==2) maLLain1(obj, *S.begin(), *++S.begin());
if (S.siz()<3) return;
if (in_dynavex(iter, S)){
S.erase(iter);
return;
}
if (iter!=S.begin()&&iter!=--S.end())
maLLain2(obj, *pre(iter, S), *nxt(iter, S));
if (iter!=S.begin()){
maLLain1(obj, *pre(iter, S), *iter);
while (pre(iter, S)!=S.begin()){
auto iter2=pre(iter, S);
auto iter3=pre(iter2, S);
if (!turn_left(*iter3, *iter2, *iter)){
maLLain2(obj, *iter2, *iter3);
maLLain2(obj, *iter2, *iter);
maLLain1(obj, *iter3, *iter);
S.erase(iter2);
}
else break;
}
}
if (iter!=--S.end()){
maLLain1(obj, *nxt(iter, S), *iter);
while (++nxt(iter, S)!=S.end()){
auto iter2=nxt(iter, S);
auto iter3=nxt(iter2, S);
if (!turn_left(*iter, *iter2, *iter3)){
maLLain2(obj, *iter2, *iter3);
maLLain2(obj, *iter2, *iter);
maLLain1(obj, *iter3, *iter);
S.erase(iter2);
}
else break;
}
}
}
template <typename maLLain_type>
struct Dynavex{
multiset<V, cmp5> upper;
multiset<V, cmp6> lower;
inline void insert(const V &p, maLLain_type &obj){
dynavex_insert(p, upper, obj);
dynavex_insert(p, lower, obj);
}
inline bool inside(const V &p){
return in_dynavex(p, upper)&&in_dynavex(p, lower);
}
};
inline double height(const V &a, const V &b1, const V &b2){ //b1、b2为底
return S_tri(a, b1, b2)/dis(b1, b2);
}
inline double diameter(const V *a, const LL &n){
double ans=0; LL j=0;
for (LL i=0; i<n; ++i){ //枚举顶点,对面是平行线
while (height(a[i], a[j], a[(j+1)%n])<height(a[i], a[(j+1)%n], a[(j+2)%n]))
j=(j+1)%n;
ans=max(ans, dis(a[i], a[j]));
ans=max(ans, dis(a[i], a[(j+1)%n]));
}
return ans;
}
double max_dis(V *a, LL &n){ //最长距离点对(直径)
graham(a, n, false);
return diameter(a, n);
}
double min_dis(V *a, V *b, const LL &l, const LL &r){ //随着分治进行,对b要按y排序
if (l+1==r) return INF;
LL m=(l+r)>>1;
double D=min(min_dis(a, b, l, m), min_dis(a, b, m, r));
V *c=(V*)malloc(sizeof(V)*(r-l));
V *d=(V*)malloc(sizeof(V)*(r-l));
LL i=l, j=m, cnt=0;
while (i<m||j<r){ //归并
if (j==r||i<m&&b[i].y<b[j].y) c[cnt++]=b[i++];
else c[cnt++]=b[j++];
} cnt=0;
L seperator(a[m], V(a[m].x, a[m].y+1));
for (i=0; i<r-l; ++i) if (dis(c[i], seperator)<D) d[cnt++]=c[i];
for (i=0; i<cnt-2; ++i) //距离分割线在d内的点,按y坐标向后枚举两个
D=min(D, min(dis(d[i], d[i+1]), dis(d[i], d[i+2])));
D=min(D, dis(d[cnt-2], d[cnt-1]));
memcpy(b+l, c, sizeof(V)*(r-l));
free(c); free(d);
return D;
}
double min_dis(V *a, const LL &n){ //最短距离点对
sort(a, a+n, cmp1);
V *b=(V*)malloc(sizeof(V)*n);
memcpy(b, a, sizeof(V)*n);
double ans=min_dis(a, b, 0, n);
free(b);
return ans;
}
void Minkowski_sum(V *a, LL n, V *b, LL m, V *c, LL &N){
V *l=(V*)malloc((n+m)*sizeof(V)); N=0;
LL cnta=0, cntb=0;
V pa, pb;
while (cnta<n||cntb<m){
if (n) pa=a[(cnta+1)%n]-a[cnta];
if (m) pb=b[(cntb+1)%m]-b[cntb];
if (cnta==n){
l[N++]=pb; cntb++;
continue;
}
if (cntb==m){
l[N++]=pa; cnta++;
continue;
}
if ((pa^pb)>0) l[N++]=pa, cnta++;
else if ((pa^pb)==0) l[N++]=pa+pb, cnta++, cntb++;
else l[N++]=pb, cntb++;
}
if (!m) c[0]=a[0];
else if (!n) c[0]=b[0];
else c[0]=a[0]+b[0]; //最下面的点,一定是正好往右走 //可以先判一下
for (LL i=0; i<N; ++i)
c[i+1]=c[i]+l[i];
free(l);
}
using pdd=pair<double, double>;
inline bool seg_LLersect(const pdd &a, const pdd &b){
if (less(b.second, a.first)) return false;
if (greater(b.first, a.second)) return false;
return true;
}
inline void seg_add(pdd &a, const pdd &b){
if (!seg_LLersect(a, b)) return;
a.first=min(a.first, b.first);
a.second=max(a.second, b.second);
}
inline bool seg_include(const pdd &a, const pdd &b){
return a.first<=b.first&&a.second>=b.second;
}
}
using namespace geo_2d;
const LL maxn=405;
LL S, n, m, cnt, siz[maxn];
pair<LL, LL> area[maxn];
V a[maxn], b[maxn];
LL A[maxn], B[maxn], cnta, cntb;
struct Bit{
LL a[maxn], n, q[maxn*10], m;
inline LL lowbit(LL x){ return x&(-x); }
Bit(){};
Bit(LL N){ n=N; }
inline void clear(){
for (LL i=0; i<m; ++i)
a[q[i]]=0;
m=0;
}
inline void modify(LL x, LL d){
while (x<=n){
if (!a[x]) q[m++]=x;
a[x]+=d;
x+=lowbit(x);
}
}
inline LL query(LL x){
LL ans=0;
while (x){
ans+=a[x];
x-=lowbit(x);
}
return ans;
}
inline LL query(LL l, LL r){
return query(r)-query(l-1);
}
}bit;
int main(){
scanf("%lld", &S); S*=2;
read_polygen(a, n, true);
bit.n=n;
V d, t; LL ans=0;
for (LL i=0; i<n; ++i)
for (LL j=i+1; j<n; ++j){
cnta=cntb=0;
d=a[j]-a[i];
for (LL k=0; k<n; ++k){
if (k==i||k==j) continue;
t=a[k]-a[i];
if ((d^t)<0) A[cnta++]=S_tri2(a[i], a[j], a[k]);
else B[cntb++]=S_tri2(a[i], a[j], a[k]);
}
if (!cnta||!cntb) continue;
sort(B, B+cntb);
for (int k=0; k<cnta; ++k)
ans+=B+cntb-lower_bound(B, B+cntb, S-A[k]);
}
for (LL i=0; i<n; ++i){
m=0;
for (LL j=0; j<n; ++j) if (i!=j) b[m++]=a[j];
polar_sort2(b, n-1, a[i]);
for (LL j=0; j<n-1; ++j){ //枚举对角线
LL p1=nxt(j, n-1), p2=nxt(j, n-1);
while (turn_left2(a[i], b[j], b[p2])&&p2!=j)
p2=nxt(p2, n-1);
if (turn_right2(a[i], b[j], b[p1])) continue;
if (p2==j) continue;
cnt=0;
for (LL k=p1; k!=j; k=nxt(k, n-1)){
if (turn_left2(a[i], b[j], b[k]))
area[cnt++]=make_pair(S-S_tri2(a[i], b[j], b[k]), k);
else area[cnt++]=make_pair(S_tri2(a[i], b[j], b[k]), k);
}
sort(area, area+cnt, std::greater<pair<LL, LL>>()); //以面积大为小,方便查询
for (int i=0; i<cnt; ++i) siz[area[i].second]=i+1;
/*for (LL k=p1; k!=j; k=nxt(k, n-1)){
if (turn_left2(a[i], b[j], b[k]))
siz[k]=lower_bound(area, area+cnt, S-S_tri2(a[i], b[j], b[k]),
std::greater<LL>())-area+1;
else siz[k]=lower_bound(area, area+cnt, S_tri2(a[i], b[j], b[k]),
std::greater<LL>())-area+1;
}*/
bit.clear();
while (turn_left(a[i], b[j], b[p1])){
while (p2!=j&&angle(b[p1]-a[i], b[j]-a[i])+angle(b[p2]-a[i], b[j]-a[i])>=PI){
bit.modify(siz[p2], 1);
p2=nxt(p2, n-1);
}
ans+=bit.query(siz[p1]);
p1=nxt(p1, n-1);
}
}
}
printf("%lld\n", ans/2);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3508kb
input:
2 4 1 2 3 4 3 3 4 1
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4314 26 1569 1513 1454 1067 122 1333 1065 1429 1032 577 1159 955 587 1231 118 1270 1621 1536 512 871 698 1113 19 137 268 940 492 929 96 1077 292 174 661 1131 1056 239 742 194 1057 974 1604 1523 124 723 315 900 897 1236 469 477 1085 1189
output:
25417
result:
ok single line: '25417'
Test #3:
score: 0
Accepted
time: 39ms
memory: 3644kb
input:
5965 76 1251 145 1786 963 1570 61 1653 264 91 1726 695 934 743 1150 619 405 243 1862 1721 1044 838 1125 125 987 1203 910 1627 393 1553 859 1010 918 1188 1798 977 1835 1446 675 158 481 1808 1417 1144 276 788 1834 697 920 778 1010 618 1229 1359 652 58 597 452 208 1457 1120 1081 675 636 1180 914 538 15...
output:
2142660
result:
ok single line: '2142660'
Test #4:
score: 0
Accepted
time: 1401ms
memory: 3684kb
input:
1 250 317585868 598152434 843773388 209824234 92263069 613343638 590616991 779389536 116195475 274286318 290397390 898992827 50266020 818254190 627104042 754661662 336582604 62711465 95657793 175801878 452170674 298288603 966795197 10639394 791949036 803586958 201721863 62682611 772808232 475871864 ...
output:
257344298
result:
ok single line: '257344298'
Test #5:
score: 0
Accepted
time: 1401ms
memory: 3756kb
input:
1000 250 489909807 579157286 426974190 974851864 351232834 414620104 391171962 367547122 311733897 568131259 671852560 798180643 450291034 329717374 564801347 64208901 522900708 569058854 747496171 165286265 364729854 440961125 42573807 338449743 752445471 558080018 195329229 256606629 388417588 393...
output:
258359224
result:
ok single line: '258359224'
Test #6:
score: 0
Accepted
time: 1408ms
memory: 3644kb
input:
1000000 250 941215258 343282149 682958157 715880819 517644744 497183549 859346949 977273175 940346170 218118245 91625396 464321762 648792552 562719601 721515059 964378174 422796415 202406046 353671885 383976556 636972702 45133308 145678370 401457239 475059265 752421732 674466339 50424707 864771350 2...
output:
260650430
result:
ok single line: '260650430'
Test #7:
score: 0
Accepted
time: 1381ms
memory: 3576kb
input:
100000000000 250 101624314 159623553 153687593 122892370 233790285 234784657 426866037 277531011 387784199 201308854 748358468 3428305 201922674 774144670 481611426 971908533 367035225 423292377 259088766 211506135 318942549 175802255 917757628 328812367 204268050 861194486 621660803 662766622 20447...
output:
257000024
result:
ok single line: '257000024'
Test #8:
score: 0
Accepted
time: 881ms
memory: 3648kb
input:
128 250 87940 490622755 844625 470949830 1360527 463139767 1542565 460754799 3565033 440398624 4286283 434670747 7546740 413456442 9387580 403566324 9994703 400527341 12551094 388673614 13793262 383368062 15540302 376311676 20451785 358460216 27642495 336053705 36346955 312848044 42249640 298841831 ...
output:
158882750
result:
ok single line: '158882750'
Test #9:
score: 0
Accepted
time: 884ms
memory: 3644kb
input:
1000000000000 250 74316 491379590 2172584 453439667 3563944 440407695 4252955 434924140 5885704 423507761 11258282 394493917 22610880 351340562 23248466 349308344 27064687 337728036 29093863 331930340 32426158 322870944 37313956 310469989 39123895 306110299 40360287 303197219 51224833 279543995 7262...
output:
158882596
result:
ok single line: '158882596'
Test #10:
score: 0
Accepted
time: 892ms
memory: 4064kb
input:
1000000000000000 250 1999 498585909 86254 490713066 364512 480911278 717767 473218431 2917554 446064464 28615316 333277234 31196560 326151400 37660724 309625645 40743604 302304367 52693714 276578679 57149865 267871245 64676503 254045831 64986137 253498601 73177329 239572643 73185710 239558907 764001...
output:
158690301
result:
ok single line: '158690301'
Test #11:
score: 0
Accepted
time: 5957ms
memory: 3692kb
input:
1 400 467526769 85195364 225672739 676874691 482779579 401136887 842924424 883009585 695094694 16970951 127866211 667087790 348796082 450340214 758113817 947053867 50859403 422719383 484509644 744417132 525901816 509623389 342643408 286087025 339829212 216954812 925876339 274973537 740209606 7562305...
output:
1717879706
result:
ok single line: '1717879706'
Test #12:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
1 4 1 2 3 4 3 3 4 1
output:
3
result:
ok single line: '3'
Test #13:
score: 0
Accepted
time: 5980ms
memory: 3692kb
input:
100000000000000 400 380714483 121012358 754639896 374212230 251499688 914785718 304426117 493721170 648093554 223992706 636369399 132682333 405088289 752182289 656813997 658920273 266851901 664445919 692050240 567918329 667813809 704320804 773813959 603467078 766217868 969675946 479449900 307909031 ...
output:
1695084992
result:
ok single line: '1695084992'
Test #14:
score: 0
Accepted
time: 5982ms
memory: 3672kb
input:
10000000 400 580695944 192753382 937895019 137397468 390252822 523406369 982122005 569014908 200988937 5989403 145078052 899491855 606826411 803166147 966562503 945153639 748006339 640561259 424430815 433294206 276733249 889483881 663438442 358661637 742918074 262349148 189748187 519434585 511863931...
output:
1676593188
result:
ok single line: '1676593188'
Test #15:
score: 0
Accepted
time: 6039ms
memory: 3652kb
input:
1400434 400 53751349 97477045 310204931 125239024 369742886 808554246 579714188 367660695 378859868 573460506 908899666 159398706 522170854 728188301 958134200 151674089 315323856 944510256 242333635 209656437 830160729 705204733 958202640 984858268 577761247 712628528 37506279 478164604 355539048 6...
output:
1697561644
result:
ok single line: '1697561644'
Test #16:
score: 0
Accepted
time: 5944ms
memory: 3908kb
input:
10000 400 996609018 505810866 214183081 251635386 709268177 112304605 73830539 236945177 452391147 309229299 79768211 481923079 844749319 965243603 364472947 173236695 265534912 61419527 360623062 896888897 851741353 252319248 814864031 987082658 981912301 20545573 890090827 150513184 827242596 4610...
output:
1685812686
result:
ok single line: '1685812686'
Test #17:
score: 0
Accepted
time: 5931ms
memory: 3640kb
input:
10010 400 516735939 553106692 890223632 284242609 18974994 939328370 50066856 18053211 46277717 854942078 50330486 184445579 798012040 803346910 204171736 30696286 650486690 729301542 830815134 561605913 465213728 771175096 632289323 630366465 232861648 548220307 430645723 334466338 353796222 241827...
output:
1706903950
result:
ok single line: '1706903950'
Test #18:
score: 0
Accepted
time: 5977ms
memory: 3692kb
input:
10000000 400 791559755 728793923 92037253 880096143 8427433 624970639 919700463 21453086 194307614 18931032 494247451 372482124 61387912 352841935 317275458 6622899 648068020 993901805 727090562 356208771 236083096 634624025 595529501 692789111 980738959 251376808 935744668 327137643 51021009 642836...
output:
1683868754
result:
ok single line: '1683868754'
Test #19:
score: 0
Accepted
time: 5933ms
memory: 3752kb
input:
1000012341 400 846580774 376779176 119449172 758044568 71746587 70705427 430552563 284033019 79315691 670109747 481965709 581064071 453381439 990950986 528555866 572697188 989259359 109786938 135179607 420627391 344497211 769574973 612914473 513812777 293424153 762274117 686490297 854941395 56500473...
output:
1680918602
result:
ok single line: '1680918602'
Test #20:
score: 0
Accepted
time: 5934ms
memory: 4068kb
input:
1000000000000000000 400 606198357 9925234 607356611 30504202 448275416 776381334 806632151 85429027 391625941 281930407 45916121 618962261 308227945 444162800 639228228 470344940 420290106 560455339 41749802 67831866 153968729 82178563 255385736 622775750 853688028 560309693 197262244 114483728 5386...
output:
0
result:
ok single line: '0'
Test #21:
score: 0
Accepted
time: 5947ms
memory: 3656kb
input:
142 400 98627 50502 92610 44300 49410 45941 89508 50351 41314 77088 16068 91491 26303 44998 46623 86154 84015 41296 2313 81223 76303 17007 53850 47688 18060 94553 5476 93120 7269 96627 24889 9413 518 15885 75802 40475 60582 81522 36450 29313 10034 53032 23950 52968 342 12010 40099 94836 54282 83632 ...
output:
1694281814
result:
ok single line: '1694281814'
Test #22:
score: 0
Accepted
time: 3712ms
memory: 3704kb
input:
128 400 72449 491488600 653498 474444743 904203 469943626 1499057 461311367 1814375 457443167 2491230 450149978 3878592 437842544 4083632 436227305 4451148 433431723 4872147 430369475 6469804 419825528 7603033 413136729 7982396 411013044 9136446 404852894 9938222 400805975 10125900 399883237 1037223...
output:
1050739900
result:
ok single line: '1050739900'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
4 5 1 1 3 3 3 0 0 1 1 0
output:
3
result:
ok single line: '3'
Test #24:
score: 0
Accepted
time: 3729ms
memory: 3688kb
input:
112389123 400 11746 496572707 44010 493366069 135596 488356203 1382973 462837371 1594879 460095918 2417874 450887591 6116772 422029763 6504141 419614440 6587129 419106618 7409315 414242100 7663842 412792731 8483413 408286068 9627384 402354223 13271106 385566682 16257334 373536432 17056508 370518018 ...
output:
1050739900
result:
ok single line: '1050739900'
Test #25:
score: 0
Accepted
time: 2460ms
memory: 3748kb
input:
128 350 86843 490681410 2915032 446087708 3187793 443629513 5167309 428301963 10467574 398225717 18101330 366682062 22440269 351889555 26133020 340469169 29330693 331268247 29838053 329859633 33443623 320208044 35159561 315817029 35318797 315415656 47708501 286851225 55489891 271066027 57452172 2672...
output:
614597725
result:
ok single line: '614597725'
Test #26:
score: 0
Accepted
time: 2478ms
memory: 3800kb
input:
128129123481 350 73606 491420902 885312 470258972 2635647 448729143 2817083 446998604 5217365 427957343 5763571 424300906 7626234 413005317 8800294 406603802 11436463 393671873 12072236 390791493 14331191 381147956 14504061 380443762 16647823 372052065 18948962 363655218 20132752 359545647 20334777 ...
output:
614597648
result:
ok single line: '614597648'
Test #27:
score: 0
Accepted
time: 1551ms
memory: 3688kb
input:
12831 300 49128 492991004 901834 469982981 4309383 434495700 4620550 432182591 5548428 425719157 6216086 421403266 7727344 412434983 9577645 402604341 21571352 354720856 25037060 343762341 30839589 327117064 31723948 324735801 41852105 299748891 43932660 295054686 45399342 291821608 45894945 2907427...
output:
330791175
result:
ok single line: '330791175'
Test #28:
score: 0
Accepted
time: 1539ms
memory: 3668kb
input:
1231198212341 300 364162 480920422 628161 474944715 870281 470512298 2442462 450639119 3220861 443338834 4167735 435576672 4563839 432598140 8743883 406900978 10480691 398162648 11225189 394647331 11526077 393260939 11553424 393135867 13377265 385116084 14762605 379398709 17501447 368869732 20515223...
output:
330790448
result:
ok single line: '330790448'
Test #29:
score: 0
Accepted
time: 2ms
memory: 3592kb
input:
1 4 0 0 1000 0 0 1000 1000 1000
output:
1
result:
ok single line: '1'
Test #30:
score: 0
Accepted
time: 11ms
memory: 3724kb
input:
8408 49 1492 1850 761 591 536 399 1943 1555 294 2079 1846 1514 1753 1551 782 1184 191 1164 975 438 315 1938 582 680 282 1370 489 105 957 1966 1722 1780 1089 1853 934 549 266 385 664 836 1234 1899 950 989 866 1995 116 1495 169 187 1484 419 1946 1822 1117 1444 976 1371 2108 1827 1582 450 1616 1846 492...
output:
335537
result:
ok single line: '335537'
Test #31:
score: 0
Accepted
time: 4ms
memory: 3812kb
input:
6424 31 2642 826 1979 2024 1468 758 1651 1649 2827 1185 807 1544 2910 390 1678 2036 2369 2422 1007 2712 1506 2640 1619 394 704 2858 903 1096 1705 220 2358 1248 2148 2430 1298 2708 1707 966 770 2087 2462 131 1308 780 1662 1351 866 1185 24 1093 1762 1305 1629 185 2460 1291 2422 2481 631 1422 670 2774
output:
51002
result:
ok single line: '51002'
Test #32:
score: 0
Accepted
time: 2ms
memory: 3616kb
input:
7715 33 2788 2333 2106 2760 3132 1162 712 3009 2475 2869 62 3164 1967 1449 2067 438 300 3153 2416 809 1608 476 2791 927 1322 1472 1269 1094 1106 1466 2771 591 3049 2433 1384 711 2625 753 654 1999 3315 983 978 2924 2326 1497 3297 1134 2319 128 1786 776 1654 1032 1193 281 1772 3232 208 1085 980 2523 3...
output:
65127
result:
ok single line: '65127'
Test #33:
score: 0
Accepted
time: 42ms
memory: 3616kb
input:
8141 79 2997 1721 1062 1408 2797 1835 1902 3586 1370 1205 3841 3654 711 2666 3131 3767 38 2244 3331 700 1804 3170 2342 3632 2731 2428 1550 3358 3848 1123 2616 3252 3082 2362 3279 661 1741 910 125 600 3317 2124 1667 1023 1319 2706 156 1499 2948 3652 238 2960 1573 155 1733 681 3221 828 3518 2688 1134 ...
output:
2456415
result:
ok single line: '2456415'
Test #34:
score: 0
Accepted
time: 52ms
memory: 3932kb
input:
1897 84 1351 810 554 1362 618 423 965 1497 948 140 1885 819 993 1539 694 2280 1195 175 2191 950 1687 670 575 2093 1688 198 1808 1779 1379 1808 194 465 829 1229 952 1130 1310 461 1148 756 2087 2151 225 582 2086 769 401 1381 1469 76 2176 331 916 89 1878 305 0 2076 2057 1346 2248 1208 585 1032 2202 180...
output:
3113918
result:
ok single line: '3113918'