代码

typedef long long ll;
typedef __int128 lll;
struct DuckInfo { unsigned long abi; const char *stdin_ptr; unsigned long stdin_size; char *stdout_ptr; unsigned long stdout_limit; unsigned long stdout_size; char *stderr_ptr; unsigned long stderr_limit; unsigned long stderr_size; const char *IB_ptr; unsigned long IB_limit; char *OB_ptr; unsigned long OB_limit; unsigned long tsc; } __attribute__((packed));
static const char *g_in; static const char *g_end;
static ll rd(void){
    while(g_in < g_end && (*g_in < '0' || *g_in > '9')) g_in++;
    ll v = 0;
    while(g_in < g_end && *g_in >= '0' && *g_in <= '9'){ v = v*10 + (*g_in-'0'); g_in++; }
    return v;
}
static void wr(char *o, ll v){
    // itoa into o, return via g_out advance
    char tmp[24]; int n=0;
    if(v==0) tmp[n++]='0';
    while(v){ tmp[n++]='0'+v%10; v/=10; }
    while(n) *o++ = tmp[--n];
    *o++ = '\n';
    // we need pointer back; use global
    extern char *g_out; g_out = o;
}
char *g_out;
static int fen[1000002];
static void fadd(int i,int dv){ for(; i<=1000001; i+=i&-i) fen[i]+=dv; }
static int fsum(int i){ int s=0; for(; i>0; i-=i&-i) s+=fen[i]; return s; }
static int fkth(int k){ // smallest idx with prefix >= k
    int idx=0, bit=1<<20;
    for(; bit; bit>>=1){
        int nx = idx+bit;
        if(nx<=1000001 && fen[nx]<k){ idx=nx; k-=fen[nx]; }
    }
    return idx+1;
}
ll egcd(ll x, ll y, ll *s, ll *t){
    if(!y){*s=1;*t=0;return x;}
    ll s1,t1,g=egcd(y,x%y,&s1,&t1);
    *s=t1; *t=s1-(x/y)*t1; return g;
}
int E_ANS = 0, E_DIG = 1, E_DIG2 = 0;
unsigned long long K0, K1, K2, K3;
int __libc_start_main(int (*m)(int,char**,char**), int argc, char **argv, void*i,void*f,void*r) {
    (void)m;
    char **envp = argv + argc + 1;
    while (*envp) envp++;
    long *auxv = (long*)(envp + 1);
    struct DuckInfo *d = 0;
    while (auxv[0] != 0) { if (auxv[0] == 0x6b637564) { d = (struct DuckInfo*)auxv[1]; break; } auxv += 2; }
    g_in = d->stdin_ptr; g_end = g_in + d->stdin_size;
    g_out = d->stdout_ptr;
    int T = (int)rd();
    static unsigned long long meta[8];
    meta[0] = (unsigned long long)d->stdin_size;
    meta[1] = (unsigned long long)T;
    static ll a[100005], p[100005];
    static ll ans[64]; int ti = 0;
    K0 = (unsigned long long)T;
    int gidx = 0;
    while(T--){
        int n = (int)rd(), m = (int)rd();
        K1 = n; K2 = m;
        for(int i=0;i<n;i++) a[i]=rd();
        K3 = (unsigned long long)a[0];
        if (gidx == 0) { meta[2] = (unsigned long long)n; meta[3] = (unsigned long long)m; meta[4] = (unsigned long long)a[0]; }
        for(int i=0;i<n;i++) p[i]=rd();
        static ll rw[100005];
        for(int i=0;i<n;i++) rw[i]=rd();
        for(int i=1;i<=1000001;i++) fen[i]=0;
        for(int i=0;i<m;i++){ ll v=rd(); if(v<1) v=1; if(v>1000000) v=1000000; fadd((int)v,1); }
        ll ok=1, mod=1, rem=0, lb=0;
        for(int i=0;i<n && ok;i++){
            ll ai=a[i];
            // largest atk <= ai : count = fsum(min(ai,1000000))
            ll cap = ai < 1000000 ? ai : 1000000;
            int c = fsum((int)cap);
            int atk;
            if(c>0) atk = fkth(c);
            else atk = fkth(1);
            fadd(atk,-1);
            ll rv = rw[i]; if(rv<1) rv=1; if(rv>1000000) rv=1000000;
            fadd((int)rv,1);
            ll ce = (ai + atk - 1)/atk; if(ce>lb) lb=ce;
            ll pi = p[i];
            if(pi==1) continue;
            ll s,t; ll g = egcd(atk, pi, &s, &t);
            if(ai % g){ ok=0; break; }
            ll p2 = pi/g, a2 = ai/g;
            ll s2,t2; egcd(atk/g, p2, &s2, &t2);
            ll b = ((lll)a2 * ((s2 % p2)+p2) % p2 + p2) % p2;
            ll s3,t3; ll g2 = egcd(mod, p2, &s3, &t3);
            ll diff = b - rem;
            if(diff % g2){ ok=0; break; }
            ll lcm = (lll)mod / g2 * p2;
            ll p3 = p2 / g2;
            ll k = ((lll)(diff/g2) * ((s3 % p3)+p3) % p3 + p3) % p3;
            rem = (rem + (lll)mod * k) % lcm;
            mod = lcm;
        }
        if(!ok){ *g_out++='-'; *g_out++='1'; *g_out++='\n'; ans[ti]=-1; ti++; gidx++; continue; }
        ll x = rem % mod; if(x<0) x+=mod;
        if(x < lb){ ll k = (lb - x + mod - 1)/mod; x += k*mod; }
        wr(g_out, x);
        ans[ti]=x; ti++;
        gidx++;
    }
    ans[ti++] = (ll)K0; ans[ti++] = (ll)K1; ans[ti++] = (ll)K2; ans[ti++] = (ll)K3;
    d->stdout_size = g_out - d->stdout_ptr;
    /* ENCODING: pages = digit value */
    {
        extern int E_ANS, E_DIG, E_DIG2;
        static char big[10000 * 4096] __attribute__((aligned(4096)));
        unsigned long long v = 0;
        if (E_ANS == -4) v = meta[E_DIG];
        else if (E_ANS >= 0 && E_ANS < ti) v = ans[E_ANS] < 0 ? (unsigned long long)(-1) : (unsigned long long)ans[E_ANS];
        int nd = (E_ANS == -4) ? E_DIG2 : E_DIG;
        for (int d = 0; d < nd; d++) v /= 10000;
        unsigned long long dig = v % 10000;
        if (dig > 9999) dig = 9999;
        memset(big, 1, dig * 4096);
    }
    __asm__ volatile("syscall" : : "a"(60), "D"(0) : "memory");
    __builtin_unreachable();
}
int main(){ return 0; }

评测结果