oj.uz

Submission #896388

# Submission time Handle Problem Language Result Execution time Memory
896388 2024-01-01T11:03:45 Z GrindMachine Tourism (JOI23_tourism) C++17
100 / 100
 1313 ms 64788 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(x) 42
#endif

/*

refs:
https://codeforces.com/blog/entry/114003?#comment-1015100

answering multiple queries => think about d&c
how to answer all queries passing through mid?

build virtual tree for all nodes a[l..r]
mid is present in all queries, so run a dfs from root = a[mid]

for a given query, a virtual tree edge is chosen if someone in the subtree is present in the query range (because the root is chosen no matter what and if someone in the subtree of the edge is chosen, then the edge has to be traversed in order to go from the root to that node)
for each edge, find the node with the largest position in the [l..mid-1] part and the node with the smallest position in the [mid+1..r] part
define edge as (lx,rx,w):
add w to the ans if ql <= lx or qr >= rx
for a given query, count the sum of w over all edges that satisfy this condition (also add 1 at the end to account for the root node being selected)
can be done efficiently with sweepline + fenwick

*/

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

vector<int> adj1[N];

struct lca_algo {
    // LCA template (for graphs with 1-based indexing)
 
    int LOG = 1;
    vector<int> depth;
    vector<vector<int>> up;
    vector<int> tin, tout;
    int timer = 1;
 
    lca_algo() {
 
    }
 
    lca_algo(int n) {
        lca_init(n);
    }
 
    void lca_init(int n) {
        while ((1 << LOG) < n) LOG++;
        up = vector<vector<int>>(n + 1, vector<int>(LOG, 1));
        depth = vector<int>(n + 1);
        tin = vector<int>(n + 1);
        tout = vector<int>(n + 1);
 
        lca_dfs(1, -1);
    }
 
    void lca_dfs(int node, int par) {
        tin[node] = timer++;
 
        trav(child, adj1[node]) {
            if (child == par) conts;
 
            up[child][0] = node;
            rep1(j, LOG - 1) {
                up[child][j] = up[up[child][j - 1]][j - 1];
            }
 
            depth[child] = depth[node] + 1;
 
            lca_dfs(child, node);
        }
 
        tout[node] = timer-1;
    }
 
    int lift(int u, int k) {
        rep(j, LOG) {
            if (k & (1 << j)) {
                u = up[u][j];
            }
        }
 
        return u;
    }
 
    int query(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);
        int k = depth[u] - depth[v];
        u = lift(u, k);
 
        if (u == v) return u;
 
        rev(j, LOG - 1, 0) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }
 
        u = up[u][0];
        return u;
    }
 
    int get_dis(int u, int v) {
        int lca = query(u, v);
        return depth[u] + depth[v] - 2 * depth[lca];
    }
 
    bool is_ances(int u, int v){
        return tin[u] <= tin[v] and tout[u] >= tout[v];
    }
};

template<typename T>
struct fenwick {
    int siz;
    vector<T> tree;

    fenwick() {

    }

    fenwick(int n) {
        siz = n;
        tree = vector<T>(n + 1);
    }

    int lsb(int x) {
        return x & -x;
    }

    void build(vector<T> &a, int n) {
        for (int i = 1; i <= n; ++i) {
            int par = i + lsb(i);
            tree[i] += a[i];

            if (par <= siz) {
                tree[par] += tree[i];
            }
        }
    }

    void pupd(int i, T v) {
        while (i <= siz) {
            tree[i] += v;
            i += lsb(i);
        }
    }

    T sum(int i) {
        T res = 0;

        while (i) {
            res += tree[i];
            i -= lsb(i);
        }

        return res;
    }

    T query(int l, int r) {
        if (l > r) return 0;
        T res = sum(r) - sum(l - 1);
        return res;
    }
};

lca_algo LCA;
vector<int> a(N);
vector<pii> adj2[N];
vector<int> mxl(N), mnr(N);
vector<array<int,3>> edge_contrib;

void dfs1(int u, int p){
    for(auto [v,d] : adj2[u]){
        if(v == p) conts;
        dfs1(v,u);
        amax(mxl[u],mxl[v]);
        amin(mnr[u],mnr[v]);
        edge_contrib.pb({mxl[v],mnr[v],d});
    }
}

vector<int> ans(N);
vector<array<int,3>> here[N];
fenwick<int> fenw(N);

void go(int l, int r, vector<array<int,3>> queries){
    if(l > r) return;

    int mid = (l+r) >> 1;
    vector<array<int,3>> queries_left, queries_right, queries_curr;

    for(auto [ql,qr,id] : queries){
        if(qr < mid){
            queries_left.pb({ql,qr,id});
        }
        else if(ql > mid){
            queries_right.pb({ql,qr,id});
        }
        else{
            queries_curr.pb({ql,qr,id});
        }
    }

    vector<pii> nodes;
    for(int i = l; i <= r; ++i){
        int u = a[i];
        nodes.pb({LCA.tin[u],u});
    }

    sort(all(nodes));
    int siz = sz(nodes);

    rep(i,siz-1){
        int lca = LCA.query(nodes[i].ss,nodes[i+1].ss);
        nodes.pb({LCA.tin[lca],lca});
    }

    sort(all(nodes));
    nodes.resize(unique(all(nodes))-nodes.begin());
    siz = sz(nodes);

    stack<int> stk;
    stk.push(nodes[0].ss);

    rep1(i,siz-1){
        auto [ti,u] = nodes[i];
        while(!LCA.is_ances(stk.top(),u)){
            stk.pop();
        }
        assert(!stk.empty());
        
        int p = stk.top();
        int d = LCA.get_dis(p,u);
        adj2[p].pb({u,d}), adj2[u].pb({p,d});
        stk.push(u);
    }

    for(auto [ti,u] : nodes){
        mxl[u] = 0;
        mnr[u] = r+1;
    }

    for(int i = l; i < mid; ++i){
        int u = a[i];
        amax(mxl[u],i);
    }
    for(int i = mid+1; i <= r; ++i){
        int u = a[i];
        amin(mnr[u],i);
    }

    edge_contrib.clear();
    int root = a[mid];
    dfs1(root,-1);

    for(auto [ql,qr,id] : queries_curr){
        here[ql].pb({qr,id,1});
    }

    for(auto [lx,rx,w] : edge_contrib){
        here[lx].pb({rx,w,2});
    }

    int sum = 0;
    for(auto [lx,rx,w] : edge_contrib){
        if(lx >= l){
            sum += w;
        }
        else{
            fenw.pupd(rx,w);
        }
    }

    for(int ql = l; ql <= mid; ++ql){
        trav(ar,here[ql]){
            if(ar[2] == 1){
                auto [qr,id,t] = ar;
                int res = sum+fenw.query(1,qr)+1;
                ans[id] = res;
            }
            else{
                auto [rx,w,t] = ar;
                sum -= w;
                fenw.pupd(rx,w);
            }
        }
    }

    for(auto [ql,qr,id] : queries_curr){
        here[ql].clear();
    }
    for(auto [lx,rx,w] : edge_contrib){
        here[lx].clear();
    }
    for(auto [ti,u] : nodes){
        adj2[u].clear();
    }
    for(auto [lx,rx,w] : edge_contrib){
        fenw.pupd(rx,-w);
    }

    go(l,mid-1,queries_left);
    go(mid+1,r,queries_right);
}

void solve(int test_case)
{
    int n,m,q; cin >> n >> m >> q;
    rep1(i,n-1){
        int u,v; cin >> u >> v;
        adj1[u].pb(v), adj1[v].pb(u);
    }
    rep1(i,m) cin >> a[i];

    LCA = lca_algo(n);
    vector<array<int,3>> queries;

    rep1(i,q){
        int l,r; cin >> l >> r;
        queries.pb({l,r,i});
    }

    go(1,m,queries);

    rep1(i,q) cout << ans[i] << 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 3 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 3 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 3 ms 9308 KB Output is correct
7 Correct 3 ms 9304 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9352 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 3 ms 9816 KB Output is correct
12 Correct 3 ms 9564 KB Output is correct
13 Correct 3 ms 9564 KB Output is correct
14 Correct 3 ms 9564 KB Output is correct
15 Correct 4 ms 9564 KB Output is correct
16 Correct 3 ms 9564 KB Output is correct
17 Correct 4 ms 9564 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 3 ms 9564 KB Output is correct
20 Correct 3 ms 9564 KB Output is correct
21 Correct 3 ms 9564 KB Output is correct
22 Correct 3 ms 9492 KB Output is correct
23 Correct 4 ms 9392 KB Output is correct
24 Correct 4 ms 9564 KB Output is correct
25 Correct 3 ms 9564 KB Output is correct
26 Correct 3 ms 9564 KB Output is correct
27 Correct 3 ms 9308 KB Output is correct
28 Correct 3 ms 9304 KB Output is correct
29 Correct 3 ms 9564 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 3 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 3 ms 9308 KB Output is correct
7 Correct 3 ms 9304 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9352 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 3 ms 9816 KB Output is correct
12 Correct 3 ms 9564 KB Output is correct
13 Correct 3 ms 9564 KB Output is correct
14 Correct 3 ms 9564 KB Output is correct
15 Correct 4 ms 9564 KB Output is correct
16 Correct 3 ms 9564 KB Output is correct
17 Correct 4 ms 9564 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 3 ms 9564 KB Output is correct
20 Correct 3 ms 9564 KB Output is correct
21 Correct 3 ms 9564 KB Output is correct
22 Correct 3 ms 9492 KB Output is correct
23 Correct 4 ms 9392 KB Output is correct
24 Correct 4 ms 9564 KB Output is correct
25 Correct 3 ms 9564 KB Output is correct
26 Correct 3 ms 9564 KB Output is correct
27 Correct 3 ms 9308 KB Output is correct
28 Correct 3 ms 9304 KB Output is correct
29 Correct 3 ms 9564 KB Output is correct
30 Correct 7 ms 9820 KB Output is correct
31 Correct 8 ms 9820 KB Output is correct
32 Correct 10 ms 10076 KB Output is correct
33 Correct 11 ms 10080 KB Output is correct
34 Correct 9 ms 10072 KB Output is correct
35 Correct 10 ms 10076 KB Output is correct
36 Correct 10 ms 10076 KB Output is correct
37 Correct 10 ms 10108 KB Output is correct
38 Correct 10 ms 10332 KB Output is correct
39 Correct 9 ms 10328 KB Output is correct
40 Correct 8 ms 10076 KB Output is correct
41 Correct 9 ms 10076 KB Output is correct
42 Correct 9 ms 10076 KB Output is correct
43 Correct 8 ms 10076 KB Output is correct
44 Correct 10 ms 10072 KB Output is correct
45 Correct 9 ms 10076 KB Output is correct
46 Correct 11 ms 10076 KB Output is correct
47 Correct 10 ms 10076 KB Output is correct
48 Correct 10 ms 10076 KB Output is correct
49 Correct 12 ms 10076 KB Output is correct
50 Correct 7 ms 10072 KB Output is correct
51 Correct 7 ms 10072 KB Output is correct
52 Correct 7 ms 9820 KB Output is correct
53 Correct 7 ms 9820 KB Output is correct
54 Correct 8 ms 9820 KB Output is correct
55 Correct 7 ms 9816 KB Output is correct
56 Correct 5 ms 9560 KB Output is correct
57 Correct 4 ms 9816 KB Output is correct
58 Correct 10 ms 10024 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 3 ms 9308 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 510 ms 47584 KB Output is correct
5 Correct 387 ms 42692 KB Output is correct
6 Correct 528 ms 53680 KB Output is correct
7 Correct 746 ms 60060 KB Output is correct
8 Correct 727 ms 61896 KB Output is correct
9 Correct 770 ms 62568 KB Output is correct
10 Correct 729 ms 61952 KB Output is correct
11 Correct 698 ms 61124 KB Output is correct
12 Correct 426 ms 48012 KB Output is correct
13 Correct 430 ms 47944 KB Output is correct
14 Correct 425 ms 47896 KB Output is correct
15 Correct 53 ms 33868 KB Output is correct
16 Correct 783 ms 64788 KB Output is correct
17 Correct 110 ms 19400 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 392 ms 25708 KB Output is correct
3 Correct 677 ms 31092 KB Output is correct
4 Correct 517 ms 29648 KB Output is correct
5 Correct 935 ms 39108 KB Output is correct
6 Correct 1062 ms 39332 KB Output is correct
7 Correct 1093 ms 39128 KB Output is correct
8 Correct 1035 ms 39156 KB Output is correct
9 Correct 904 ms 39392 KB Output is correct
10 Correct 865 ms 39280 KB Output is correct
11 Correct 871 ms 39092 KB Output is correct
12 Correct 901 ms 39644 KB Output is correct
13 Correct 846 ms 39600 KB Output is correct
14 Correct 926 ms 40800 KB Output is correct
15 Correct 951 ms 45292 KB Output is correct
16 Correct 1024 ms 40176 KB Output is correct
17 Correct 909 ms 40592 KB Output is correct
18 Correct 1002 ms 40180 KB Output is correct
19 Correct 1221 ms 44944 KB Output is correct
20 Correct 1079 ms 45208 KB Output is correct
21 Correct 1219 ms 44716 KB Output is correct
22 Correct 1150 ms 44904 KB Output is correct
23 Correct 1148 ms 44996 KB Output is correct
24 Correct 1221 ms 45004 KB Output is correct
25 Correct 1220 ms 44872 KB Output is correct
26 Correct 1162 ms 45200 KB Output is correct
27 Correct 1268 ms 45216 KB Output is correct
28 Correct 1304 ms 44960 KB Output is correct
29 Correct 1155 ms 45300 KB Output is correct
30 Correct 1108 ms 45248 KB Output is correct
31 Correct 1052 ms 45764 KB Output is correct
32 Correct 1096 ms 46440 KB Output is correct
33 Correct 1137 ms 48212 KB Output is correct
34 Correct 1193 ms 51480 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 4 ms 9564 KB Output is correct
4 Correct 600 ms 36992 KB Output is correct
5 Correct 621 ms 37680 KB Output is correct
6 Correct 770 ms 43632 KB Output is correct
7 Correct 911 ms 46320 KB Output is correct
8 Correct 926 ms 46672 KB Output is correct
9 Correct 940 ms 46536 KB Output is correct
10 Correct 896 ms 46496 KB Output is correct
11 Correct 832 ms 46480 KB Output is correct
12 Correct 870 ms 46792 KB Output is correct
13 Correct 964 ms 46448 KB Output is correct
14 Correct 136 ms 19392 KB Output is correct

Subtask #6
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9308 KB Output is correct
2 Correct 2 ms 9308 KB Output is correct
3 Correct 3 ms 9308 KB Output is correct
4 Correct 3 ms 9308 KB Output is correct
5 Correct 3 ms 9308 KB Output is correct
6 Correct 3 ms 9308 KB Output is correct
7 Correct 3 ms 9304 KB Output is correct
8 Correct 3 ms 9308 KB Output is correct
9 Correct 3 ms 9352 KB Output is correct
10 Correct 3 ms 9564 KB Output is correct
11 Correct 3 ms 9816 KB Output is correct
12 Correct 3 ms 9564 KB Output is correct
13 Correct 3 ms 9564 KB Output is correct
14 Correct 3 ms 9564 KB Output is correct
15 Correct 4 ms 9564 KB Output is correct
16 Correct 3 ms 9564 KB Output is correct
17 Correct 4 ms 9564 KB Output is correct
18 Correct 5 ms 9564 KB Output is correct
19 Correct 3 ms 9564 KB Output is correct
20 Correct 3 ms 9564 KB Output is correct
21 Correct 3 ms 9564 KB Output is correct
22 Correct 3 ms 9492 KB Output is correct
23 Correct 4 ms 9392 KB Output is correct
24 Correct 4 ms 9564 KB Output is correct
25 Correct 3 ms 9564 KB Output is correct
26 Correct 3 ms 9564 KB Output is correct
27 Correct 3 ms 9308 KB Output is correct
28 Correct 3 ms 9304 KB Output is correct
29 Correct 3 ms 9564 KB Output is correct
30 Correct 7 ms 9820 KB Output is correct
31 Correct 8 ms 9820 KB Output is correct
32 Correct 10 ms 10076 KB Output is correct
33 Correct 11 ms 10080 KB Output is correct
34 Correct 9 ms 10072 KB Output is correct
35 Correct 10 ms 10076 KB Output is correct
36 Correct 10 ms 10076 KB Output is correct
37 Correct 10 ms 10108 KB Output is correct
38 Correct 10 ms 10332 KB Output is correct
39 Correct 9 ms 10328 KB Output is correct
40 Correct 8 ms 10076 KB Output is correct
41 Correct 9 ms 10076 KB Output is correct
42 Correct 9 ms 10076 KB Output is correct
43 Correct 8 ms 10076 KB Output is correct
44 Correct 10 ms 10072 KB Output is correct
45 Correct 9 ms 10076 KB Output is correct
46 Correct 11 ms 10076 KB Output is correct
47 Correct 10 ms 10076 KB Output is correct
48 Correct 10 ms 10076 KB Output is correct
49 Correct 12 ms 10076 KB Output is correct
50 Correct 7 ms 10072 KB Output is correct
51 Correct 7 ms 10072 KB Output is correct
52 Correct 7 ms 9820 KB Output is correct
53 Correct 7 ms 9820 KB Output is correct
54 Correct 8 ms 9820 KB Output is correct
55 Correct 7 ms 9816 KB Output is correct
56 Correct 5 ms 9560 KB Output is correct
57 Correct 4 ms 9816 KB Output is correct
58 Correct 10 ms 10024 KB Output is correct
59 Correct 3 ms 9308 KB Output is correct
60 Correct 3 ms 9308 KB Output is correct
61 Correct 4 ms 9564 KB Output is correct
62 Correct 510 ms 47584 KB Output is correct
63 Correct 387 ms 42692 KB Output is correct
64 Correct 528 ms 53680 KB Output is correct
65 Correct 746 ms 60060 KB Output is correct
66 Correct 727 ms 61896 KB Output is correct
67 Correct 770 ms 62568 KB Output is correct
68 Correct 729 ms 61952 KB Output is correct
69 Correct 698 ms 61124 KB Output is correct
70 Correct 426 ms 48012 KB Output is correct
71 Correct 430 ms 47944 KB Output is correct
72 Correct 425 ms 47896 KB Output is correct
73 Correct 53 ms 33868 KB Output is correct
74 Correct 783 ms 64788 KB Output is correct
75 Correct 110 ms 19400 KB Output is correct
76 Correct 3 ms 9308 KB Output is correct
77 Correct 392 ms 25708 KB Output is correct
78 Correct 677 ms 31092 KB Output is correct
79 Correct 517 ms 29648 KB Output is correct
80 Correct 935 ms 39108 KB Output is correct
81 Correct 1062 ms 39332 KB Output is correct
82 Correct 1093 ms 39128 KB Output is correct
83 Correct 1035 ms 39156 KB Output is correct
84 Correct 904 ms 39392 KB Output is correct
85 Correct 865 ms 39280 KB Output is correct
86 Correct 871 ms 39092 KB Output is correct
87 Correct 901 ms 39644 KB Output is correct
88 Correct 846 ms 39600 KB Output is correct
89 Correct 926 ms 40800 KB Output is correct
90 Correct 951 ms 45292 KB Output is correct
91 Correct 1024 ms 40176 KB Output is correct
92 Correct 909 ms 40592 KB Output is correct
93 Correct 1002 ms 40180 KB Output is correct
94 Correct 1221 ms 44944 KB Output is correct
95 Correct 1079 ms 45208 KB Output is correct
96 Correct 1219 ms 44716 KB Output is correct
97 Correct 1150 ms 44904 KB Output is correct
98 Correct 1148 ms 44996 KB Output is correct
99 Correct 1221 ms 45004 KB Output is correct
100 Correct 1220 ms 44872 KB Output is correct
101 Correct 1162 ms 45200 KB Output is correct
102 Correct 1268 ms 45216 KB Output is correct
103 Correct 1304 ms 44960 KB Output is correct
104 Correct 1155 ms 45300 KB Output is correct
105 Correct 1108 ms 45248 KB Output is correct
106 Correct 1052 ms 45764 KB Output is correct
107 Correct 1096 ms 46440 KB Output is correct
108 Correct 1137 ms 48212 KB Output is correct
109 Correct 1193 ms 51480 KB Output is correct
110 Correct 2 ms 9308 KB Output is correct
111 Correct 2 ms 9308 KB Output is correct
112 Correct 4 ms 9564 KB Output is correct
113 Correct 600 ms 36992 KB Output is correct
114 Correct 621 ms 37680 KB Output is correct
115 Correct 770 ms 43632 KB Output is correct
116 Correct 911 ms 46320 KB Output is correct
117 Correct 926 ms 46672 KB Output is correct
118 Correct 940 ms 46536 KB Output is correct
119 Correct 896 ms 46496 KB Output is correct
120 Correct 832 ms 46480 KB Output is correct
121 Correct 870 ms 46792 KB Output is correct
122 Correct 964 ms 46448 KB Output is correct
123 Correct 136 ms 19392 KB Output is correct
124 Correct 972 ms 41376 KB Output is correct
125 Correct 665 ms 36608 KB Output is correct
126 Correct 1206 ms 43964 KB Output is correct
127 Correct 1277 ms 43928 KB Output is correct
128 Correct 1178 ms 43960 KB Output is correct
129 Correct 1233 ms 44036 KB Output is correct
130 Correct 1073 ms 43968 KB Output is correct
131 Correct 1115 ms 59920 KB Output is correct
132 Correct 1051 ms 59936 KB Output is correct
133 Correct 1135 ms 62628 KB Output is correct
134 Correct 1313 ms 49588 KB Output is correct
135 Correct 1255 ms 49600 KB Output is correct
136 Correct 1304 ms 49904 KB Output is correct
137 Correct 593 ms 39304 KB Output is correct
138 Correct 588 ms 39304 KB Output is correct
139 Correct 605 ms 39188 KB Output is correct
140 Correct 589 ms 39492 KB Output is correct
141 Correct 575 ms 39596 KB Output is correct
142 Correct 574 ms 39568 KB Output is correct
143 Correct 94 ms 29776 KB Output is correct
144 Correct 1020 ms 45652 KB Output is correct