QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#905703#1465. Not Our ProblemDEMONKILLERAC ✓33ms40792kbC++143.7kb2025-02-19 14:57:002025-02-19 14:57:19

Judging History

This is the latest submission verdict.

  • [2025-02-19 14:57:19]
  • Judged
  • Verdict: AC
  • Time: 33ms
  • Memory: 40792kb
  • [2025-02-19 14:57:00]
  • Submitted

answer

#include<bits/stdc++.h>
#define Pii pair<int,int>
#define Fi first
#define Se second
#define lc p<<1
#define rc p<<1|1
#define ll long long
#define _ll __int128
#define lb(i) i&(-i)
#define Pli pair<ll,int>
#define ull unsigned long long
using namespace std;
namespace IO{
    char buf[1<<21],*p1=buf,*p2=buf;
    #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    inline bool Isdigit(char c){return c>='0'&&c<='9';}
    template<typename T>inline void read(T &x){
        x=0;char c=getchar();bool f=0;
        while(!Isdigit(c)){if(c=='-')f=1;c=getchar();}
        while(Isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
        x=f?-x:x;
    }
    template<typename T,typename ...Args>
    inline void read(T &x,Args &...args){read(x),read(args...);}
    static int stk[65],top;
    void Write(int x){if(x<0)putchar('-'),x=-x;if(!x)return putchar('0'),void();top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(ll x){if(x<0)putchar('-'),x=-x;if(!x)return putchar('0'),void();top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(_ll x){if(x<0)putchar('-'),x=-x;if(!x)return putchar('0'),void();top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(ull x){if(x<0)putchar('-'),x=-x;if(!x)return putchar('0'),void();top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(unsigned x){if(x<0)putchar('-'),x=-x;if(!x)return putchar('0'),void();top=0;while(x){stk[++top]=x%10,x/=10;}while(top)putchar(stk[top--]^48);}
    void Write(char c){putchar(c);}
    void Write(const char *c){while(*c)putchar(*c++);}
    template<typename T,typename ...Args>
    inline void Write(T x,Args ...args){Write(x),Write(args...);}
}
using namespace IO;
const int N=1e6+10,Mod=998244353;
const ll inf=1e9,Inf=2e18;
ll K,a[N],L[N],R[N];
int n,cnt,Res=1,Fl,Mx,P[N],Sum[N],S[N];
inline bool Check(ll x,ll y){
    if(min(x,y)>inf)return true;
    return (_ll)x*y*min(x,y)>K;
}
inline ll Get(ll x){return max((ll)sqrt(K/x),K/x/x);}
void Init(int n){
    for(int i=1;i<=n;i++)
        Sum[i]=(Sum[i-1]+(Get(i)+1)%Mod)%Mod;
    Mx=sqrtl(K/(N-9)),R[Mx+1]=N-10;
    for(int i=Mx;i>=1;i--){
        R[i]=K/i/i,L[i]=R[i+1]+1;
        // cout<<i<<" "<<L[i]<<" "<<R[i]<<endl;
        // cout<<(int)sqrt(K/L[i])<<" "<<(int)sqrt(K/R[i])<<" "<<(int)sqrt(K/(R[i]+1))<<endl;
        S[i]=(S[i+1]+1LL*(i+1)*((R[i]-L[i]+1)%Mod)%Mod)%Mod;
    }
}
inline int Solve(ll x,ll y){
    ll a=Get(x),b=Get(y);
    if(a>b){
        x^=y^=x^=y;
        a^=b^=a^=b;
    }
    // cout<<x<<" "<<a<<" "<<y<<" "<<b<<endl;
    if(a<=y)return (a+1)%Mod*((b+1)%Mod)%Mod;
    int Res=(y+1)%Mod*((b+1)%Mod)%Mod;
    if(a<=N-10)return ((Res+Sum[a])%Mod-Sum[y]+Mod)%Mod;
    else if(y<N-10)Res=((Res+Sum[N-10])%Mod-Sum[y]+Mod)%Mod;
    int h=sqrt(K/a);
    Res=(Res+S[h+1])%Mod;
    return (Res+1LL*(h+1)*((a-L[h]+1)%Mod)%Mod)%Mod;
}
int main(){
    // freopen("tower.in","r",stdin);
    // freopen("tower.out","w",stdout);
    read(n,K);
    P[cnt=1]=0,Init(N-10);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(a[i]!=-1)
            P[++cnt]=i;
    }
    P[++cnt]=n+1;
    for(int i=2;i<=cnt;i++)
        if(P[i]-P[i-1]==1){
            if(Check(a[P[i-1]],a[P[i]]))
                return Write("0\n"),0;
        }
        else if(P[i]-P[i-1]==2){
            if(a[P[i]]==0&&a[P[i-1]]==0)Fl=true;
            else Res=1LL*Res*((Get(max(a[P[i-1]],a[P[i]]))+1)%Mod)%Mod;
        }
        else{
            if(a[P[i]]==0||a[P[i-1]]==0)Fl=true;
            else Res=1LL*Res*Solve(a[P[i-1]],a[P[i]])%Mod;
        }
    Fl?Write("-1\n"):Write(Res,'\n');
}

詳細信息

Test #1:

score: 100
Accepted
time: 6ms
memory: 15036kb

input:

4 100
-1 7 2 -1

output:

104

result:

ok 1 number(s): "104"

Test #2:

score: 0
Accepted
time: 8ms
memory: 15424kb

input:

4 100
10 -1 -1 1

output:

240

result:

ok 1 number(s): "240"

Test #3:

score: 0
Accepted
time: 5ms
memory: 15140kb

input:

1 0
-1

output:

-1

result:

ok 1 number(s): "-1"

Test #4:

score: 0
Accepted
time: 8ms
memory: 13888kb

input:

2 10
10 10

output:

0

result:

ok 1 number(s): "0"

Test #5:

score: 0
Accepted
time: 6ms
memory: 14112kb

input:

7 1000
-1 25 0 388 -1 -1 1

output:

14014

result:

ok 1 number(s): "14014"

Test #6:

score: 0
Accepted
time: 8ms
memory: 15716kb

input:

10 1000000
-1 71350 0 6 -1 2 2 -1 -1 358968

output:

652782809

result:

ok 1 number(s): "652782809"

Test #7:

score: 0
Accepted
time: 13ms
memory: 31404kb

input:

7 1000000000000000000
-1 193562447565998153 0 10833 -1 -1 12700

output:

429385005

result:

ok 1 number(s): "429385005"

Test #8:

score: 0
Accepted
time: 8ms
memory: 14152kb

input:

100 1000
-1 174 2 -1 -1 1 2 -1 -1 2 139 -1 -1 1 4 -1 -1 1 1 -1 -1 4 18 -1 -1 356 1 -1 -1 31 1 -1 -1 1 2 -1 -1 1 7 -1 -1 2 0 509 -1 -1 174 0 22 -1 -1 1 1 -1 -1 801 0 2 -1 -1 6 2 -1 -1 1 23 -1 -1 446 0 927 -1 -1 635 1 -1 -1 513 0 5 -1 -1 2 6 -1 -1 2 1 -1 -1 839 0 342 -1 -1 8 1 -1 -1 2

output:

240069117

result:

ok 1 number(s): "240069117"

Test #9:

score: 0
Accepted
time: 7ms
memory: 14064kb

input:

100 1000000
2 -1 -1 257208 1 -1 -1 80 14 -1 -1 20 113 -1 -1 2 155991 -1 -1 1 805463 -1 -1 734 1 -1 -1 942182 0 3 -1 -1 1 1 -1 -1 3 88674 -1 -1 718 0 793 -1 -1 540 1 -1 -1 1 893042 -1 -1 891 0 491 -1 -1 6 18 -1 -1 1 735332 -1 -1 1 1 -1 -1 231702 0 22 -1 -1 1 476 -1 -1 826 20 -1 -1 1 29 -1 -1 2 989 -1...

output:

279593366

result:

ok 1 number(s): "279593366"

Test #10:

score: 0
Accepted
time: 17ms
memory: 33876kb

input:

97 1000000000000000000
-1 55 1 -1 -1 844479880 0 123881535849416001 -1 -1 128083297778537531 1 -1 -1 171572811 0 352900396625380054 -1 -1 1 1 -1 -1 41 6 -1 -1 21627 155 -1 643122694 0 392322295 -1 -1 254987357 2 -1 -1 4 0 571457328786259212 -1 -1 1 8816 -1 -1 131254846109630352 0 971779784498766346 ...

output:

188490398

result:

ok 1 number(s): "188490398"

Test #11:

score: 0
Accepted
time: 23ms
memory: 22620kb

input:

999998 1000
-1 343 1 -1 -1 1 3 -1 -1 1 1 -1 -1 2 0 468 -1 -1 1 1 -1 -1 783 0 5 -1 -1 2 0 760 -1 -1 318 1 -1 -1 1 320 -1 -1 27 1 -1 -1 2 2 -1 -1 2 1 -1 -1 997 1 -1 -1 547 0 313 -1 -1 4 0 304 -1 -1 1 4 -1 -1 980 0 96 -1 -1 1 797 -1 -1 13 0 13 -1 -1 19 0 401 -1 -1 1 1 -1 -1 5 5 -1 -1 26 0 458 -1 -1 6 0...

output:

104236068

result:

ok 1 number(s): "104236068"

Test #12:

score: 0
Accepted
time: 23ms
memory: 24492kb

input:

999998 1000000
-1 538406 1 -1 -1 1 2 -1 -1 288 0 393 -1 -1 256582 0 111893 -1 1 1 -1 -1 105454 0 40 -1 -1 1 4 -1 -1 6 1 -1 -1 3 0 588226 -1 -1 2 22 -1 -1 1 477043 -1 -1 2 912 -1 -1 3 0 539669 -1 -1 1 1 -1 -1 597 0 423 -1 -1 717193 0 506800 -1 -1 424362 0 523732 -1 -1 411789 0 2 -1 -1 2 0 681371 -1 -...

output:

945384981

result:

ok 1 number(s): "945384981"

Test #13:

score: 0
Accepted
time: 33ms
memory: 40792kb

input:

999999 1000000000000000000
34 -1 -1 10403 0 945252394656439232 -1 -1 11 3 -1 -1 2789 153814328 -1 -1 685484514683924741 1 -1 -1 1 14600 -1 -1 162108378 0 942407706831037158 -1 -1 1 81 -1 -1 286801961 1 -1 -1 13177 356030442 -1 -1 9557 0 647686052355282463 -1 -1 797322887 0 33989350 -1 -1 31337243480...

output:

727350500

result:

ok 1 number(s): "727350500"

Test #14:

score: 0
Accepted
time: 8ms
memory: 15348kb

input:

50 1000
-1 -1 -1 694 26 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 -1 -1 555 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

output:

0

result:

ok 1 number(s): "0"

Test #15:

score: 0
Accepted
time: 17ms
memory: 38812kb

input:

1000000 1000000000000000000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

-1

result:

ok 1 number(s): "-1"

Test #16:

score: 0
Accepted
time: 5ms
memory: 15508kb

input:

50 1000
210 -1 -1 -1 -1 -1 836 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 517 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 31 -1 128 -1 -1 -1 -1

output:

0

result:

ok 1 number(s): "0"

Test #17:

score: 0
Accepted
time: 18ms
memory: 38720kb

input:

1000000 1000000000000000000
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...

output:

0

result:

ok 1 number(s): "0"

Test #18:

score: 0
Accepted
time: 8ms
memory: 15700kb

input:

7 100
-1 101 0 1 -1 -1 40

output:

202

result:

ok 1 number(s): "202"

Test #19:

score: 0
Accepted
time: 9ms
memory: 14976kb

input:

17 20
2 -1 -1 2 3 -1 -1 1 3 -1 -1 21 0 5 -1 -1 1

output:

186624

result:

ok 1 number(s): "186624"

Test #20:

score: 0
Accepted
time: 7ms
memory: 16968kb

input:

8 1000000000000
5 -1 -1 2 1 -1 -1 2

output:

667440443

result:

ok 1 number(s): "667440443"

Test #21:

score: 0
Accepted
time: 8ms
memory: 17196kb

input:

4 1000000000000
5 -1 -1 2

output:

709877272

result:

ok 1 number(s): "709877272"

Test #22:

score: 0
Accepted
time: 7ms
memory: 17416kb

input:

4 1000000000000
1 -1 -1 2

output:

232569899

result:

ok 1 number(s): "232569899"