oj.uz

Submission #1091055

# Submission time Handle Problem Language Result Execution time Memory
1091055 2024-09-19T15:55:27 Z underwaterkillerwhale Tourism (JOI23_tourism) C++17
100 / 100
 3670 ms 69628 KB 
#include <bits/stdc++.h>
#define ll              long long
#define pii             pair<int,int>
#define pll             pair<ll,ll>
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)
#define iter(id, v)     for(auto id : v)
#define fs              first
#define se              second
#define MP              make_pair
#define pb              push_back
#define bit(msk, i)     ((msk >> i) & 1)
#define SZ(v)           (ll)v.size()
#define ALL(v)          v.begin(),v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 1e5 + 7;
const int Mod = 1e9 + 2022; ///loonf mod sai
const int INF = 1e9;
const ll BASE = 137;
const int szBL = 320;

struct FastSet {
    using uint = unsigned int ; using ull = unsigned long long ; template < class T > using V = vector <T>; template < class T > using VV = V <V<T>>;

    int popcnt ( uint x ) { return __builtin_popcount(x); } int popcnt ( ull x ) { return __builtin_popcountll(x); } int bsr ( uint x ) { return 31 - __builtin_clz(x); } int bsr ( ull x ) { return 63 - __builtin_clzll(x); } int bsf ( uint x ) { return __builtin_ctz(x); } int bsf ( ull x ) { return __builtin_ctzll(x); }
    static constexpr uint B = 64 ;

    int n, lg;
    int idx[(int)1e5 + 7]; ///size
    VV<ull> seg;
    FastSet( int _n) : n(_n) {
        do {
            seg.push_back(V<ull>((_n + B - 1 ) / B));
            _n = (_n + B - 1 ) / B;
        }while (_n > 1 );
        lg = seg.size();

    }
    bool operator []( int i) const {
        return (seg[ 0 ][i / B] >> (i % B) & 1 ) != 0 ;
    }
    void set ( int i) {
        for ( int h = 0 ; h < lg; h++) {
            seg[h][i / B] |= 1ULL << (i % B); i /= B;
        }
    }
    void reset ( int i) {
        for ( int h = 0 ; h < lg; h++) {
            seg[h][i / B] &= ~( 1ULL << (i % B));
            if (seg[h][i / B]) break ;
            i /= B;
        }
    }
    int next ( int i) {
        if (i < 0) i = 0;
        if (i > n) i = n;
        for ( int h = 0 ; h < lg; h++) {
            if (i / B == seg[h].size()) break ;
            ull d = seg[h][i / B] >> (i % B);
            if (!d) {
                i = i / B + 1 ;
                continue ;
            }
            i += bsf(d);
            for ( int g = h - 1 ; g >= 0 ; g--) {
                i *= B; i += bsf(seg[g][i / B]);
            }
            return i;
        }
        return n;
    }
    int prev ( int i) {
        if (i < 0) i = 0;
        if (i > n) i = n;
        i--;
        for ( int h = 0 ; h < lg; h++) {
            if (i == -1 ) break ;
            ull d = seg[h][i / B] << ( 63 - i % 64 );
            if (!d) {
                i = i / B - 1 ;
                continue ;
            }
            i += bsr(d) - (B - 1 );
            for ( int g = h - 1 ; g >= 0 ; g--) {
                i *= B;
                i += bsr(seg[g][i / B]);
            }
            return i;
        }
        return -1 ;
    }
};



struct Query {
    int fs, se, id;
};

int n, m, Q;
vector<int> ke[N];
Query qr[N];
int C[N];

int high[N], szC[N], euler[2 * N], posin[N], pa[N], ein[N], eout[N], Ver[N];
pii flca[2 * N][25];

void pdfs (int u, int p) {
    static int sz = 0, time_dfs = 0;
    high[u] = high[p] + 1;
    pa[u] = p;
    szC[u] = 1;

    flca[++sz][0] = MP(high[u], u);
    posin[u] = sz;
    ein[u] = ++time_dfs;
    Ver[time_dfs] = u;
    iter (&v, ke[u]) {
        if (v != p) {
            pdfs(v, u);
            szC[u] += szC[v];
            flca[++sz][0] = MP(high[u], u);
        }
    }
    eout[u] = time_dfs;
}

void init_LCA () {
    for (int j = 1; (1 << j) <= 2 * n; ++j)
        for (int i = 1; i + (1 << j) - 1 <= 2 * n; ++i)
            flca[i][j] = min(flca[i][j - 1], flca[i + (1 << j - 1)][j - 1]);
}

int LCA (int u, int v) {
    u = posin[u];
    v = posin[v];
    if (u > v) swap(u, v);
    int K = 31 - __builtin_clz(v - u + 1);
    return min(flca[u][K], flca[v - (1 << K) + 1][K]).se;
}

namespace sub2 {

    int pre[N];

    void dfs (int u, int p, int &res) {
        iter (&v, ke[u]) {
            if (v != p) {
                dfs(v, u, res);
                pre[u] += pre[v];
            }
        }
        if (pre[u] > 0) ++res;
    }

    void solution () {
        rep (q, 1, Q) {
            rep (i, 1, n) pre[i] = 0;
            int L = qr[q].fs, R = qr[q].se;
            int Lca = C[L];
            rep (i, L, R) {
                Lca = LCA(Lca, C[i]);
            }
            rep (i, L, R) {
                pre[C[i]]++;
                pre[pa[Lca]]--;
            }
            int res = 0;
            dfs(1, 0, res);
            cout << res <<"\n";
        }

    }

}

namespace sub6 {

    int sptLCA[N][25];
    int res = 0;
    int ptrL = 1, ptrR = 0;
    int cnt[N];

    FastSet S(1e5 + 1);

    void update (int u, int val) {
        cnt[ein[u]] += val;
        if (val == -1) {
            if (cnt[ein[u]] == 0) S.reset(ein[u]);
        }
        int lc = -1, rc = -1;
        int nxt = S.next(ein[u]), prv = S.prev(ein[u]);
//        cout << u <<" "<<ein[u]<<" "<<nxt <<" "<<prv<<"\n";
        if (nxt != 1e5 + 1) rc = Ver[nxt];
        if (prv != -1) lc = Ver[prv];
        if (rc == -1 && lc == -1) res += val * high[u];
        else {
            int nearest = 1;
            if (rc != -1) {
                nearest = LCA(u, rc);
            }
            if (lc != -1) {
                int v = LCA(u, lc);
                if (high[nearest] < high[v]) nearest = v;
            }
            res += val * (high[u] - high[nearest]);
        }

        if (val == 1) S.set(ein[u]);
    }

    void shifting (int L, int R) {
        while (ptrL > L) {
            --ptrL;
            update(C[ptrL], 1);
        }
        while (ptrR < R) {
            ++ptrR;
            update (C[ptrR], 1);
        }
        while (ptrL < L) {
            update(C[ptrL], -1);
            ++ptrL;
        }
        while (ptrR > R) {
           update (C[ptrR], -1);
           --ptrR;
        }
    }

    void solution () {
        sort (qr + 1, qr + 1 + Q, [] (Query A, Query B) {
            if (A.fs / szBL != B.fs / szBL) return A.fs < B.fs;
            else return A.se < B.se;
        });
        rep (i, 1, m) sptLCA[i][0] = C[i];

        for (int j = 1; (1 << j) <= m; ++j)
        for (int i = 1; i + (1 << j) - 1 <= m; ++i)
            sptLCA[i][j] = LCA(sptLCA[i][j - 1], sptLCA[i + (1 << j - 1)][j - 1]);

        auto get_LCA = [] (int L, int R) {
            int K = 31 - __builtin_clz(R - L + 1);
            return LCA(sptLCA[L][K], sptLCA[R - (1 << K) + 1][K]);
        };

        vector<int> Ans(Q + 1);
        rep (q, 1, Q) {
            int L = qr[q].fs, R = qr[q].se, id = qr[q].id;
            shifting(L, R);
            Ans[id] = res - high[get_LCA(L, R)] + 1;
        }
        rep (i, 1, Q) cout << Ans[i] <<"\n";
    }
}


void solution() {
    cin >> n >> m >> Q;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].pb(v);
        ke[v].pb(u);
    }
    rep (i, 1, m) cin >> C[i];
    rep (i, 1, Q) cin >> qr[i].fs >> qr[i].se, qr[i].id = i;
    pdfs(1, 0);
    init_LCA();
//    if (n <= 2000 && m <= 2000 && Q <= 2000) sub2 :: solution();
//    else
        sub6 :: solution();

}

#define file(name) freopen(name".inp","r",stdin); \
freopen(name".out","w",stdout);
int main () {
//    file("c");
    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
no bug +8
chu y break hay return se lam hong logic
xet transition cua i va i + 1
construct ket qua
chu y truong hop : KHONG CO GI

ko làm được

hướng 1: đổi hướng làm
hướng 2: đưa ra nhận xét

tim mo hinh bai toan sau khi doc de

trung ten bien trong ham gan nhat co the dan den sai

10 7 3
6 5
3 6
9 3
8 3
7 8
7 1
2 5
7 10
8 4
9 4 10 1 10 7 6
4 4
1 3
6 7



*/

Compilation message

tourism.cpp: In function 'void init_LCA()':
tourism.cpp:136:63: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  136 |             flca[i][j] = min(flca[i][j - 1], flca[i + (1 << j - 1)][j - 1]);
      |                                                             ~~^~~
tourism.cpp: In function 'void sub6::solution()':
tourism.cpp:245:69: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  245 |             sptLCA[i][j] = LCA(sptLCA[i][j - 1], sptLCA[i + (1 << j - 1)][j - 1]);
      |                                                                   ~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 2 ms 2840 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 2 ms 2908 KB Output is correct
17 Correct 2 ms 2908 KB Output is correct
18 Correct 2 ms 2908 KB Output is correct
19 Correct 2 ms 2868 KB Output is correct
20 Correct 2 ms 3072 KB Output is correct
21 Correct 2 ms 2908 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 3016 KB Output is correct
25 Correct 2 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 1 ms 2908 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 2 ms 2840 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 2 ms 2908 KB Output is correct
17 Correct 2 ms 2908 KB Output is correct
18 Correct 2 ms 2908 KB Output is correct
19 Correct 2 ms 2868 KB Output is correct
20 Correct 2 ms 3072 KB Output is correct
21 Correct 2 ms 2908 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 3016 KB Output is correct
25 Correct 2 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 1 ms 2908 KB Output is correct
30 Correct 7 ms 3676 KB Output is correct
31 Correct 9 ms 3616 KB Output is correct
32 Correct 10 ms 3932 KB Output is correct
33 Correct 11 ms 4080 KB Output is correct
34 Correct 10 ms 4076 KB Output is correct
35 Correct 4 ms 3928 KB Output is correct
36 Correct 3 ms 3928 KB Output is correct
37 Correct 4 ms 3932 KB Output is correct
38 Correct 9 ms 4160 KB Output is correct
39 Correct 10 ms 4160 KB Output is correct
40 Correct 9 ms 4192 KB Output is correct
41 Correct 4 ms 4188 KB Output is correct
42 Correct 4 ms 4188 KB Output is correct
43 Correct 4 ms 3928 KB Output is correct
44 Correct 11 ms 3936 KB Output is correct
45 Correct 10 ms 3932 KB Output is correct
46 Correct 10 ms 3932 KB Output is correct
47 Correct 4 ms 3932 KB Output is correct
48 Correct 3 ms 3932 KB Output is correct
49 Correct 3 ms 3932 KB Output is correct
50 Correct 9 ms 3932 KB Output is correct
51 Correct 9 ms 4084 KB Output is correct
52 Correct 9 ms 3932 KB Output is correct
53 Correct 9 ms 3932 KB Output is correct
54 Correct 10 ms 3932 KB Output is correct
55 Correct 9 ms 3928 KB Output is correct
56 Correct 6 ms 2908 KB Output is correct
57 Correct 2 ms 3676 KB Output is correct
58 Correct 3 ms 3932 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 2 ms 2908 KB Output is correct
3 Correct 5 ms 3148 KB Output is correct
4 Correct 2134 ms 43908 KB Output is correct
5 Correct 1139 ms 53584 KB Output is correct
6 Correct 1966 ms 62032 KB Output is correct
7 Correct 3008 ms 69544 KB Output is correct
8 Correct 3000 ms 69628 KB Output is correct
9 Correct 3142 ms 69620 KB Output is correct
10 Correct 3070 ms 69628 KB Output is correct
11 Correct 3127 ms 69620 KB Output is correct
12 Correct 265 ms 69320 KB Output is correct
13 Correct 270 ms 69328 KB Output is correct
14 Correct 278 ms 69456 KB Output is correct
15 Correct 63 ms 57424 KB Output is correct
16 Correct 116 ms 69272 KB Output is correct
17 Correct 659 ms 15960 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2652 KB Output is correct
2 Correct 57 ms 34156 KB Output is correct
3 Correct 84 ms 40176 KB Output is correct
4 Correct 78 ms 41484 KB Output is correct
5 Correct 96 ms 60048 KB Output is correct
6 Correct 103 ms 60240 KB Output is correct
7 Correct 111 ms 60244 KB Output is correct
8 Correct 120 ms 60240 KB Output is correct
9 Correct 117 ms 60088 KB Output is correct
10 Correct 112 ms 60244 KB Output is correct
11 Correct 116 ms 60244 KB Output is correct
12 Correct 113 ms 60240 KB Output is correct
13 Correct 109 ms 60500 KB Output is correct
14 Correct 109 ms 61096 KB Output is correct
15 Correct 135 ms 63060 KB Output is correct
16 Correct 128 ms 60364 KB Output is correct
17 Correct 110 ms 60468 KB Output is correct
18 Correct 99 ms 60496 KB Output is correct
19 Correct 82 ms 60496 KB Output is correct
20 Correct 95 ms 60240 KB Output is correct
21 Correct 100 ms 60172 KB Output is correct
22 Correct 102 ms 60240 KB Output is correct
23 Correct 100 ms 59992 KB Output is correct
24 Correct 95 ms 60100 KB Output is correct
25 Correct 105 ms 60184 KB Output is correct
26 Correct 101 ms 60036 KB Output is correct
27 Correct 110 ms 60080 KB Output is correct
28 Correct 104 ms 60248 KB Output is correct
29 Correct 105 ms 60280 KB Output is correct
30 Correct 108 ms 60240 KB Output is correct
31 Correct 115 ms 60388 KB Output is correct
32 Correct 105 ms 60752 KB Output is correct
33 Correct 102 ms 61524 KB Output is correct
34 Correct 104 ms 63060 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 5 ms 2908 KB Output is correct
4 Correct 2530 ms 41644 KB Output is correct
5 Correct 2659 ms 42656 KB Output is correct
6 Correct 3269 ms 55956 KB Output is correct
7 Correct 3481 ms 63380 KB Output is correct
8 Correct 3537 ms 63300 KB Output is correct
9 Correct 3451 ms 63364 KB Output is correct
10 Correct 3575 ms 63368 KB Output is correct
11 Correct 3607 ms 63360 KB Output is correct
12 Correct 3541 ms 63312 KB Output is correct
13 Correct 3492 ms 63316 KB Output is correct
14 Correct 644 ms 16136 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2652 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2904 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 3 ms 2908 KB Output is correct
8 Correct 2 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 2 ms 2908 KB Output is correct
11 Correct 2 ms 2840 KB Output is correct
12 Correct 1 ms 2908 KB Output is correct
13 Correct 1 ms 2908 KB Output is correct
14 Correct 2 ms 2908 KB Output is correct
15 Correct 2 ms 2908 KB Output is correct
16 Correct 2 ms 2908 KB Output is correct
17 Correct 2 ms 2908 KB Output is correct
18 Correct 2 ms 2908 KB Output is correct
19 Correct 2 ms 2868 KB Output is correct
20 Correct 2 ms 3072 KB Output is correct
21 Correct 2 ms 2908 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 2 ms 3016 KB Output is correct
25 Correct 2 ms 2904 KB Output is correct
26 Correct 2 ms 2908 KB Output is correct
27 Correct 2 ms 2908 KB Output is correct
28 Correct 1 ms 2908 KB Output is correct
29 Correct 1 ms 2908 KB Output is correct
30 Correct 7 ms 3676 KB Output is correct
31 Correct 9 ms 3616 KB Output is correct
32 Correct 10 ms 3932 KB Output is correct
33 Correct 11 ms 4080 KB Output is correct
34 Correct 10 ms 4076 KB Output is correct
35 Correct 4 ms 3928 KB Output is correct
36 Correct 3 ms 3928 KB Output is correct
37 Correct 4 ms 3932 KB Output is correct
38 Correct 9 ms 4160 KB Output is correct
39 Correct 10 ms 4160 KB Output is correct
40 Correct 9 ms 4192 KB Output is correct
41 Correct 4 ms 4188 KB Output is correct
42 Correct 4 ms 4188 KB Output is correct
43 Correct 4 ms 3928 KB Output is correct
44 Correct 11 ms 3936 KB Output is correct
45 Correct 10 ms 3932 KB Output is correct
46 Correct 10 ms 3932 KB Output is correct
47 Correct 4 ms 3932 KB Output is correct
48 Correct 3 ms 3932 KB Output is correct
49 Correct 3 ms 3932 KB Output is correct
50 Correct 9 ms 3932 KB Output is correct
51 Correct 9 ms 4084 KB Output is correct
52 Correct 9 ms 3932 KB Output is correct
53 Correct 9 ms 3932 KB Output is correct
54 Correct 10 ms 3932 KB Output is correct
55 Correct 9 ms 3928 KB Output is correct
56 Correct 6 ms 2908 KB Output is correct
57 Correct 2 ms 3676 KB Output is correct
58 Correct 3 ms 3932 KB Output is correct
59 Correct 1 ms 2652 KB Output is correct
60 Correct 2 ms 2908 KB Output is correct
61 Correct 5 ms 3148 KB Output is correct
62 Correct 2134 ms 43908 KB Output is correct
63 Correct 1139 ms 53584 KB Output is correct
64 Correct 1966 ms 62032 KB Output is correct
65 Correct 3008 ms 69544 KB Output is correct
66 Correct 3000 ms 69628 KB Output is correct
67 Correct 3142 ms 69620 KB Output is correct
68 Correct 3070 ms 69628 KB Output is correct
69 Correct 3127 ms 69620 KB Output is correct
70 Correct 265 ms 69320 KB Output is correct
71 Correct 270 ms 69328 KB Output is correct
72 Correct 278 ms 69456 KB Output is correct
73 Correct 63 ms 57424 KB Output is correct
74 Correct 116 ms 69272 KB Output is correct
75 Correct 659 ms 15960 KB Output is correct
76 Correct 1 ms 2652 KB Output is correct
77 Correct 57 ms 34156 KB Output is correct
78 Correct 84 ms 40176 KB Output is correct
79 Correct 78 ms 41484 KB Output is correct
80 Correct 96 ms 60048 KB Output is correct
81 Correct 103 ms 60240 KB Output is correct
82 Correct 111 ms 60244 KB Output is correct
83 Correct 120 ms 60240 KB Output is correct
84 Correct 117 ms 60088 KB Output is correct
85 Correct 112 ms 60244 KB Output is correct
86 Correct 116 ms 60244 KB Output is correct
87 Correct 113 ms 60240 KB Output is correct
88 Correct 109 ms 60500 KB Output is correct
89 Correct 109 ms 61096 KB Output is correct
90 Correct 135 ms 63060 KB Output is correct
91 Correct 128 ms 60364 KB Output is correct
92 Correct 110 ms 60468 KB Output is correct
93 Correct 99 ms 60496 KB Output is correct
94 Correct 82 ms 60496 KB Output is correct
95 Correct 95 ms 60240 KB Output is correct
96 Correct 100 ms 60172 KB Output is correct
97 Correct 102 ms 60240 KB Output is correct
98 Correct 100 ms 59992 KB Output is correct
99 Correct 95 ms 60100 KB Output is correct
100 Correct 105 ms 60184 KB Output is correct
101 Correct 101 ms 60036 KB Output is correct
102 Correct 110 ms 60080 KB Output is correct
103 Correct 104 ms 60248 KB Output is correct
104 Correct 105 ms 60280 KB Output is correct
105 Correct 108 ms 60240 KB Output is correct
106 Correct 115 ms 60388 KB Output is correct
107 Correct 105 ms 60752 KB Output is correct
108 Correct 102 ms 61524 KB Output is correct
109 Correct 104 ms 63060 KB Output is correct
110 Correct 1 ms 2648 KB Output is correct
111 Correct 1 ms 2908 KB Output is correct
112 Correct 5 ms 2908 KB Output is correct
113 Correct 2530 ms 41644 KB Output is correct
114 Correct 2659 ms 42656 KB Output is correct
115 Correct 3269 ms 55956 KB Output is correct
116 Correct 3481 ms 63380 KB Output is correct
117 Correct 3537 ms 63300 KB Output is correct
118 Correct 3451 ms 63364 KB Output is correct
119 Correct 3575 ms 63368 KB Output is correct
120 Correct 3607 ms 63360 KB Output is correct
121 Correct 3541 ms 63312 KB Output is correct
122 Correct 3492 ms 63316 KB Output is correct
123 Correct 644 ms 16136 KB Output is correct
124 Correct 2786 ms 61572 KB Output is correct
125 Correct 1636 ms 56880 KB Output is correct
126 Correct 3510 ms 63312 KB Output is correct
127 Correct 3564 ms 63568 KB Output is correct
128 Correct 3550 ms 63396 KB Output is correct
129 Correct 3598 ms 63480 KB Output is correct
130 Correct 3670 ms 63452 KB Output is correct
131 Correct 3463 ms 68680 KB Output is correct
132 Correct 3384 ms 69536 KB Output is correct
133 Correct 3392 ms 66508 KB Output is correct
134 Correct 3487 ms 63528 KB Output is correct
135 Correct 3564 ms 63492 KB Output is correct
136 Correct 3620 ms 63484 KB Output is correct
137 Correct 3160 ms 63616 KB Output is correct
138 Correct 3188 ms 63780 KB Output is correct
139 Correct 3148 ms 63604 KB Output is correct
140 Correct 3218 ms 63776 KB Output is correct
141 Correct 3047 ms 63788 KB Output is correct
142 Correct 3071 ms 63708 KB Output is correct
143 Correct 76 ms 51284 KB Output is correct
144 Correct 123 ms 63056 KB Output is correct