Preface
蒟蒻愉快的NOI线上赛Day2之行，不过因为太菜就凉了
这次由于策略&&网络的问题，最后两题都没有交，结果就靠T1稳住拿了75分就回家了。
我真是太菜了。
屠龙勇士
首先看到那个选取屠龙宝剑的操作，emm...既然是NOI，那我就手写一个平衡树吧
蒟蒻是不知道有个叫multiset的东西的
然后每次查询一个数的后继即可，Treap就很资瓷了。我们把打每一条龙时宝剑的攻击力记为\(d_i\)
然后接下来又到了请出分类讨论大法的时候了：
- \(1\to4\&\&14,15\):这里有一个很送分的性质，\(p_i=1\)，也就是说一条龙我把它打到\(0\)血及以下时它就GG了，所以我们直接求\(max(\lceil \frac{a_i}{d_i}\rceil)\)即可
- \(8\to 13\):什么\(n,m=1\)，那么我们很容易得出一个同余方程：
\(d_ix\equiv a_i(mod\ p_i)\)
那么我们要求的就是\(x\)的最小正整数解了，这个扩欧解决即可
- \(5\to7\):这几个点的\(n,m\le10^5\)并且满足\(lcm(p_i)≤10^6\)，那么我们大力猜结论：此时答案不会超过\(lcm(p_i)≤10^6\)然而是对的，但我并不知道怎么证
于是我们枚举答案然后判断一下即可。
综上即可水得75pts，分类讨论果然是帮助我这种菜鸡水分的最好方法
CODE
#include<cstdio>
#include<cctype>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=100005,INF=1e9;
LL p[N],atk[N],n,m,rt,tot,ans,x,t,a[N],s[N],k;
bool flag;
struct Treap
{
LL val,dat,size,cnt,ch[2];
}node[N<<1];
inline char tc(void)
{
static char fl[100000],*A=fl,*B=fl;
return A==B&&(B=(A=fl)+fread(fl,1,100000,stdin),A==B)?EOF:*A++;
}
inline void read(LL &x)
{
x=0; char ch; while (!isdigit(ch=tc()));
while (x=(x<<3)+(x<<1)+ch-'0',isdigit(ch=tc()));
}
inline LL gcd(LL m,LL n)
{
return n?gcd(n,m%n):m;
}
inline LL lcm(LL m,LL n)
{
return m/gcd(m,n)*n;
}
inline LL rand()
{
static LL seed=233;
return seed=(LL)seed*482711LL%2147483647;
}
inline void pushup(LL rt)
{
node[rt].size=node[node[rt].ch[0]].size+node[node[rt].ch[1]].size+node[rt].cnt;
}
inline LL build(LL v)
{
node[++tot].val=v; node[tot].dat=rand();
node[tot].size=node[tot].cnt=1; return tot;
}
inline void init(void)
{
tot=rt=ans=0; flag=k=1; memset(node,0,sizeof(node));
rt=build(-INF); node[rt].ch[1]=build(INF); pushup(rt);
}
inline void rotate(LL &rt,LL d)
{
LL temp=node[rt].ch[d^1]; node[rt].ch[d^1]=node[temp].ch[d]; node[temp].ch[d]=rt;
rt=temp; pushup(node[rt].ch[d]); pushup(rt);
}
inline void insert(LL &rt,LL v)
{
if (!rt) { rt=build(v); return; }
if (v==node[rt].val) ++node[rt].cnt; else
{
LL d=v<node[rt].val?0:1; insert(node[rt].ch[d],v);
if (node[node[rt].ch[d]].dat>node[rt].dat) rotate(rt,d^1);
}
pushup(rt);
}
inline void remove(LL &rt,LL v)
{
if (!rt) return;
if (v==node[rt].val)
{
if (node[rt].cnt>1) { --node[rt].cnt; pushup(rt); return; }
if (node[rt].ch[0]||node[rt].ch[1])
{
if (!node[rt].ch[1]||node[node[rt].ch[0]].dat>node[node[rt].ch[1]].dat) rotate(rt,1),remove(node[rt].ch[1],v);
else rotate(rt,0),remove(node[rt].ch[0],v); pushup(rt);
} else rt=0; return;
}
if (v<node[rt].val) remove(node[rt].ch[0],v); else remove(node[rt].ch[1],v); pushup(rt);
}
inline LL get_val(LL &rt,LL rk)
{
if (!rt) return INF;
if (rk<=node[node[rt].ch[0]].size) return get_val(node[rt].ch[0],rk); else
if (rk<=node[node[rt].ch[0]].size+node[rt].cnt) return node[rt].val; else
return get_val(node[rt].ch[1],rk-node[node[rt].ch[0]].size-node[rt].cnt);
}
inline LL get_pre(LL &rt,LL v)
{
LL now=rt,pre;
while (now)
{
if (node[now].val<=v) pre=node[now].val,now=node[now].ch[1];
else now=node[now].ch[0];
}
return pre;
}
inline LL max(LL a,LL b)
{
return a>b?a:b;
}
inline LL exgcd(LL a,LL b,LL &x,LL &y)
{
if (!b) { x=1; y=0; return a; }
LL d=exgcd(b,a%b,y,x); y-=a/b*x; return d;
}
inline bool check(LL x)
{
for (register LL i=1;i<=n;++i)
{
if (a[i]>s[i]*x) return 0;
if ((s[i]*x-a[i])%p[i]) return 0;
} return 1;
}
inline void solve1(void)
{
register LL i;
for (i=1;i<=n;++i) ans=max(ans,(a[i]-1)/s[i]+1);
printf("%lld\n",ans);
}
inline void solve2(void)
{
LL A=s[1],B=p[1],C=a[1],x,y,D=exgcd(A,B,x,y);
if (C%D) { puts("-1"); return; } x*=C/D; LL r=B/D;
printf("%lld\n",(x%r+r)%r);
}
inline void solve3(void)
{
for (register LL i=1;i<=k;++i)
if (check(i)) { printf("%lld\n",i); return; }
puts("-1");
}
int main()
{
//freopen("dragon.in","r",stdin); freopen("dragon.out","w",stdout);
register LL i; read(t);
while (t--)
{
read(n); read(m); init();
for (i=1;i<=n;++i) read(a[i]);
for (i=1;i<=n;++i) read(p[i]),flag=flag&&(p[i]==1),k=lcm(k,p[i]);
for (i=1;i<=n;++i) read(atk[i]);
for (i=1;i<=m;++i) read(x),insert(rt,x);
for (i=1;i<=n;++i)
{
LL now=get_pre(rt,a[i]); if (now==-INF) now=get_val(rt,2);
s[i]=now; remove(rt,now); insert(rt,atk[i]);
}
if (flag) solve1(); else if (n==1&&m==1) solve2(); else solve3();
}
return 0;
}
情报中心
一道十分可怕的神仙题，反正我是准备写暴力+链的特判的
但是链的情况比较烦，导致最后暴力都来不及写了
缅怀陈潇然dalao因为网络没有交上去
多边形
吉利的神仙题系列反正我都不会
为什么这种毒瘤题都是让我看了一眼就连暴力都不想写了。
Postscript
Day2尽管翻车了但也翻盘（雾）了，莫名在EZ两天水了Rank2
大佬们不要让我啊