oj.uz

Submission #985853

# Submission time Handle Problem Language Result Execution time Memory
985853 2024-05-19T06:48:57 Z GrindMachine Fish 2 (JOI22_fish2) C++17
100 / 100
 3120 ms 30664 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/101003?#comment-898608

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct lazysegtree {
    /*=======================================================*/

    struct data {
        ll mn,cnt;
    };

    struct lazy {
        ll a;
    };

    data d_neutral = {inf2,0};
    lazy l_neutral = {0};

    void merge(data &curr, data &left, data &right) {
        curr.mn = min(left.mn,right.mn);
        curr.cnt = 0;
        if(left.mn == curr.mn) curr.cnt += left.cnt;
        if(right.mn == curr.mn) curr.cnt += right.cnt;
    }

    void create(int x, int lx, int rx, T v) {
        tr[x] = {v,1};
    }

    void modify(int x, int lx, int rx, T v) {
        lz[x].a = v;
    }

    void propagate(int x, int lx, int rx) {
        ll v = lz[x].a;
        if(!v) return;

        tr[x].mn += v;

        if(rx-lx > 1){
            lz[2*x+1].a += v;
            lz[2*x+2].a += v;
        }

        lz[x] = l_neutral;
    }

    /*=======================================================*/

    int siz = 1;
    vector<data> tr;
    vector<lazy> lz;

    lazysegtree() {

    }

    lazysegtree(int n) {
        while (siz < n) siz *= 2;
        tr.assign(2 * siz, d_neutral);
        lz.assign(2 * siz, l_neutral);
    }

    void build(int n, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < n) {
                create(x, lx, rx, 0);
            }

            return;
        }

        int mid = (lx + rx) / 2;

        build(n, 2 * x + 1, lx, mid);
        build(n, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void build(int n) {
        build(n, 0, 0, siz);
    }

    void rupd(int l, int r, T v, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return;
        if (lx >= l and rx <= r) {
            modify(x, lx, rx, v);
            propagate(x, lx, rx);
            return;
        }

        int mid = (lx + rx) / 2;

        rupd(l, r, v, 2 * x + 1, lx, mid);
        rupd(l, r, v, 2 * x + 2, mid, rx);

        merge(tr[x], tr[2 * x + 1], tr[2 * x + 2]);
    }

    void rupd(int l, int r, T v) {
        rupd(l, r + 1, v, 0, 0, siz);
    }

    data query(int l, int r, int x, int lx, int rx) {
        propagate(x, lx, rx);

        if (lx >= r or rx <= l) return d_neutral;
        if (lx >= l and rx <= r) return tr[x];

        int mid = (lx + rx) / 2;

        data curr;
        data left = query(l, r, 2 * x + 1, lx, mid);
        data right = query(l, r, 2 * x + 2, mid, rx);

        merge(curr, left, right);
        return curr;
    }

    data query(int l, int r) {
        return query(l, r + 1, 0, 0, siz);
    }
};

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        ll sum,mnp,mns,val1,val2;
    };

    data neutral = {0,0,0,inf2,inf2};

    data merge(data &left, data &right) {
        data curr;

        curr.sum = left.sum+right.sum;
        curr.mnp = min({left.mnp,left.sum+right.mnp});
        curr.mns = min({right.mns,right.sum+left.mns});
        curr.val1 = min({left.val1,curr.mnp});
        curr.val2 = min({right.val2,curr.mns});

        return curr;
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {
        tr[i] = {v,-v,-v};
    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        modify(i + n, v);
        for (i = (i + n) >> 1; i; i >>= 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    data query(int l, int r) {
        data resl = neutral, resr = neutral;

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) resl = merge(resl, tr[l++]);
            if (!(r & 1)) resr = merge(tr[r--], resr);
        }

        return merge(resl, resr);
    }
};

ll msb(ll x){
    return 63-__builtin_clzll(x);
}

void solve(int test_case)
{
    ll n; cin >> n;
    vector<ll> a(n+5);
    rep1(i,n) cin >> a[i];
    a[0] = a[n+1] = inf2;
    vector<ll> p(n+5);
    rep1(i,n) p[i] = p[i-1]+a[i];

    vector<ll> ngel(n+5), nger(n+5,n+1);

    {
        stack<ll> stk;

        rep1(i,n){
            while(!stk.empty() and a[i] >= a[stk.top()]){
                nger[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
    }

    {
        stack<ll> stk;

        rev(i,n,1){
            while(!stk.empty() and a[i] >= a[stk.top()]){
                ngel[stk.top()] = i;
                stk.pop();
            }
            stk.push(i);
        }
    }

    set<pll> pairs;

    auto add_pair = [&](ll l, ll r){
        if(l > r) swap(l,r);
        if(r-l-1 <= 0) return;

        ll sum = p[r-1]-p[l];
        if(min(a[l],a[r]) > sum){
            pairs.insert({l+1,r-1});
        }
    };

    rep1(i,n){
        add_pair(i,ngel[i]);
        add_pair(i,nger[i]);
    }

    lazysegtree<ll> st(n+5);
    st.build(n+1);
    for(auto [l,r] : pairs){
        st.rupd(l,r,1);
    }

    segtree<ll> seg(n+5);
    rep1(i,n) seg.pupd(i,a[i]);

    set<ll> pos[30];
    rep1(i,n) pos[msb(a[i])].insert(i);

    auto get = [&](ll i){
        vector<pll> segs;

        // sum[l..i] < a[l-1]
        vector<ll> points_left;
        rep(bit,30){
            auto it = pos[bit].upper_bound(i);
            if(it != pos[bit].begin()){
                it--;
                points_left.pb(*it);
                if(it != pos[bit].begin()){
                    it--;
                    points_left.pb(*it);
                }
            }
        }

        vector<pll> ok_left;
        
        trav(l,points_left){
            if(i == l) conts;
            ll sum = seg.query(l+1,i).sum;
            if(sum < a[l]){
                ok_left.pb({l+1,sum});
            }
            if(l+1 <= i-1 and sum-a[i] < min(a[l],a[i])){
                segs.pb({l+1,i-1});
            }
        }

        ok_left.pb({1,seg.query(1,i).sum});
        if(seg.query(1,i-1).sum < a[i]){
            segs.pb({1,i-1});
        }

        // sum[i..r] < a[r+1]
        vector<ll> points_right;
        rep(bit,30){
            auto it = pos[bit].lower_bound(i);
            if(it != pos[bit].end()){
                points_right.pb(*it);
                if(next(it) != pos[bit].end()){
                    points_right.pb(*next(it));
                }
            }
        }

        vector<pll> ok_right;

        trav(r,points_right){
            if(i == r) conts;
            ll sum = seg.query(i,r-1).sum;
            if(sum < a[r]){
                ok_right.pb({r-1,sum});
            }
            if(i+1 <= r-1 and sum-a[i] < min(a[i],a[r])){
                segs.pb({i+1,r-1});
            }
        }

        ok_right.pb({n,seg.query(i,n).sum});
        if(seg.query(i+1,n).sum < a[i]){
            segs.pb({i+1,n});
        }

        // merge ok_left, ok_right

        for(auto [l,sum1] : ok_left){
            for(auto [r,sum2] : ok_right){
                ll sum = sum1+sum2-a[i];
                if(sum < min(a[l-1],a[r+1])){
                    segs.pb({l,r});
                }
            }
        }

        // [l..i-1] and [i+1..r] that were not added
        auto &curr = pos[msb(a[i])];
        auto it = curr.find(i);
        if(it != curr.begin()){
            it--;
            if(it != curr.begin()){
                it--;
                ll l = *it+1;
                if(seg.query(l,i-1).sum < min(a[l-1],a[i])){
                    segs.pb({l,i-1});
                }
            }
        }

        it = curr.find(i);
        it++;
        if(it != curr.end()){
            it++;
            if(it != curr.end()){
                ll r = *it-1;
                if(seg.query(i+1,r).sum < min(a[i],a[r+1])){
                    segs.pb({i+1,r});
                }
            }
        }

        return segs;
    };

    ll q; cin >> q;
    while(q--){
        ll t; cin >> t;
        if(t == 1){
            ll i,v; cin >> i >> v;
            auto del = get(i);

            pos[msb(a[i])].erase(i);
            a[i] = v;
            seg.pupd(i,v);
            pos[msb(v)].insert(i);

            auto ins = get(i);

            // debug(i,v);
            // debug(del);
            // debug(ins);
            // cout << endl;

            for(auto [l,r] : del){
                st.rupd(l,r,-1);
            }
            for(auto [l,r] : ins){
                st.rupd(l,r,1);
            }
        }
        else{
            ll l,r; cin >> l >> r;
            ll pos1 = l, pos2 = r;

            {
                ll lo = l, hi = r;
                while(lo <= hi){
                    ll mid = (lo+hi) >> 1;
                    if(seg.query(l,mid-1).sum+seg.query(mid,r).val1 < 0){
                        pos1 = mid;
                        lo = mid+1;
                    }
                    else{
                        hi = mid-1;
                    }
                }
            }

            {
                ll lo = l, hi = r;
                while(lo <= hi){
                    ll mid = (lo+hi) >> 1;
                    if(seg.query(mid+1,r).sum+seg.query(l,mid).val2 < 0){
                        pos2 = mid;
                        hi = mid-1;
                    }
                    else{
                        lo = mid+1;
                    }
                }
            }

            ll ans = st.query(pos1,pos2).cnt;
            cout << ans << endl;
        }
    }
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 3 ms 464 KB Output is correct
20 Correct 2 ms 348 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 82 ms 27976 KB Output is correct
3 Correct 86 ms 27220 KB Output is correct
4 Correct 85 ms 27992 KB Output is correct
5 Correct 69 ms 27220 KB Output is correct
6 Correct 54 ms 25744 KB Output is correct
7 Correct 46 ms 24048 KB Output is correct
8 Correct 55 ms 25848 KB Output is correct
9 Correct 45 ms 24008 KB Output is correct
10 Correct 63 ms 25568 KB Output is correct
11 Correct 54 ms 24660 KB Output is correct
12 Correct 50 ms 24744 KB Output is correct
13 Correct 50 ms 24912 KB Output is correct
14 Correct 62 ms 26900 KB Output is correct
15 Correct 65 ms 26932 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 3 ms 464 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 82 ms 27976 KB Output is correct
23 Correct 86 ms 27220 KB Output is correct
24 Correct 85 ms 27992 KB Output is correct
25 Correct 69 ms 27220 KB Output is correct
26 Correct 54 ms 25744 KB Output is correct
27 Correct 46 ms 24048 KB Output is correct
28 Correct 55 ms 25848 KB Output is correct
29 Correct 45 ms 24008 KB Output is correct
30 Correct 63 ms 25568 KB Output is correct
31 Correct 54 ms 24660 KB Output is correct
32 Correct 50 ms 24744 KB Output is correct
33 Correct 50 ms 24912 KB Output is correct
34 Correct 62 ms 26900 KB Output is correct
35 Correct 65 ms 26932 KB Output is correct
36 Correct 96 ms 28760 KB Output is correct
37 Correct 83 ms 27472 KB Output is correct
38 Correct 89 ms 26680 KB Output is correct
39 Correct 100 ms 28752 KB Output is correct
40 Correct 74 ms 26884 KB Output is correct
41 Correct 67 ms 26000 KB Output is correct
42 Correct 64 ms 25808 KB Output is correct
43 Correct 60 ms 23888 KB Output is correct
44 Correct 57 ms 24092 KB Output is correct
45 Correct 82 ms 25428 KB Output is correct
46 Correct 70 ms 25260 KB Output is correct
47 Correct 53 ms 23640 KB Output is correct
48 Correct 65 ms 24916 KB Output is correct
49 Correct 58 ms 24740 KB Output is correct
50 Correct 74 ms 26964 KB Output is correct
51 Correct 73 ms 26812 KB Output is correct
52 Correct 78 ms 27472 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 82 ms 27976 KB Output is correct
3 Correct 86 ms 27220 KB Output is correct
4 Correct 85 ms 27992 KB Output is correct
5 Correct 69 ms 27220 KB Output is correct
6 Correct 54 ms 25744 KB Output is correct
7 Correct 46 ms 24048 KB Output is correct
8 Correct 55 ms 25848 KB Output is correct
9 Correct 45 ms 24008 KB Output is correct
10 Correct 63 ms 25568 KB Output is correct
11 Correct 54 ms 24660 KB Output is correct
12 Correct 50 ms 24744 KB Output is correct
13 Correct 50 ms 24912 KB Output is correct
14 Correct 62 ms 26900 KB Output is correct
15 Correct 65 ms 26932 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 740 ms 29296 KB Output is correct
18 Correct 698 ms 30548 KB Output is correct
19 Correct 724 ms 29072 KB Output is correct
20 Correct 759 ms 29044 KB Output is correct
21 Correct 713 ms 29016 KB Output is correct
22 Correct 723 ms 30664 KB Output is correct
23 Correct 713 ms 28756 KB Output is correct
24 Correct 726 ms 29688 KB Output is correct
25 Correct 707 ms 29332 KB Output is correct
26 Correct 728 ms 29264 KB Output is correct
27 Correct 673 ms 27800 KB Output is correct
28 Correct 748 ms 27796 KB Output is correct
29 Correct 718 ms 27736 KB Output is correct
30 Correct 699 ms 25668 KB Output is correct
31 Correct 703 ms 25656 KB Output is correct
32 Correct 730 ms 26628 KB Output is correct
33 Correct 751 ms 27132 KB Output is correct
34 Correct 714 ms 26180 KB Output is correct
35 Correct 697 ms 25440 KB Output is correct
36 Correct 686 ms 27256 KB Output is correct
37 Correct 668 ms 26468 KB Output is correct
38 Correct 655 ms 26752 KB Output is correct
39 Correct 712 ms 29376 KB Output is correct
40 Correct 751 ms 28720 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 82 ms 27976 KB Output is correct
3 Correct 86 ms 27220 KB Output is correct
4 Correct 85 ms 27992 KB Output is correct
5 Correct 69 ms 27220 KB Output is correct
6 Correct 54 ms 25744 KB Output is correct
7 Correct 46 ms 24048 KB Output is correct
8 Correct 55 ms 25848 KB Output is correct
9 Correct 45 ms 24008 KB Output is correct
10 Correct 63 ms 25568 KB Output is correct
11 Correct 54 ms 24660 KB Output is correct
12 Correct 50 ms 24744 KB Output is correct
13 Correct 50 ms 24912 KB Output is correct
14 Correct 62 ms 26900 KB Output is correct
15 Correct 65 ms 26932 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 2307 ms 29304 KB Output is correct
18 Correct 3071 ms 29880 KB Output is correct
19 Correct 1759 ms 28636 KB Output is correct
20 Correct 2153 ms 29544 KB Output is correct
21 Correct 2279 ms 29304 KB Output is correct
22 Correct 2954 ms 29960 KB Output is correct
23 Correct 2118 ms 28636 KB Output is correct
24 Correct 2950 ms 29372 KB Output is correct
25 Correct 2029 ms 28516 KB Output is correct
26 Correct 1244 ms 27700 KB Output is correct
27 Correct 1735 ms 27732 KB Output is correct
28 Correct 2157 ms 25816 KB Output is correct
29 Correct 1448 ms 27592 KB Output is correct
30 Correct 1851 ms 27600 KB Output is correct
31 Correct 2614 ms 25828 KB Output is correct
32 Correct 3094 ms 26824 KB Output is correct
33 Correct 955 ms 26604 KB Output is correct
34 Correct 2181 ms 27688 KB Output is correct
35 Correct 879 ms 26676 KB Output is correct
36 Correct 2577 ms 26776 KB Output is correct
37 Correct 1702 ms 26340 KB Output is correct
38 Correct 1097 ms 26620 KB Output is correct
39 Correct 1411 ms 28948 KB Output is correct
40 Correct 726 ms 28720 KB Output is correct

Subtask #6
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 456 KB Output is correct
5 Correct 7 ms 596 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 5 ms 588 KB Output is correct
13 Correct 3 ms 348 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 2 ms 756 KB Output is correct
17 Correct 4 ms 348 KB Output is correct
18 Correct 2 ms 348 KB Output is correct
19 Correct 3 ms 464 KB Output is correct
20 Correct 2 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 82 ms 27976 KB Output is correct
23 Correct 86 ms 27220 KB Output is correct
24 Correct 85 ms 27992 KB Output is correct
25 Correct 69 ms 27220 KB Output is correct
26 Correct 54 ms 25744 KB Output is correct
27 Correct 46 ms 24048 KB Output is correct
28 Correct 55 ms 25848 KB Output is correct
29 Correct 45 ms 24008 KB Output is correct
30 Correct 63 ms 25568 KB Output is correct
31 Correct 54 ms 24660 KB Output is correct
32 Correct 50 ms 24744 KB Output is correct
33 Correct 50 ms 24912 KB Output is correct
34 Correct 62 ms 26900 KB Output is correct
35 Correct 65 ms 26932 KB Output is correct
36 Correct 96 ms 28760 KB Output is correct
37 Correct 83 ms 27472 KB Output is correct
38 Correct 89 ms 26680 KB Output is correct
39 Correct 100 ms 28752 KB Output is correct
40 Correct 74 ms 26884 KB Output is correct
41 Correct 67 ms 26000 KB Output is correct
42 Correct 64 ms 25808 KB Output is correct
43 Correct 60 ms 23888 KB Output is correct
44 Correct 57 ms 24092 KB Output is correct
45 Correct 82 ms 25428 KB Output is correct
46 Correct 70 ms 25260 KB Output is correct
47 Correct 53 ms 23640 KB Output is correct
48 Correct 65 ms 24916 KB Output is correct
49 Correct 58 ms 24740 KB Output is correct
50 Correct 74 ms 26964 KB Output is correct
51 Correct 73 ms 26812 KB Output is correct
52 Correct 78 ms 27472 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 740 ms 29296 KB Output is correct
55 Correct 698 ms 30548 KB Output is correct
56 Correct 724 ms 29072 KB Output is correct
57 Correct 759 ms 29044 KB Output is correct
58 Correct 713 ms 29016 KB Output is correct
59 Correct 723 ms 30664 KB Output is correct
60 Correct 713 ms 28756 KB Output is correct
61 Correct 726 ms 29688 KB Output is correct
62 Correct 707 ms 29332 KB Output is correct
63 Correct 728 ms 29264 KB Output is correct
64 Correct 673 ms 27800 KB Output is correct
65 Correct 748 ms 27796 KB Output is correct
66 Correct 718 ms 27736 KB Output is correct
67 Correct 699 ms 25668 KB Output is correct
68 Correct 703 ms 25656 KB Output is correct
69 Correct 730 ms 26628 KB Output is correct
70 Correct 751 ms 27132 KB Output is correct
71 Correct 714 ms 26180 KB Output is correct
72 Correct 697 ms 25440 KB Output is correct
73 Correct 686 ms 27256 KB Output is correct
74 Correct 668 ms 26468 KB Output is correct
75 Correct 655 ms 26752 KB Output is correct
76 Correct 712 ms 29376 KB Output is correct
77 Correct 751 ms 28720 KB Output is correct
78 Correct 1 ms 348 KB Output is correct
79 Correct 2307 ms 29304 KB Output is correct
80 Correct 3071 ms 29880 KB Output is correct
81 Correct 1759 ms 28636 KB Output is correct
82 Correct 2153 ms 29544 KB Output is correct
83 Correct 2279 ms 29304 KB Output is correct
84 Correct 2954 ms 29960 KB Output is correct
85 Correct 2118 ms 28636 KB Output is correct
86 Correct 2950 ms 29372 KB Output is correct
87 Correct 2029 ms 28516 KB Output is correct
88 Correct 1244 ms 27700 KB Output is correct
89 Correct 1735 ms 27732 KB Output is correct
90 Correct 2157 ms 25816 KB Output is correct
91 Correct 1448 ms 27592 KB Output is correct
92 Correct 1851 ms 27600 KB Output is correct
93 Correct 2614 ms 25828 KB Output is correct
94 Correct 3094 ms 26824 KB Output is correct
95 Correct 955 ms 26604 KB Output is correct
96 Correct 2181 ms 27688 KB Output is correct
97 Correct 879 ms 26676 KB Output is correct
98 Correct 2577 ms 26776 KB Output is correct
99 Correct 1702 ms 26340 KB Output is correct
100 Correct 1097 ms 26620 KB Output is correct
101 Correct 1411 ms 28948 KB Output is correct
102 Correct 726 ms 28720 KB Output is correct
103 Correct 2527 ms 28024 KB Output is correct
104 Correct 2438 ms 30656 KB Output is correct
105 Correct 973 ms 29792 KB Output is correct
106 Correct 1118 ms 29572 KB Output is correct
107 Correct 2276 ms 28532 KB Output is correct
108 Correct 2678 ms 30616 KB Output is correct
109 Correct 1338 ms 28928 KB Output is correct
110 Correct 1710 ms 30324 KB Output is correct
111 Correct 989 ms 29492 KB Output is correct
112 Correct 1111 ms 29792 KB Output is correct
113 Correct 1558 ms 27756 KB Output is correct
114 Correct 839 ms 27988 KB Output is correct
115 Correct 2757 ms 25880 KB Output is correct
116 Correct 1729 ms 25680 KB Output is correct
117 Correct 1069 ms 27916 KB Output is correct
118 Correct 1024 ms 26000 KB Output is correct
119 Correct 1676 ms 27740 KB Output is correct
120 Correct 2557 ms 25944 KB Output is correct
121 Correct 1524 ms 26112 KB Output is correct
122 Correct 3120 ms 26900 KB Output is correct
123 Correct 996 ms 25816 KB Output is correct
124 Correct 1377 ms 25768 KB Output is correct
125 Correct 776 ms 25880 KB Output is correct
126 Correct 1071 ms 25956 KB Output is correct
127 Correct 1804 ms 26748 KB Output is correct
128 Correct 816 ms 26636 KB Output is correct
129 Correct 1550 ms 28832 KB Output is correct
130 Correct 1026 ms 28640 KB Output is correct