oj.uz

Submission #568407

# Submission time Handle Problem Language Result Execution time Memory
568407 2022-05-25T11:30:21 Z Ooops_sorry New Home (APIO18_new_home) C++17
100 / 100
 4807 ms 342992 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define ld double
#define ll __int128

mt19937 rnd(51);

const int INF = 1e9;

struct st{
    vector<int> t_min, t_max;
    vector<multiset<int>> t;
    int n;
    void build(int n_) {
        n = n_;
        t_min.clear(), t_max.clear(), t.clear();
        t_min.resize(2 * n, INF);
        t_max.resize(2 * n, -INF);
        t.resize(2 * n);
    }
    void upd(int v) {
        if (t[v].size() == 0) {
            t_min[v] = INF;
            t_max[v] = -INF;
            return;
        }
        t_min[v] = *t[v].begin();
        t_max[v] = *t[v].rbegin();
    }
    void update(int i, int val, bool add) {
        i += n;
        if (add) {
            t[i].insert(val);
        } else {
            t[i].erase(t[i].find(val));
        }
        upd(i);
        for (; i > 1; i /= 2) {
            t_min[i / 2] = min(t_min[i], t_min[i ^ 1]);
            t_max[i / 2] = max(t_max[i], t_max[i ^ 1]);
        }
    }
    int get_min(int l, int r) {
        l += n, r += n + 1;
        int ans = INF;
        while (l < r) {
            if (l & 1) {
                ans = min(ans, t_min[l++]);
            }
            if (r & 1) {
                ans = min(ans, t_min[--r]);
            }
            l /= 2, r /= 2;
        }
        return ans;
    }
    int get_max(int l, int r) {
        l += n, r += n + 1;
        int ans = -INF;
        while (l < r) {
            if (l & 1) {
                ans = max(ans, t_max[l++]);
            }
            if (r & 1) {
                ans = max(ans, t_max[--r]);
            }
            l /= 2, r /= 2;
        }
        return ans;
    }
};

vector<multiset<int>> pos;
vector<int> u2;

st L, R;
int sz;

void add(int a, int b) {
    int need = (a + b) / 2;
    int pos = upper_bound(u2.begin(), u2.end(), need) - u2.begin() - 1;
    int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
    L.update(pos, a, 1);
    R.update(pos + 1, b, 1);
}

void del(int a, int b) {
    int need = (a + b) / 2;
    int pos = upper_bound(u2.begin(), u2.end(), need) - u2.begin() - 1;
    int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
    L.update(pos, a, 0);
    R.update(pos + 1, b, 0);
}

void func(int i, int j, int need) {
    if (need) {
        if (pos[i].find(j) != pos[i].end()) {
            pos[i].insert(j);
            return;
        }
        int pre = *prev(pos[i].lower_bound(j));
        int nxt = *pos[i].upper_bound(j);
        del(pre, nxt);
        add(pre, j);
        add(j, nxt);
        pos[i].insert(j);
    } else {
        pos[i].erase(pos[i].find(j));
        if (pos[i].find(j) != pos[i].end()) return;
        int pre = *prev(pos[i].lower_bound(j));
        int nxt = *pos[i].upper_bound(j);
        del(pre, j);
        del(j, nxt);
        add(pre, nxt);
    }
}

vector<int> solve(int n, int k, int q, vector<int> x, vector<int> t, vector<int> a, vector<int> b, vector<int> l, vector<int> y) {
    u2.clear();
    u2.pb(-INF);
    u2.pb(INF);
    vector<vector<int>> ind(k);
    pos.clear();
    pos.resize(k);
    vector<int> ans(q);
    for (int i = 0; i < n; i++) {
        ind[t[i]].pb(x[i]);
        u2.pb(x[i]);
    }
    for (int i = 0; i < k; i++) {
        ind[i].pb(-INF);
        ind[i].pb(INF);
        sort(ind[i].begin(), ind[i].end());
    }
    for (int i = 0; i < q; i++) {
        u2.pb(l[i]);
    }
    sort(u2.begin(), u2.end());
    u2.erase(unique(u2.begin(), u2.end()), u2.end());
    vector<vector<int>> qu;
    for (int i = 0; i < n; i++) {
        qu.pb({a[i], -1, t[i], x[i]});
        qu.pb({b[i], 1, t[i], x[i]});
    }
    for (int i = 0; i < q; i++) {
        qu.pb({y[i], 0, l[i], i});
    }
    sz = u2.size();
    bool bad = 0;
    L.build(sz);
    R.build(sz);
    for (int i = 0; i < k; i++) {
        if (ind[i].size() == 2) bad = 1;
        pos[i].insert(-INF);
        pos[i].insert(INF);
        add(-INF, INF);
    }
    sort(qu.begin(), qu.end());
    set<int> st;
    for (int i = 0; i < k; i++) st.insert(i);
    for (int i = 0; i < qu.size(); i++) {
        if (qu[i][1] == -1) {
            if (pos[qu[i][2]].size() == 2) st.erase(qu[i][2]);
            func(qu[i][2], qu[i][3], 1);
        } else if (qu[i][1] == 0) {
            int j = lower_bound(u2.begin(), u2.end(), qu[i][2]) - u2.begin();
            int mx = L.get_min(j, sz - 1), mn = R.get_max(0, j);
            if (st.size() > 0) {
                ans[qu[i][3]] = -1;
            } else {
                ans[qu[i][3]] = max(qu[i][2] - mx, mn - qu[i][2]);
            }
        } else {
            func(qu[i][2], qu[i][3], 0);
            if (pos[qu[i][2]].size() == 2) st.insert(qu[i][2]);
        }
    }
    return ans;
}

vector<int> solvee(int n, int k, int q, vector<int> x, vector<int> t, vector<int> a, vector<int> b, vector<int> l, vector<int> y) {
    vector<int> ans;
    for (int i = 0; i < q; i++) {
        vector<int> bst(k, INF);
        for (int j = 0; j < n; j++) {
            if (a[j] <= y[i] && y[i] <= b[j]) {
                bst[t[j]] = min(bst[t[j]], abs(x[j] - l[i]));
            }
        }
        if (*max_element(bst.begin(), bst.end()) == INF) ans.pb(-1);
        else ans.pb(*max_element(bst.begin(), bst.end()));
    }
    return ans;
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif // LOCAL
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (1) {
        int n, k, q;
        cin >> n >> k >> q;
        vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
        for (int i = 0; i < n; i++) {
            cin >> x[i] >> t[i] >> a[i] >> b[i];
            t[i]--;
        }
        for (int i = 0; i < q; i++) {
            cin >> l[i] >> y[i];
        }
        vector<int> ans = solve(n, k, q, x, t, a, b, l, y);
        for (auto to : ans) {
            cout << to << '\n';
        }
        return 0;
    }
    while (1) {
        int n = rnd() % 5 + 1, k = rnd() % 5 + 1, q = rnd() % 1 + 1;
        vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
        for (int i = 0; i < n; i++) {
            x[i] = rnd() % 10 + 1;
            t[i] = rnd() % k;
            a[i] = rnd() % 10 + 1;
            b[i] = rnd() % 10 + 1;
            if (a[i] > b[i]) swap(a[i], b[i]);
        }
        for (int i = 0; i < q; i++) {
            l[i] = rnd() % 10 + 1;
            y[i] = rnd() % 10 + 1;
        }
        auto res = solve(n, k, q, x, t, a, b, l, y), res2 = solvee(n, k, q, x, t, a, b, l, y);
        if (res != res2) {
            cout << n << ' ' << k << ' ' << q << endl;
            for (int i = 0; i < n; i++) {
                cout << x[i] << ' ' <<  t[i] + 1 << ' ' << a[i] << ' ' << b[i] << endl;
            }
            for (int i = 0; i < q; i++) {
                cout << l[i] << ' ' << y[i] << endl;
            }
            cout << "Bad" << endl;
            for (int i = 0; i < q; i++) {
                cout << res[i] << ' ' << res2[i] << endl;
            }
            return 0;
        }
        cout << "ok" << endl;
    }
    return 0;
}

Compilation message

new_home.cpp: In function 'void add(int, int)':
new_home.cpp:85:9: warning: unused variable 'I' [-Wunused-variable]
   85 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |         ^
new_home.cpp:85:64: warning: unused variable 'J' [-Wunused-variable]
   85 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |                                                                ^
new_home.cpp: In function 'void del(int, int)':
new_home.cpp:93:9: warning: unused variable 'I' [-Wunused-variable]
   93 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |         ^
new_home.cpp:93:64: warning: unused variable 'J' [-Wunused-variable]
   93 |     int I = lower_bound(u2.begin(), u2.end(), a) - u2.begin(), J = lower_bound(u2.begin(), u2.end(), b) - u2.begin();
      |                                                                ^
new_home.cpp: In function 'std::vector<int> solve(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
new_home.cpp:164:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  164 |     for (int i = 0; i < qu.size(); i++) {
      |                     ~~^~~~~~~~~~~
new_home.cpp:152:10: warning: variable 'bad' set but not used [-Wunused-but-set-variable]
  152 |     bool bad = 0;
      |          ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 612 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 724 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 612 KB Output is correct
30 Correct 2 ms 468 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 612 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 724 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 612 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 507 ms 49644 KB Output is correct
32 Correct 111 ms 15764 KB Output is correct
33 Correct 424 ms 44076 KB Output is correct
34 Correct 426 ms 44272 KB Output is correct
35 Correct 485 ms 49576 KB Output is correct
36 Correct 478 ms 49396 KB Output is correct
37 Correct 288 ms 41640 KB Output is correct
38 Correct 290 ms 41608 KB Output is correct
39 Correct 242 ms 41000 KB Output is correct
40 Correct 252 ms 41084 KB Output is correct
41 Correct 300 ms 40988 KB Output is correct
42 Correct 289 ms 41168 KB Output is correct
43 Correct 92 ms 17704 KB Output is correct
44 Correct 302 ms 41188 KB Output is correct
45 Correct 277 ms 40956 KB Output is correct
46 Correct 258 ms 40960 KB Output is correct
47 Correct 201 ms 39964 KB Output is correct
48 Correct 184 ms 39700 KB Output is correct
49 Correct 210 ms 40376 KB Output is correct
50 Correct 244 ms 41020 KB Output is correct
51 Correct 205 ms 40092 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2784 ms 260116 KB Output is correct
2 Correct 1773 ms 243252 KB Output is correct
3 Correct 3659 ms 329064 KB Output is correct
4 Correct 3449 ms 271916 KB Output is correct
5 Correct 1790 ms 242576 KB Output is correct
6 Correct 1887 ms 242772 KB Output is correct
7 Correct 3062 ms 329032 KB Output is correct
8 Correct 2708 ms 271800 KB Output is correct
9 Correct 2276 ms 252036 KB Output is correct
10 Correct 1775 ms 243948 KB Output is correct
11 Correct 1430 ms 239524 KB Output is correct
12 Correct 1622 ms 242584 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3013 ms 244916 KB Output is correct
2 Correct 760 ms 83060 KB Output is correct
3 Correct 2696 ms 242692 KB Output is correct
4 Correct 4043 ms 328192 KB Output is correct
5 Correct 3483 ms 267756 KB Output is correct
6 Correct 3707 ms 278904 KB Output is correct
7 Correct 2453 ms 249960 KB Output is correct
8 Correct 2649 ms 250028 KB Output is correct
9 Correct 4046 ms 334992 KB Output is correct
10 Correct 3838 ms 271080 KB Output is correct
11 Correct 3475 ms 254144 KB Output is correct
12 Correct 3145 ms 250192 KB Output is correct
13 Correct 1411 ms 243812 KB Output is correct
14 Correct 1306 ms 241796 KB Output is correct
15 Correct 1484 ms 245624 KB Output is correct
16 Correct 1695 ms 248004 KB Output is correct
17 Correct 1538 ms 244424 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 612 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 724 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 612 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 507 ms 49644 KB Output is correct
32 Correct 111 ms 15764 KB Output is correct
33 Correct 424 ms 44076 KB Output is correct
34 Correct 426 ms 44272 KB Output is correct
35 Correct 485 ms 49576 KB Output is correct
36 Correct 478 ms 49396 KB Output is correct
37 Correct 288 ms 41640 KB Output is correct
38 Correct 290 ms 41608 KB Output is correct
39 Correct 242 ms 41000 KB Output is correct
40 Correct 252 ms 41084 KB Output is correct
41 Correct 300 ms 40988 KB Output is correct
42 Correct 289 ms 41168 KB Output is correct
43 Correct 92 ms 17704 KB Output is correct
44 Correct 302 ms 41188 KB Output is correct
45 Correct 277 ms 40956 KB Output is correct
46 Correct 258 ms 40960 KB Output is correct
47 Correct 201 ms 39964 KB Output is correct
48 Correct 184 ms 39700 KB Output is correct
49 Correct 210 ms 40376 KB Output is correct
50 Correct 244 ms 41020 KB Output is correct
51 Correct 205 ms 40092 KB Output is correct
52 Correct 656 ms 66380 KB Output is correct
53 Correct 625 ms 62816 KB Output is correct
54 Correct 558 ms 55092 KB Output is correct
55 Correct 415 ms 49424 KB Output is correct
56 Correct 468 ms 53840 KB Output is correct
57 Correct 350 ms 43376 KB Output is correct
58 Correct 446 ms 49580 KB Output is correct
59 Correct 471 ms 53736 KB Output is correct
60 Correct 360 ms 43648 KB Output is correct
61 Correct 295 ms 40048 KB Output is correct
62 Correct 627 ms 66380 KB Output is correct
63 Correct 560 ms 56528 KB Output is correct
64 Correct 545 ms 52184 KB Output is correct
65 Correct 429 ms 44576 KB Output is correct
66 Correct 311 ms 41304 KB Output is correct
67 Correct 258 ms 17852 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 328 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 596 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 720 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 2 ms 612 KB Output is correct
15 Correct 2 ms 688 KB Output is correct
16 Correct 3 ms 588 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 2 ms 596 KB Output is correct
19 Correct 2 ms 596 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 2 ms 596 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 724 KB Output is correct
24 Correct 2 ms 596 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 2 ms 592 KB Output is correct
27 Correct 2 ms 340 KB Output is correct
28 Correct 2 ms 596 KB Output is correct
29 Correct 2 ms 612 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 507 ms 49644 KB Output is correct
32 Correct 111 ms 15764 KB Output is correct
33 Correct 424 ms 44076 KB Output is correct
34 Correct 426 ms 44272 KB Output is correct
35 Correct 485 ms 49576 KB Output is correct
36 Correct 478 ms 49396 KB Output is correct
37 Correct 288 ms 41640 KB Output is correct
38 Correct 290 ms 41608 KB Output is correct
39 Correct 242 ms 41000 KB Output is correct
40 Correct 252 ms 41084 KB Output is correct
41 Correct 300 ms 40988 KB Output is correct
42 Correct 289 ms 41168 KB Output is correct
43 Correct 92 ms 17704 KB Output is correct
44 Correct 302 ms 41188 KB Output is correct
45 Correct 277 ms 40956 KB Output is correct
46 Correct 258 ms 40960 KB Output is correct
47 Correct 201 ms 39964 KB Output is correct
48 Correct 184 ms 39700 KB Output is correct
49 Correct 210 ms 40376 KB Output is correct
50 Correct 244 ms 41020 KB Output is correct
51 Correct 205 ms 40092 KB Output is correct
52 Correct 2784 ms 260116 KB Output is correct
53 Correct 1773 ms 243252 KB Output is correct
54 Correct 3659 ms 329064 KB Output is correct
55 Correct 3449 ms 271916 KB Output is correct
56 Correct 1790 ms 242576 KB Output is correct
57 Correct 1887 ms 242772 KB Output is correct
58 Correct 3062 ms 329032 KB Output is correct
59 Correct 2708 ms 271800 KB Output is correct
60 Correct 2276 ms 252036 KB Output is correct
61 Correct 1775 ms 243948 KB Output is correct
62 Correct 1430 ms 239524 KB Output is correct
63 Correct 1622 ms 242584 KB Output is correct
64 Correct 3013 ms 244916 KB Output is correct
65 Correct 760 ms 83060 KB Output is correct
66 Correct 2696 ms 242692 KB Output is correct
67 Correct 4043 ms 328192 KB Output is correct
68 Correct 3483 ms 267756 KB Output is correct
69 Correct 3707 ms 278904 KB Output is correct
70 Correct 2453 ms 249960 KB Output is correct
71 Correct 2649 ms 250028 KB Output is correct
72 Correct 4046 ms 334992 KB Output is correct
73 Correct 3838 ms 271080 KB Output is correct
74 Correct 3475 ms 254144 KB Output is correct
75 Correct 3145 ms 250192 KB Output is correct
76 Correct 1411 ms 243812 KB Output is correct
77 Correct 1306 ms 241796 KB Output is correct
78 Correct 1484 ms 245624 KB Output is correct
79 Correct 1695 ms 248004 KB Output is correct
80 Correct 1538 ms 244424 KB Output is correct
81 Correct 656 ms 66380 KB Output is correct
82 Correct 625 ms 62816 KB Output is correct
83 Correct 558 ms 55092 KB Output is correct
84 Correct 415 ms 49424 KB Output is correct
85 Correct 468 ms 53840 KB Output is correct
86 Correct 350 ms 43376 KB Output is correct
87 Correct 446 ms 49580 KB Output is correct
88 Correct 471 ms 53736 KB Output is correct
89 Correct 360 ms 43648 KB Output is correct
90 Correct 295 ms 40048 KB Output is correct
91 Correct 627 ms 66380 KB Output is correct
92 Correct 560 ms 56528 KB Output is correct
93 Correct 545 ms 52184 KB Output is correct
94 Correct 429 ms 44576 KB Output is correct
95 Correct 311 ms 41304 KB Output is correct
96 Correct 258 ms 17852 KB Output is correct
97 Correct 4695 ms 327664 KB Output is correct
98 Correct 819 ms 79224 KB Output is correct
99 Correct 3310 ms 229520 KB Output is correct
100 Correct 4617 ms 325228 KB Output is correct
101 Correct 4355 ms 286128 KB Output is correct
102 Correct 3590 ms 256340 KB Output is correct
103 Correct 2406 ms 217160 KB Output is correct
104 Correct 2224 ms 217084 KB Output is correct
105 Correct 1398 ms 214056 KB Output is correct
106 Correct 1499 ms 214404 KB Output is correct
107 Correct 3092 ms 257864 KB Output is correct
108 Correct 3266 ms 279140 KB Output is correct
109 Correct 2597 ms 228996 KB Output is correct
110 Correct 3305 ms 258440 KB Output is correct
111 Correct 3659 ms 279652 KB Output is correct
112 Correct 2848 ms 228600 KB Output is correct
113 Correct 1817 ms 208892 KB Output is correct
114 Correct 4807 ms 342992 KB Output is correct
115 Correct 4384 ms 293536 KB Output is correct
116 Correct 4370 ms 272032 KB Output is correct
117 Correct 3671 ms 234116 KB Output is correct
118 Correct 2498 ms 216820 KB Output is correct
119 Correct 2397 ms 93460 KB Output is correct
120 Correct 952 ms 203340 KB Output is correct
121 Correct 1123 ms 209156 KB Output is correct
122 Correct 1127 ms 207908 KB Output is correct
123 Correct 1203 ms 211044 KB Output is correct
124 Correct 1322 ms 214116 KB Output is correct
125 Correct 1174 ms 211152 KB Output is correct
126 Correct 1484 ms 215300 KB Output is correct