QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#854141#9738. Make It Divisibleucup-team3474#WA 15ms18648kbC++232.7kb2025-01-11 21:56:202025-01-11 21:56:20

Judging History

This is the latest submission verdict.

  • [2025-01-11 21:56:20]
  • Judged
  • Verdict: WA
  • Time: 15ms
  • Memory: 18648kb
  • [2025-01-11 21:56:20]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k;
ll a[N],b[N];
ll c[N];
ll res[N];

typedef struct{
    int l,r;
    ll gg;
}Node;
Node tr[N];


ll Cal(ll x,ll y){
    if(x==0||y==0) return max(x,y);
    return __gcd(x,y);
}

void pushup(int u){
    // if(tr[u<<1].gg==0||tr[u])
    tr[u].gg=Cal(tr[u<<1].gg,tr[u<<1|1].gg);
}

void build(int u,int l,int r){
    tr[u]={l,r};
    if(l==r){
        tr[u].gg=c[l];
    }else{
        int mid=l+r>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
}

ll query(int u,int l,int r){
    if(l>r) return 0; 
    if(tr[u].l>=l&&tr[u].r<=r){
        return tr[u].gg;
    } else{
        int mid=tr[u].l+tr[u].r>>1;
        ll ans=0;
        if(l<=mid) ans=Cal(ans,query(u<<1,l,r));
        if(r>mid) ans=Cal(ans,query(u<<1|1,l,r));
        return ans;
    }
}


bool check(){
    for(int i=1;i<=n;i++){
        if(a[i]!=a[1]) return false;
    }
    return true;
}

bool Check(ll x){
    // cout<<x<<endl;
    if(x<=0) return false;
    // cout<<x<<endl;
    for(int i=1;i<=n;i++){
        // cout<<res[i]<<" "<<a[i]+x<<endl;
        if(res[i]%(a[i]+x)!=0) return false;
    }
    return true;
}

int l[N],r[N];



void __(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    if(check()){
        printf("%lld %lld\n",k,k*(1+k)/2);
        return;
    }
    for(int i=1;i<n;i++) c[i]=abs(a[i]-a[i+1]);
    build(1,1,n-1);
    // map<int,vector<int>> mp;
    // for(int i=1;i<=n;i++) mp[a[i]].push_back(i);
    stack<int> st;
    st.push(0);
    a[0]=-1000000007,a[n+1]=-1000000007;
    for(int i=1;i<=n;i++){
        while(st.size()&&a[i]<=a[st.top()]) st.pop();
        l[i]=st.top()+1;
        st.push(i);
    }
    while(st.size()) st.pop();
    st.push(n+1);
    for(int i=n;i>=1;i--){
        while(st.size()&&a[i]<=a[st.top()]) st.pop();
        r[i]=st.top()-1;
        st.push(i);
    }
    
    // for(int i=1;i<=n;i++) cout<<l[i]<<" "<<r[i]<<endl;
    for(int i=1;i<=n;i++) res[i]=query(1,l[i],r[i]-1);
    // for(int i=1;i<=n;i++) cout<<res[i]<<" ";
    // cout<<endl;
    ll val=query(1,1,n);
    ll mn=1e9+7;
    for(int i=1;i<=n;i++) mn=min(mn,a[i]);
    ll ans1=0,ans2=0;
    // cout<<val<<endl;
    for(int i=1;i<=val/i;i++){
        if(Check(i-mn)){
            ans1++;
            ans2+=i-mn;
        }
        if(i!=val/i){
            if(Check(val/i-mn)){
                ans1++;
                ans2+=val/i-mn;
            }
        }
    }
    printf("%lld %lld\n",ans1,ans2);
}


int main(){
    int _=1;
    cin>>_;
    while(_--){
        __();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 14328kb

input:

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

output:

3 8
0 0
100 5050

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 3ms
memory: 14068kb

input:

4
201 1000000000
1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...

output:

0 0
0 0
0 0
0 0

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 3ms
memory: 14072kb

input:

500
4 1000000000
8 14 24 18
4 1000000000
17 10 18 14
4 1000000000
6 17 19 19
4 1000000000
15 14 15 25
4 1000000000
16 16 5 25
4 1000000000
4 30 20 5
4 1000000000
11 4 23 9
4 1000000000
14 25 13 2
4 1000000000
18 18 1 15
4 1000000000
22 22 22 28
4 1000000000
15 17 17 10
4 1000000000
22 14 13 25
4 100...

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 500 lines

Test #4:

score: 0
Accepted
time: 15ms
memory: 18368kb

input:

1
50000 1000000000
230 286458 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 41263680 ...

output:

0 0

result:

ok single line: '0 0'

Test #5:

score: 0
Accepted
time: 14ms
memory: 18648kb

input:

1
50000 1000000000
12087 1196491 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 55314643 553146...

output:

0 0

result:

ok single line: '0 0'

Test #6:

score: 0
Accepted
time: 14ms
memory: 16600kb

input:

1
50000 1000000000
2138984 42249920 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 358123541 3581...

output:

0 0

result:

ok single line: '0 0'

Test #7:

score: -100
Wrong Answer
time: 15ms
memory: 14064kb

input:

500
39 1000000000
75 7 7 381 41 1197 177 177 41 109 109 16 1197 177 41 381 1605 381 381 7 177 177 177 177 177 177 177 177 7 7 143 143 143 143 143 653 143 823 7
61 1000000000
327 327 327 327 405153474 327 405153474 327 810306621 810306621 810306621 810306621 810306621 810306621 810306621 810306621 81...

output:

0 0
25 631568356
13 18925862
11 2194
2 6878
1 2
1 1
2 10
3 6873
1 110
0 0
1 36
13 19290
1 29
1 4
6 2209209
0 0
3 8
1 2
9 30770061
1000000000 500000000500000000
1 3
1000000000 500000000500000000
0 0
1 5
1 1
6 6615501
3 8233825
2 1035
2 4
7 1288
0 0
1 3
16 1617883221
2 10
0 0
1 5739
15 102584
3 1100
1...

result:

wrong answer 4th lines differ - expected: '1 1', found: '11 2194'