QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#557089#360. Cultivationmakrav30 19ms4088kbC++2014.3kb2024-09-11 02:50:442024-09-11 02:50:44

Judging History

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

  • [2024-09-11 02:50:44]
  • 评测
  • 测评结果:30
  • 用时:19ms
  • 内存:4088kb
  • [2024-09-11 02:50:44]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define pb push_back
#define ff first
#define sc second
#define int ll

const int INF = 1000000000000;

void solve() {
    int h, w, n; cin >> h >> w >> n;
    vector<pair<int, int>> a(n);
    for (int i = 0; i < n; i++) cin >> a[i].ff >> a[i].sc;
    vector<vector<bool>> gp(n, vector<bool>(n, false));
    sort(all(a), [](pair<int, int> x, pair<int, int> y) {
        return x.second < y.second;
    });
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            bool gpp = true;
            for (int k = 0; k < n; k++) {
                if (k==i||k==j)continue;
                if ((a[k].first - a[i].first) * (a[k].first - a[j].first) <= 0 && (a[k].second - a[i].second) * (a[k].second - a[j].second) <= 0) {
                    gpp = false;
                    break;
                }
            }
            gp[i][j]=gpp;
        }
    }
    vector<pair<int, int>> gps;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (gp[i][j]) {
                //cout << i << ' ' << j << '\n';
                gps.pb({i, j});
            }
        }
    }
    // for (auto &u : a) cout << u.first << ' ' << u.second << '\n';
    // for (auto &u : gps) {
    //     cout << u.first << ' ' << u.second << '\n';
    // }
    //return;
    // all above -- correct (i think)

    vector<ll> delta(sz(gps));
    vector<int> is_delta_correct(sz(gps));
    for (int i = 0; i < sz(gps); i++) {
        ll max_up = 0, min_d = h + 1;
        int mxy = max(a[gps[i].first].first, a[gps[i].second].first), mny = min(a[gps[i].first].first, a[gps[i].second].first);
        for (int j = 0; j < n; j++) {
            if (a[gps[i].first].second < a[j].second && a[j].second < a[gps[i].second].second) {
                if (a[j].first > mxy) min_d = min(min_d, (ll)a[j].first);
                else {
                    assert(a[j].first < mny);
                    max_up = max(max_up, (ll)a[j].first);
                }
            }
        }
        if (min_d == h + 1 && max_up == 0) delta[i] = INF;
        else if (min_d != h + 1 && max_up != 0) delta[i] = (min_d - max_up - 1);
        else {
            if (min_d != h + 1) {
                is_delta_correct[i] = 1;
                delta[i] = min_d - 1;
            } else {
                is_delta_correct[i] = 2;
                delta[i] = h - max_up;
            }
        }
    }

    // all above -- probably correct ..)

    vector<int> never_left(n), never_right(n);
    vector<ll> lol_left(n), lol_right(n);
    vector<int> type_left(n), type_right(n);
    for (int i = 0; i < n; i++) {
        {
            // left
            int max_up = 0, min_d = h + 1;
            for (int j = 0; j < n; j++) {
                if (a[j].second < a[i].second) {
                    if (a[j].first == a[i].first) {
                        never_left[i] = 1;
                        break;
                    }
                    if (a[j].first < a[i].first) max_up = max(max_up, a[j].first);
                    else min_d = min(min_d, a[j].first);
                }
            }
            if (min_d == h + 1 && max_up == 0) lol_left[i] = INF;
            else if (min_d != h + 1 && max_up != 0) lol_left[i] = min_d - max_up;
            else {
                if (min_d != h + 1) {
                    type_left[i] = 1;
                    lol_left[i] = min_d - 1;
                } else {
                    type_left[i] = 2;
                    lol_left[i] = h - max_up;
                }
            }
        } 
        {
            // right
            int max_up = 0, min_d = h + 1;
            for (int j = 0; j < n; j++) {
                if (a[j].second > a[i].second) {
                    if (a[j].first == a[i].first) {
                        never_right[i] = 1;
                        break;
                    }
                    if (a[j].first < a[i].first) max_up = max(max_up, a[j].first);
                    else min_d = min(min_d, a[j].first);
                }
            }
            if (min_d == h + 1 && max_up == 0) lol_right[i] = INF;
            else if (min_d != h + 1 && max_up != 0) lol_right[i] = min_d - max_up;
            else {
                if (min_d != h + 1) {
                    type_right[i] = 1;
                    lol_right[i] = min_d - 1;
                } else {
                    type_right[i] = 2;
                    lol_right[i] = h - max_up;
                }
            }
            //cout << a[i].first << ' ' << a[i].second << ' ' << type_right[i] << ' ' << never_right[i] << '\n';
        }
    }   


    // check this block above

    vector<int> ord_left(n), ord_right(n);
    iota(all(ord_left), 0); iota(all(ord_right), 0);
    sort(all(ord_left), [&](int i, int j) {
        return a[i].second < a[j].second;
    });
    sort(all(ord_right), [&](int i, int j) {
        return a[i].second > a[j].second;
    });

    vector<int> pos_left(n), pos_right(n);
    for (int i = 0; i < n; i++) {
        pos_left[ord_left[i]] = i;
        pos_right[ord_right[i]] = i;
    }
    vector<int> ups;
    for (int i = 0; i < n; i++) ups.pb(a[i].first - 1);

    // part above probably correct

    vector<int> alds;
    for (int i = 0; i < sz(gps); i++) {
        alds.pb(a[gps[i].second].second - a[gps[i].first].second - 1);
    }
    sort(all(alds));
    alds.resize(unique(all(alds)) - alds.begin());
    map<int, int> pos;
    for (int i = 0; i < sz(alds); i++) pos[alds[i]] = i;
    vector<int> ind_mid(sz(gps));
    for (int i = 0; i < sz(gps); i++) ind_mid[i] = pos[a[gps[i].second].second - a[gps[i].first].second - 1];

    // part above probably correct

    vector<int> ordp1(sz(gps)) /* order by delta of basic y values */, ordp2(sz(gps)) /* order by delta of second y values */;
    vector<int> vals(sz(gps)), W(sz(gps));
    for (int i = 0; i < sz(gps); i++) {
        vals[i] = abs(a[gps[i].first].first - a[gps[i].second].first);
        W[i] = a[gps[i].second].second - a[gps[i].first].second;
    }
    iota(all(ordp1), 0);
    sort(all(ordp1), [&](int i, int j){
        return vals[i] < vals[j];
    });
    iota(all(ordp2), 0);
    sort(all(ordp2), [&](int i, int j) {
        return delta[i] < delta[j];
    });

    vector<int> YS;
    for (int i =0;i<n;i++)YS.pb(a[i].first);
    sort(all(YS));
    int MX=0;
    for (int i=1;i<n;i++){
        MX=max(MX,YS[i]-YS[i-1]-1);
    }
    // fuck

    int need_down = INF;
    for (int i = 0; i < n; i++) need_down = min(need_down, h - a[i].first);

    auto solve = [&](int up) -> long long {
        // returns minimal answer with current up value
        vector<pair<int, int>> lefts, rights;
        vector<int> used_left(n, 0), used_right(n, 0), cnt_mid(sz(alds));
        vector<pair<int, int>> start_mid, endd_mid, endd_mid_fuck;
        for (int i = 0; i < n; i++) {
            {
                if (never_left[i]) continue;
                if (type_left[i] == 0) {
                    if (lol_left[i] - 1 <= up) continue;
                    lefts.pb({lol_left[i] - 1 - up, pos_left[i]});
                    used_left[pos_left[i]] = 1;
                } else if (type_left[i] == 1) {
                    if (up >= lol_left[i]) continue;
                    used_left[pos_left[i]] = 1;
                } else {
                    used_left[pos_left[i]] = 1;
                    lefts.pb({lol_left[i], pos_left[i]});
                }
            }
        }
        for (int i = 0; i < n; i++) {
            {
                if (never_right[i]) continue;
                if (type_right[i] == 0) {
                    if (lol_right[i] - 1 <= up) continue;
                    rights.pb({lol_right[i] - 1 - up, pos_right[i]});
                    used_right[pos_right[i]] = 1;
                } else if (type_right[i] == 1) {
                    if (up >= lol_right[i]) continue;
                    used_right[pos_right[i]] = 1;
                } else {
                    used_right[pos_right[i]] = 1;
                    //cout << a[pos_right[i]].second << "fuckk\n";
                    rights.pb({lol_right[i], pos_right[i]});
                }
                if (lol_right[i] - 1 <= up) {
                    continue;
                }
            }
        }
        sort(all(lefts)); sort(all(rights));
        int pmax_left = -1, pmax_right = -1, pmid = -1;
        auto update_left = [&]() {
            while (pmax_left >= 0 && !used_left[pmax_left]) pmax_left--;
        };
        auto update_right = [&]() {
            while (pmax_right >= 0 && !used_right[pmax_right]) pmax_right--;
        };
        auto update_mid = [&]() {
            while (pmid >= 0 && cnt_mid[pmid] <= 0) pmid--;
        };
        for (int i = 0; i < n; i++) {
            if (used_left[i]) pmax_left = i;
            if (used_right[i]) pmax_right = i;
        }
        vector<int> E0;
        for (int i = 0; i < sz(gps); i++) {
            int j = ordp2[i];
            if (is_delta_correct[j] == 0) {
                endd_mid.pb({ind_mid[j], max(0ll, delta[j] - up)});
            } else if (is_delta_correct[j] == 1) {
                if (up >= delta[j]) {
                    E0.pb(ind_mid[j]);
                }
            } else {
                endd_mid_fuck.pb({ind_mid[j], delta[j]});
            }
            start_mid.pb({ind_mid[ordp1[i]], max(0ll, vals[ordp1[i]] - up)});
        }

        // for (int i = 0; i < sz(gps); i++) {
        //     if (is_delta_correct[ordp2[i]]) {
        //         endd_mid.pb({ind_mid[ordp2[i]], delta[ordp2[i]]});
        //     } else {

        //     }
        //     if (delta[ordp2[i]] > up) endd_mid.pb({ind_mid[ordp1[i]], delta[ordp2[i]] - up});
        // }
        int ind_start = 0, ind_endd = 0, ind_endd_fuck = 0, ind_left = 0, ind_right = 0;
        for (int F : E0) {
            cnt_mid[F]--;
        }
        while (ind_start < sz(start_mid) && start_mid[ind_start].second == 0) {
            cnt_mid[start_mid[ind_start].first]++;
            ind_start++;
        }
        while (ind_endd_fuck < sz(endd_mid_fuck) && endd_mid_fuck[ind_endd_fuck].second == 0) {
            cnt_mid[endd_mid_fuck[ind_endd_fuck].first]--;
            ind_endd_fuck++;
        }
        while (ind_endd < sz(endd_mid) && endd_mid[ind_endd].second == 0) {
            cnt_mid[endd_mid[ind_endd].first]--;
            ind_endd++;
        }
        while (ind_left < sz(lefts) && lefts[ind_left].first == 0) {
            used_left[lefts[ind_left].second] = 0;
            ind_left++;
        }
        while (ind_right < sz(rights) && rights[ind_right].first == 0) {
            used_right[rights[ind_right].second] = 0;
            ind_right++;
        }
        update_left(); update_right();
        for (int i = 0; i < sz(alds); i++) {
            if (cnt_mid[i] > 0) pmid = i;
        }
        int NEW_NEED = max(need_down, MX-up);
        int A = 4 * INF;
        int pl = (pmax_left == -1 ? 0 : a[ord_left[pmax_left]].second - 1), pr = (pmax_right == -1 ? 0 : w - a[ord_right[pmax_right]].second), 
                     pm = (pmid == -1 ? 0 : alds[pmid]);
        if (NEW_NEED == 0) {
            A = min(A, max(pl+pr,pm));
        }
        //cout<<up<<" moment zero " << pl << ' ' << pr << ' ' << pm << '\n';
        int pmnt=-1;
        //cout << up << " start shit " << pl << ' ' << pr << ' ' << pm << '\n';
        while (ind_start < sz(start_mid) || ind_endd_fuck < sz(endd_mid_fuck) || ind_left < sz(lefts) || ind_right < sz(rights) || ind_endd < sz(endd_mid)) {
            int mnt = 4 * INF;
            if (ind_start < sz(start_mid)) mnt = min(mnt, start_mid[ind_start].second);
            if (ind_left < sz(lefts)) mnt = min(mnt, lefts[ind_left].first);
            if (ind_right < sz(rights)) mnt = min(mnt, rights[ind_right].first);
            if (ind_endd < sz(endd_mid)) mnt = min(mnt, endd_mid[ind_endd].second);
            if (ind_endd_fuck < sz(endd_mid_fuck)) mnt = min(mnt, endd_mid_fuck[ind_endd_fuck].second);

            while (ind_start < sz(start_mid) && start_mid[ind_start].second == mnt) {
                cnt_mid[start_mid[ind_start].first]++;
                ind_start++;
            }
            while (ind_endd < sz(endd_mid) && endd_mid[ind_endd].second == mnt) {
                cnt_mid[endd_mid[ind_endd].first]--;
                ind_endd++;
            }
            while (ind_endd_fuck < sz(endd_mid_fuck) && endd_mid_fuck[ind_endd_fuck].second == mnt) {
                cnt_mid[endd_mid_fuck[ind_endd_fuck].first]--;
                ind_endd_fuck++;
            }
            while (ind_left < sz(lefts) && lefts[ind_left].first == mnt) {
                used_left[lefts[ind_left].second] = 0;
                ind_left++;
            }
            while (ind_right < sz(rights) && rights[ind_right].first == mnt) {
                used_right[rights[ind_right].second] = 0;
                ind_right++;
            }
            update_left(); update_mid(); update_right();
            int cl = (pmax_left == -1 ? 0 : a[ord_left[pmax_left]].second - 1), cr = (pmax_right == -1 ? 0 : w - a[ord_right[pmax_right]].second), 
                     cmid = (pmid == -1 ? 0 : alds[pmid]);
            //cout << up << ' ' << mnt << ' ' << cl << ' ' << cr << ' ' << cmid << '\n';
            if (mnt >= NEW_NEED) {
                A = min(A, mnt + max(cl + cr, cmid));
                // if (mnt+max(cl+cr,cmid) == 1){
                //     cout<<"FUCKCKKKCKCKC " << up << ' ' << mnt << '\n';
                // }
                if (mnt > NEW_NEED && pmnt <= NEW_NEED) {
                    A=min(A, NEW_NEED+max(pl+pr,pm));
                }
            }
            pmnt=mnt;
            pm=cmid;
            pl=cl;
            pr=cr;
        }
        return A + up;
    };  

    ll ans = 4000000000;
    for (int up : ups) {
        ans = min(ans, solve(up));
    }
    cout << ans << '\n';
}

signed main() {
    int tt = 1;
    #ifdef LOCAL 
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        cin >> tt;
    #else
        ios::sync_with_stdio(false); 
        cin.tie(0); cout.tie(0);
    #endif

    while (tt--) {
        solve();
    }

    return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

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

input:

2 4
2
1 1
1 4

output:

3

result:

ok single line: '3'

Test #2:

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

input:

4 1
1
2 1

output:

3

result:

ok single line: '3'

Test #3:

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

input:

3 3
3
1 2
1 3
3 3

output:

3

result:

ok single line: '3'

Test #4:

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

input:

2 2
1
1 2

output:

2

result:

ok single line: '2'

Test #5:

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

input:

4 4
10
4 2
2 3
2 4
4 1
1 2
2 1
4 3
3 3
3 1
1 4

output:

2

result:

ok single line: '2'

Test #6:

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

input:

4 4
1
4 1

output:

6

result:

ok single line: '6'

Test #7:

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

input:

4 4
3
2 2
3 3
1 4

output:

5

result:

ok single line: '5'

Test #8:

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

input:

4 4
15
4 3
2 4
4 4
4 1
3 3
1 2
3 1
2 1
3 4
3 2
4 2
2 3
1 3
2 2
1 4

output:

1

result:

ok single line: '1'

Test #9:

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

input:

4 3
3
2 1
2 3
4 1

output:

3

result:

ok single line: '3'

Test #10:

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

input:

4 4
2
3 4
2 4

output:

5

result:

ok single line: '5'

Test #11:

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

input:

2 4
1
1 2

output:

4

result:

ok single line: '4'

Test #12:

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

input:

3 3
4
2 1
1 1
3 2
3 1

output:

2

result:

ok single line: '2'

Test #13:

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

input:

3 4
3
1 4
3 3
3 4

output:

4

result:

ok single line: '4'

Test #14:

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

input:

3 3
2
2 1
3 3

output:

4

result:

ok single line: '4'

Test #15:

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

input:

4 4
2
2 4
3 1

output:

6

result:

ok single line: '6'

Test #16:

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

input:

4 4
3
2 2
2 1
4 2

output:

4

result:

ok single line: '4'

Subtask #2:

score: 10
Accepted

Dependency #1:

100%
Accepted

Test #17:

score: 10
Accepted
time: 0ms
memory: 3580kb

input:

15 15
20
6 13
14 4
11 13
15 3
12 4
10 4
11 6
8 9
12 12
2 15
4 3
8 15
8 4
3 1
5 10
11 12
8 7
13 10
11 4
1 3

output:

13

result:

ok single line: '13'

Test #18:

score: 10
Accepted
time: 1ms
memory: 3608kb

input:

25 25
66
24 6
12 18
11 2
24 18
6 9
20 6
15 19
17 2
15 9
15 20
18 9
5 19
9 2
6 12
22 16
6 2
1 5
14 24
12 21
17 24
10 15
21 1
20 22
11 24
11 4
6 21
18 12
25 20
16 3
18 16
6 4
20 9
6 15
24 14
3 20
9 9
25 9
18 6
4 16
12 7
14 22
20 25
24 10
11 14
17 6
23 23
21 12
18 22
8 23
1 11
17 18
8 5
3 7
1 17
8 12
4...

output:

9

result:

ok single line: '9'

Test #19:

score: 10
Accepted
time: 1ms
memory: 3896kb

input:

36 38
28
30 5
4 23
29 20
1 36
8 28
8 9
5 26
23 16
26 1
24 38
22 36
4 26
9 7
10 24
20 11
31 5
24 30
26 30
18 15
14 1
23 31
20 7
23 30
33 9
27 33
8 7
9 16
33 5

output:

30

result:

ok single line: '30'

Test #20:

score: 10
Accepted
time: 0ms
memory: 3872kb

input:

10 40
19
7 5
8 38
4 7
8 5
4 30
1 33
1 16
2 21
8 33
4 36
6 20
6 27
4 14
10 15
9 30
8 13
4 15
10 9
5 22

output:

17

result:

ok single line: '17'

Test #21:

score: 10
Accepted
time: 1ms
memory: 3664kb

input:

40 30
50
19 20
18 16
34 28
5 8
28 21
24 13
7 1
28 23
28 18
12 6
3 6
18 8
40 27
22 19
23 22
8 6
9 12
16 10
27 25
26 19
4 9
40 26
21 22
10 8
5 2
30 25
12 12
3 1
24 14
5 3
4 8
19 9
21 16
6 3
38 29
27 20
37 25
36 24
22 20
29 26
30 19
16 14
3 3
39 25
5 7
20 15
13 12
33 30
27 16
25 14

output:

50

result:

ok single line: '50'

Test #22:

score: 10
Accepted
time: 2ms
memory: 3596kb

input:

40 40
120
23 22
31 36
2 4
2 32
14 40
23 32
18 11
27 36
7 1
25 33
22 40
34 9
26 20
18 7
35 7
3 17
19 6
5 27
19 30
33 15
2 15
19 15
4 8
27 1
8 27
10 2
11 39
31 27
32 35
17 4
18 22
2 7
7 10
5 14
40 23
3 36
6 6
6 15
21 35
27 39
25 1
40 11
36 16
8 23
35 27
18 21
24 39
13 22
4 3
12 17
31 16
3 6
6 4
3 30
2...

output:

16

result:

ok single line: '16'

Test #23:

score: 10
Accepted
time: 1ms
memory: 3668kb

input:

40 40
33
10 22
10 3
7 11
12 14
11 12
1 21
6 23
3 11
8 24
3 40
8 14
7 25
8 15
12 3
10 7
4 32
7 32
9 32
9 30
4 22
8 22
11 24
6 19
10 16
10 2
9 4
10 15
9 28
7 1
4 31
7 35
4 18
2 35

output:

46

result:

ok single line: '46'

Test #24:

score: 10
Accepted
time: 6ms
memory: 3676kb

input:

40 40
200
10 16
27 15
18 11
16 25
34 7
39 25
26 15
12 20
8 1
20 14
25 27
33 4
29 40
20 33
8 9
32 16
37 25
34 27
31 23
30 8
40 30
35 37
27 7
18 27
36 30
13 30
12 32
32 4
15 21
29 39
4 32
8 7
12 21
35 40
32 29
34 17
22 30
12 34
34 39
23 16
27 16
13 26
28 32
8 31
30 16
13 25
28 13
19 35
38 35
2 40
7 1
...

output:

14

result:

ok single line: '14'

Test #25:

score: 10
Accepted
time: 0ms
memory: 3744kb

input:

40 40
150
8 38
27 32
34 14
29 32
16 36
29 19
40 30
30 22
34 12
4 30
24 37
14 8
31 21
40 17
38 25
16 5
29 5
38 29
28 10
2 5
5 16
20 11
38 6
21 11
5 8
26 13
21 35
27 27
10 11
18 30
30 40
8 18
31 5
16 7
3 1
35 36
40 26
18 39
25 8
19 16
17 26
6 20
13 30
34 4
35 8
33 4
25 29
39 7
22 40
10 36
26 3
30 14
1...

output:

16

result:

ok single line: '16'

Test #26:

score: 10
Accepted
time: 9ms
memory: 3848kb

input:

40 40
300
5 29
4 30
10 5
19 1
11 37
8 26
2 12
29 25
13 33
4 36
15 9
6 39
27 35
34 14
35 27
32 26
14 35
23 35
23 34
12 6
2 21
20 29
20 23
5 21
15 11
7 13
6 23
33 7
19 22
20 31
28 25
7 18
15 39
25 1
2 16
5 23
5 28
7 21
5 31
8 29
16 14
18 29
16 3
3 23
20 35
24 34
14 4
14 30
39 18
25 5
19 37
28 10
7 11
...

output:

18

result:

ok single line: '18'

Test #27:

score: 10
Accepted
time: 13ms
memory: 3772kb

input:

40 40
300
23 5
15 1
34 20
36 22
19 4
31 19
11 34
13 33
3 20
18 4
27 10
37 21
14 11
30 34
8 29
6 26
32 33
8 10
1 14
40 40
4 22
19 31
6 28
37 16
22 34
38 17
16 2
18 36
12 4
38 15
1 24
1 18
32 8
6 18
35 26
12 36
25 2
38 20
19 3
25 12
2 34
35 22
10 36
26 3
10 22
36 8
29 33
3 39
5 10
7 9
36 14
24 5
5 21
...

output:

14

result:

ok single line: '14'

Test #28:

score: 10
Accepted
time: 6ms
memory: 3792kb

input:

39 40
200
9 40
2 33
16 32
14 33
14 27
3 28
5 31
36 30
15 22
23 17
22 28
13 10
4 14
24 35
4 35
12 22
28 32
8 37
7 31
1 37
28 21
39 22
12 17
7 20
35 16
10 12
12 6
27 31
33 15
19 16
13 35
26 35
10 19
15 25
18 19
21 9
11 9
39 4
3 31
20 24
37 26
22 38
13 40
18 12
29 4
31 2
10 26
2 39
2 3
18 9
14 34
39 23...

output:

15

result:

ok single line: '15'

Test #29:

score: 10
Accepted
time: 15ms
memory: 3848kb

input:

38 38
300
30 33
11 38
6 10
19 20
29 30
1 18
30 20
11 19
23 15
32 3
32 30
5 34
7 30
34 1
5 4
20 35
8 13
25 32
12 2
6 3
1 19
38 7
35 16
14 9
37 2
10 4
13 21
37 17
34 4
20 20
14 12
20 13
36 3
10 33
5 8
23 23
9 22
17 19
13 9
20 14
31 4
11 23
17 32
12 10
21 23
31 11
17 35
12 17
31 27
3 6
10 37
2 38
5 15
...

output:

9

result:

ok single line: '9'

Test #30:

score: 10
Accepted
time: 15ms
memory: 3820kb

input:

40 40
300
25 27
25 10
20 19
16 40
29 29
39 20
3 4
6 20
20 6
1 25
39 32
28 26
27 17
30 38
4 33
27 24
21 4
36 32
29 7
4 23
39 2
40 6
14 40
33 39
23 32
23 34
18 6
36 28
40 4
15 28
13 33
34 3
4 35
20 29
38 36
7 24
5 25
20 3
37 13
40 26
5 9
40 36
24 26
16 14
8 28
37 6
24 16
7 3
28 28
34 13
34 36
29 12
13...

output:

10

result:

ok single line: '10'

Test #31:

score: 10
Accepted
time: 15ms
memory: 3856kb

input:

40 40
300
31 12
30 38
21 17
11 12
1 28
10 37
10 13
5 22
18 21
28 37
23 40
29 32
21 33
5 3
21 24
14 15
2 23
9 33
15 31
38 12
37 8
37 26
1 5
28 34
22 10
18 29
30 39
23 34
25 37
35 1
10 7
25 11
10 38
34 30
18 1
12 1
10 25
16 11
35 40
26 30
5 15
23 3
22 22
16 4
8 21
12 23
24 29
4 27
40 5
18 15
35 38
1 1...

output:

9

result:

ok single line: '9'

Test #32:

score: 10
Accepted
time: 15ms
memory: 3744kb

input:

40 40
300
24 6
26 15
30 7
10 12
17 17
7 25
36 26
19 39
32 10
20 1
16 1
34 1
23 19
10 38
40 7
13 39
25 27
28 25
39 18
25 20
17 3
32 28
10 4
6 3
12 16
29 35
13 12
29 16
2 35
6 15
19 7
1 32
18 24
13 18
1 31
28 31
29 12
19 4
20 10
1 3
6 38
1 10
27 14
33 26
1 12
8 31
9 39
22 21
8 39
37 3
26 33
25 10
32 4...

output:

11

result:

ok single line: '11'

Subtask #3:

score: 15
Accepted

Dependency #2:

100%
Accepted

Test #33:

score: 15
Accepted
time: 5ms
memory: 3744kb

input:

2 200000000
300
1 88265857
1 174408185
1 105379902
1 185252998
2 30206021
2 102367431
2 89739523
1 116153736
2 68837704
1 110817136
2 26646126
2 86276690
1 127329134
2 126441765
1 19927577
1 38738747
1 105161585
1 60367988
2 67085969
1 1865971
1 27164731
1 77127255
2 168438218
1 4482768
1 197852914
...

output:

3425851

result:

ok single line: '3425851'

Test #34:

score: 15
Accepted
time: 7ms
memory: 3704kb

input:

40 1000000000
300
20 483437001
11 245274001
5 80864001
2 7139001
36 895164001
32 773938001
27 666531001
36 894646001
20 467811001
36 877372001
4 76683001
25 599539001
25 604099001
34 834882001
6 105503001
12 279215001
27 655684001
16 364895001
19 439732001
4 61698001
39 973882001
38 925548001
28 684...

output:

19162076

result:

ok single line: '19162076'

Test #35:

score: 15
Accepted
time: 18ms
memory: 3888kb

input:

40 1000000000
300
38 393750001
12 93750001
33 31250002
18 68749999
36 631250003
14 581250003
37 843750003
39 31250001
17 6250002
11 481250000
3 818750001
37 568750002
20 281250001
36 731249999
3 731250003
30 206250000
14 893750002
18 618749999
2 868750003
9 243750003
9 781250000
39 168749999
37 8687...

output:

12500068

result:

ok single line: '12500068'

Test #36:

score: 15
Accepted
time: 18ms
memory: 4080kb

input:

40 1000000000
300
20 273611973
30 962515424
19 457562756
14 228419368
9 839242624
34 416448186
6 49326057
27 373662328
18 43718671
40 180109032
35 703858821
6 62818768
23 176704786
30 419420243
29 966647309
30 971207395
9 471992569
17 18782375
28 524707582
15 887562815
20 339788418
40 188122260
33 1...

output:

25840886

result:

ok single line: '25840886'

Test #37:

score: 15
Accepted
time: 18ms
memory: 4004kb

input:

35 1000000000
300
26 304985784
31 53820856
34 188129610
32 933853739
29 435634084
16 233290946
24 581180249
14 763935773
10 265931834
9 274498426
16 675425485
15 87227536
21 985415295
14 272012946
12 765102757
24 458857877
20 610373170
25 928877042
32 589674594
23 467914943
31 693779625
19 197133223...

output:

14686151

result:

ok single line: '14686151'

Test #38:

score: 15
Accepted
time: 19ms
memory: 4088kb

input:

40 1000000000
300
6 786763464
27 418721225
37 714875337
10 156646263
9 190541536
30 429336661
7 865464196
28 815774814
35 25779712
30 681279351
11 395942851
13 574687654
29 137106802
33 754832787
37 294845778
19 815900516
14 704212093
36 198711902
17 533523161
34 748841831
17 981957453
30 294955278
...

output:

21233330

result:

ok single line: '21233330'

Test #39:

score: 15
Accepted
time: 17ms
memory: 4064kb

input:

40 1000000000
300
40 70731728
31 860477266
8 270731733
14 56097551
5 524390251
21 148780485
6 60975598
26 612195132
13 997560998
36 426829256
32 7317081
1 256097581
25 457312359
12 241463431
5 85365829
18 4440737
1 436585368
34 39238855
33 625252064
1 143902436
13 338440011
25 334146355
5 515606983
...

output:

4878171

result:

ok single line: '4878171'

Test #40:

score: 15
Accepted
time: 18ms
memory: 3952kb

input:

40 1000000000
300
34 290272040
11 654139182
15 574182947
32 483616706
23 30659851
7 688206175
33 677483533
20 245930698
16 854673531
5 415424827
23 516937655
2 347957583
4 76422831
29 693454243
24 109103102
19 755284863
16 509051878
8 373221893
35 422824677
1 923039234
37 493392984
2 648194620
12 12...

output:

23360164

result:

ok single line: '23360164'

Test #41:

score: 15
Accepted
time: 6ms
memory: 3824kb

input:

40 999992811
300
40 756167738
1 755422093
1 756075552
40 755448533
40 755699260
1 755699433
40 756570280
40 755364761
1 755246371
40 756081840
1 756154293
1 756152536
1 755866341
1 755312497
40 755640274
7 340135464
3 953017751
1 755712914
1 755664483
40 755797029
9 969531054
40 755779575
1 75564995...

output:

129414313

result:

ok single line: '129414313'

Test #42:

score: 15
Accepted
time: 11ms
memory: 3720kb

input:

40 1000000000
300
17 999998001
1 999997965
1 999997890
1 7932
5 505323503
40 999998121
1 999998027
1 999998002
9 999997972
1 999997920
40 999997891
30 7999
29 7999
31 999998062
1 999998144
40 999997890
40 999998033
1 999998006
21 999997999
40 999998031
40 8094
40 999997995
13 999998024
40 999997875
...

output:

209640461

result:

ok single line: '209640461'

Test #43:

score: 15
Accepted
time: 10ms
memory: 3980kb

input:

40 1000000000
300
23 549509844
40 95786908
40 39290135
13 992491098
26 87052294
40 231331522
19 288109792
23 482918072
1 27192653
25 931473083
40 1
12 695623563
8 518257580
1 40343403
40 271412132
40 24291430
1 776119616
29 837580112
5 24636122
2 883373187
31 209930451
37 133788324
1 224219724
1 138...

output:

21898080

result:

ok single line: '21898080'

Test #44:

score: 15
Accepted
time: 17ms
memory: 3992kb

input:

40 1000000000
300
6 366666665
15 300000001
24 233333337
1 966666667
25 853754960
23 766666669
30 233333334
24 433333334
15 566666670
14 233333334
34 233333335
32 166666668
37 366666664
30 337173509
30 100000002
31 33333334
17 500000004
15 834459573
22 773895258
32 900000001
35 100000002
40 500000001...

output:

53549258

result:

ok single line: '53549258'

Subtask #4:

score: 0
Wrong Answer

Test #45:

score: 30
Accepted
time: 1ms
memory: 3636kb

input:

1000000000 1000000000
17
822413671 70423910
260075513 431043546
300945721 793553248
142848049 163787897
392462410 831950868
699005697 111397300
444396260 130450496
642691616 595456084
467968916 463598810
159764248 611476406
929313754 539645102
365153650 964108073
906780716 373514044
970118116 655138...

output:

852626202

result:

ok single line: '852626202'

Test #46:

score: 30
Accepted
time: 1ms
memory: 3584kb

input:

1000000000 1000000000
24
382358372 812500277
617637090 687506454
441176760 562497727
382346048 687504690
205880053 312504652
794110577 62497634
264714161 937490675
970587944 812502893
617647581 62504110
852944701 812498007
88227293 187492617
558814156 687495577
29403236 812494493
911761865 187491781...

output:

904419459

result:

ok single line: '904419459'

Test #47:

score: 30
Accepted
time: 1ms
memory: 3672kb

input:

1000000000 1000000000
25
59999964 299999989
740000035 100000111
139999972 499999797
740000159 899999809
940000104 899999905
459999870 299999853
139999925 899999750
260000183 300000150
260000200 699999915
940000072 99999821
340000223 900000130
739999776 499999813
59999984 700000029
539999767 90000023...

output:

480000793

result:

ok single line: '480000793'

Test #48:

score: 30
Accepted
time: 1ms
memory: 3652kb

input:

1000000000 1000000000
25
496770868 499466029
150245306 140351260
443861207 442170127
915815913 907024280
592352731 580300173
614771420 602707761
545759771 564678204
790963611 795646738
466306333 474998682
700037062 710428701
326403486 341417980
13108429 18468915
296795338 282907012
207909366 2192548...

output:

1967193239

result:

ok single line: '1967193239'

Test #49:

score: 30
Accepted
time: 1ms
memory: 3600kb

input:

1000000000 1000000000
25
508699723 917649746
972134563 24654272
591574312 768222747
342111766 678842208
280650655 335101574
112108587 538128714
232733100 741988808
569340416 313541403
333183415 646381341
348331220 239049882
321253252 46884019
458715217 456559440
11396102 588839952
212356188 55359081...

output:

967430445

result:

ok single line: '967430445'

Test #50:

score: 30
Accepted
time: 0ms
memory: 3892kb

input:

1000000000 1000000000
25
87500002 928571428
712500002 71428571
212500002 71428570
837500001 71428573
912499999 214285715
287500002 785714285
37500003 785714285
962500002 357142856
787500000 785714288
787500003 500000003
462500002 71428570
462500001 357142859
37499999 500000000
462500002 642857144
37...

output:

660714282

result:

ok single line: '660714282'

Test #51:

score: 30
Accepted
time: 1ms
memory: 3672kb

input:

1000000000 1000000000
25
499999999 565789472
499999990 250000002
499999996 749999995
499999999 144736850
499999993 513157893
499999992 644736853
500000010 13157889
499999998 118421056
499999993 197368414
499999990 592105269
499999994 486842107
500000005 276315783
499999994 539473685
499999990 618421...

output:

1131578975

result:

ok single line: '1131578975'

Test #52:

score: 30
Accepted
time: 0ms
memory: 3576kb

input:

999999999 777777777
25
777772259 317438734
467526694 324943812
750092374 316807230
351488629 328182224
670366487 319838016
194662876 330078646
807706262 316391102
682779230 318750710
529347725 323684686
437218310 325726470
284055780 328324426
156380921 332766879
754204172 318252081
631742119 3197068...

output:

1086358403

result:

ok single line: '1086358403'

Test #53:

score: 30
Accepted
time: 0ms
memory: 3672kb

input:

100000000 1000000000
25
75997424 820728673
777782 777777776
777783 777777777
777780 777777778
18626903 845305698
32700264 518597334
66223561 813120928
92237121 497548369
66359837 477082113
51360029 493816356
777776 777777775
777778 777777776
77907935 347786430
777776 777777776
777779 777777786
77777...

output:

434734665

result:

ok single line: '434734665'

Test #54:

score: 30
Accepted
time: 1ms
memory: 3604kb

input:

1000000000 1000000000
25
202384720 191386798
272784910 876112960
134295596 689831109
144607550 725288401
304962179 141608855
184056836 214149818
580684614 928741905
339656490 906353399
222518718 825019927
65386126 415917878
836363213 211099284
885557581 342429798
772605154 167160669
750597218 865168...

output:

1169492481

result:

ok single line: '1169492481'

Test #55:

score: 30
Accepted
time: 1ms
memory: 3672kb

input:

1000000000 1000000000
25
217898725 381443931
363716745 553078122
741451918 906975033
153568070 900704450
12302872 385341608
276235760 349179186
221511192 438759684
177246208 108385423
157609379 88135252
542559523 122476619
676920172 289023879
132864371 527493734
980440215 892433157
465353007 9681278...

output:

936384704

result:

ok single line: '936384704'

Test #56:

score: 30
Accepted
time: 1ms
memory: 3656kb

input:

1000000000 1000000000
25
108777360 996968244
655575871 74556270
426116462 624297074
601010849 48108108
411143918 863537296
176018437 125264437
769284398 653206473
823951690 375380635
675138657 124417631
305117857 433890179
878598110 72028431
322847356 902439915
323815174 873868901
575209775 37455562...

output:

603034352

result:

ok single line: '603034352'

Test #57:

score: 30
Accepted
time: 0ms
memory: 3656kb

input:

335563010 332545567
25
106441293 332545567
117303130 332545567
335563010 272104540
335563010 47336793
335563010 171741328
315104367 332545567
335563010 258033462
174568335 332545567
170964494 332545567
335563010 68594399
304935196 332545567
97310526 332545567
99941575 332545567
12373018 332545567
33...

output:

389908846

result:

ok single line: '389908846'

Test #58:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

1000000000 1000000000
25
786394982 791216768
119431195 847633609
81087720 1
264330507 432964753
737246186 427050407
922213406 555980523
550982306 581735630
1 1
852080288 1
1 538609505
375220500 773780706
182457491 294843990
1 634980243
421417169 1
253676052 1
601408832 610485554
957268112 249030717
...

output:

886822710

result:

wrong answer 1st lines differ - expected: '905880429', found: '886822710'

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%