QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#791340#9738. Make It DivisibleLinx#TL 1ms3816kbC++172.4kb2024-11-28 18:09:402024-11-28 18:09:44

Judging History

你现在查看的是最新测评结果

  • [2024-11-28 18:09:44]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3816kb
  • [2024-11-28 18:09:40]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;



void solve() {
    int n, k;
    cin >> n >> k;
    std::vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) {
        cin >> a[i];
    }
    bool ok = 1;
    for(int i = 1; i <= n; i ++ ) {
        if(a[i] != a[1]) {
            ok = 0;
            break;
        }
    }
    if(ok) {
        cout << k << ' ' << (ll)(k + 1) * k / 2 << '\n';
        return ;
    }
    deque<int> dq;
    vector<pii> b;
    for(int i = 1; i <= n; i ++ ) {
        while(dq.size() && dq.back() >= a[i]) {
            dq.pop_back();
        }
        if(dq.size()) {
            b.push_back({dq.back(), a[i]});
        }
        dq.push_back(a[i]);
    }
    while(dq.size()) dq.pop_back();
    for(int i = n; i >= 1; i -- ) {
        while(dq.size() && dq.back() >= a[i]) {
            dq.pop_back();
        }
        if(dq.size()) {
            b.push_back({dq.back(), a[i]});
        }
        dq.push_back(a[i]);
    }
    bool fg = 0;
    set<int> st;
    for(auto &[x, y] : b) {
        swap(x, y);
        int tmp = x - y;
        if(!fg) {
            for(int i = 1; i <= tmp / i; i ++ ) {
                if(tmp % i == 0) {
                    if(tmp / i > y && tmp / i - y <= k) {
                        st.insert(tmp / i - y);
                    }
                    if(i > y && i - y <= k) {
                        st.insert(i - y);
                    }
                }
            }
            fg = 1;
        } else {
            set<int> st2;
            for(int i = 1; i <= tmp / i; i ++ ) {
                if(tmp % i == 0) {
                    if(tmp / i > y && tmp / i - y <= k && st.find(tmp / i - y) != st.end()) {
                        st2.insert(tmp / i - y);
                    }
                    if(i > y && i - y <= k && st.find(i - y) != st.end()) {
                        st2.insert(i - y);
                    }
                }
            }
            swap(st, st2);
        }
    }
    cout << st.size() << ' ';
    ll tot = 0;
    for(auto x : st) {
        tot += x;
    }
    cout << tot << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int t = 1;
    cin >> t;
    while(t -- ) {
        solve();
    }
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 0ms
memory: 3504kb

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: 1ms
memory: 3560kb

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: -100
Time Limit Exceeded

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:


result: