oj.uz

Submission #239165

# Submission time Handle Problem Language Result Execution time Memory
239165 2020-06-14T16:31:23 Z Plasmatic Dynamic Diameter (CEOI19_diameter) C++11
100 / 100
 4269 ms 148900 KB 
#pragma region
#include "bits/stdc++.h"
using namespace std;
// Common Type shorteners and int128
using ll = long long; using ull = unsigned long long; using ld = long double;
using pii = pair<int, int>; using pll = pair<ll, ll>;
template <typename T> using vec = vector<T>;
template <typename K, typename V> using umap = unordered_map<K, V>; template <typename K> using uset = unordered_set<K>;
using vi = vec<int>; using vl = vec<ll>; using vpi = vec<pii>; using vpl = vec<pll>;
#ifdef __SIZEOF_INT128__
using int128 = __int128_t; using uint128 = __uint128_t;
#endif
template<typename I> string intStr(I x) { string ret; while (x > 0) { ret += (x % 10) + '0'; x /= 10; } reverse(ret.begin(), ret.end()); return ret; } // Int to string
// Shorthand Macros
#define INF 0x3f3f3f3f
#define LLINF 0x3f3f3f3f3f3f3f3f
#define mpr make_pair
#define mtup make_tuple
#define pb push_back
#define popcount __builtin_popcount
#define clz __builtin_clz
#define ctz __builtin_ctz
#define popcountll __builtin_popcountll
#define clzll __builtin_clzll
#define ctzll __builtin_ctzll
#define finline __attribute__((always_inline))
// Shorthand Function Macros
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (__typeof(a) i = a; i < b; i++)
#define reprev(i, a, b) for (__typeof(a) i = a; i > b; i--)
#define repi(a, b) rep(i, a, b)
#define repj(a, b) rep(j, a, b)
#define repk(a, b) rep(k, a, b)
#define Cmplt(type) bool operator<(const type &o) const
#define Cmpgt(type) bool operator>(const type &o) const
#define Cmpfn(name, type) bool name(const type &a, const type &b)
#define Inop(type) istream& operator>>(istream& in, type &o)
#define Outop(type) ostream& operator<<(ostream& out, type o)
#define Pow2(x) (1LL << (x))
#define scn(type, ...) type __VA_ARGS__; scan(__VA_ARGS__) // scn -> Short for SCan New
// Shorthand Functions
// template<typename T> inline int sz(const T &x) { return x.size(); }
template<typename T> inline void maxa(T& st, T v) { st = max(st, v); }
template<typename T> inline void mina(T& st, T v) { st = min(st, v); }
inline void setprec(ostream& out, int prec) { out << setprecision(prec) << fixed; }
// Out operators and printing for arrays and vectors
template <typename T> ostream& operator<<(ostream& out,vector<T> iter){out<<"[";for(auto t:iter){out<<t<<", ";}out<<"]";return out;}
template <typename T> string arrayStr(T *arr,int sz){string ret = "[";for(int i=0;i<sz;i++){ret+=to_string(arr[i])+", "; } return ret + "]";}
template <typename T> void printArray(T *arr,int sz){for(int i=0;i<sz;i++){cout<<arr[i]<<" "; } cout<<"\n";}
// I/O Operations
inline void scan(){}
template<typename F, typename... R> inline void scan(F &f,R&... r){cin>>f;scan(r...);}
template <typename F> inline void println(F t){cout<<t<<'\n';}
template<typename F, typename... R> inline void println(F f,R... r){cout<<f<<" ";println(r...);}
inline void print(){}
template<typename F, typename... R> inline void print(F f,R... r){cout<<f;print(r...);}
// Debugging
#define db(x) cout << (#x) << ": " << (x) << ", "
#define dblb(s) cout << "[" << (s) << "] "
#define dba(alias, x) cout << (alias) << ": " << (x) << ", "
template<typename F> inline string __generic_tostring(F f) { stringstream ss; ss << f; return ss.str(); }
template<typename F> inline string __join_comma(F f) {return __generic_tostring(f);}
template<typename F, typename... R> string __join_comma(F f, R... r) { return __generic_tostring(f) + ", " + __join_comma(r...); }
#define dbp(alias, ...) cout << (alias) << ": (" << __join_comma(__VA_ARGS__) << "), "
#define dbbin(x, n) cout << (#x) << ": " << bitset<n>(x) << ", "
#define dbarr(x, n) cout << (#x) << ": " << arrayStr((x), (n)) << ", "
#define dbln cout << endl;
#pragma endregion

const int MN = 1e5 + 1, LG = 18;
int N, Q,
    A[MN], B[MN], lv[MN];
ll W, 
    weight[MN];
struct Ed {
    int i, v;
    ll w() { return weight[i]; }
};
vec<Ed> g[MN];

int sz[MN];
bool block[MN];

// centroid stuff
int gsz(int c, int p) {
    sz[c] = 1;
    for (auto to : g[c])
        if (to.v != p && !block[to.v])
            sz[c] += gsz(to.v, c);
    return sz[c];
}
int gcent(int c, int p, int req) {
    for (auto to : g[c])
        if (to.v != p && !block[to.v] && sz[to.v] > req)
            return gcent(to.v, c, req);
    return c;
}

// wesley's iterative point update segtree
struct CombinePair {
  using Data = pll;
  using Lazy = pll;
  const Data qdef = {0, 0};
  Data merge(const Data &l, const Data &r) const {
      if (l.first > r.first) {
          return {l.first, max(l.second, r.first)};
      }
      return {r.first, max(r.second, l.first)};
  }
  Data applyLazy(const Data &l, const Lazy &r) const { return r; }
};
struct CombineSingle {
  using Data = ll;
  using Lazy = ll;
  const Data qdef = -LLINF;
  Data merge(const Data &l, const Data &r) const { return max(l, r); }
  Data applyLazy(const Data &l, const Lazy &r) const { return r; }
};
template <class Combine> struct SegmentTreeBottomUp {
  using Data = typename Combine::Data; using Lazy = typename Combine::Lazy;
  Combine C; int N; vector<Data> TR;
  void init(int N0, const Data &vdef) {
    N = N0;
    TR = vec<Data>(N * 2, C.qdef);
    fill(TR.begin() + N, TR.end(), vdef);
    for (int i = N - 1; i > 0; i--)
      TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
  }
  void update(int i, const Lazy &v) {
    for (i += N, TR[i] = C.applyLazy(TR[i], v); i /= 2;)
      TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
  }
  Data query(int l, int r) {
    Data ql = C.qdef, qr = C.qdef;
    for (l += N, r += N; l <= r; l /= 2, r /= 2) {
      if (l & 1) ql = C.merge(ql, TR[l++]);
      if (!(r & 1)) qr = C.merge(TR[r--], qr);
    }
    return C.merge(ql, qr);
  }
};

// Wesley's iterative lazy segtree
struct Combine {
  using Data = ll;
  using Lazy = ll;
  const Data qdef = -LLINF;
  const Lazy ldef = 0;
  Data merge(const Data &l, const Data &r) const { return max(l, r); }
  Data applyLazy(const Data &l, const Lazy &r) const { return l + r; }
  Lazy getSegmentVal(const Lazy &v, int k) const { return v; }
  Lazy mergeLazy(const Lazy &l, const Lazy &r) const { return l + r; }
};
template <class Combine> struct SegmentTreeLazyBottomUp {
  using Data = typename Combine::Data; using Lazy = typename Combine::Lazy;
  Combine C; int N, lgN; vector<Data> TR; vector<Lazy> LZ;
  void apply(int i, const Lazy &v, int k) {
    TR[i] = C.applyLazy(TR[i], C.getSegmentVal(v, k));
    if (i < N) LZ[i] = C.mergeLazy(LZ[i], v);
  }
  void pushup(int i) {
    for (int k = 2; i /= 2; k *= 2) {
      TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
      if (LZ[i] != C.ldef)
        TR[i] = C.applyLazy(TR[i], C.getSegmentVal(LZ[i], k));
    }
  }
  void propagate(int i) {
    int h = lgN + 1, k = 1 << lgN, ii = i >> h;
    for (; h > 0; ii = i >> --h, k /= 2) if (LZ[ii] != C.ldef) {
      apply(ii * 2, LZ[ii], k); apply(ii * 2 + 1, LZ[ii], k); LZ[ii] = C.ldef;
    }
  }
  void init(int n0, const Data vdef) {
      N = n0;
      lgN = __lg(N);
      TR = vector<Data>(N * 2, C.qdef);
      LZ = vector<Data>(N, C.ldef); 
      fill(TR.begin() + N, TR.end(), vdef);
      for (int i = N - 1; i > 0; i--) TR[i] = C.merge(TR[i * 2], TR[i * 2 + 1]);
  }
  void update(int l, int r, const Lazy &v) {
    int l0 = l += N, r0 = r += N, k = 1; propagate(l); propagate(r);
    for (; l <= r; l /= 2, r /= 2, k *= 2) {
      if (l & 1) apply(l++, v, k);
      if (!(r & 1)) apply(r--, v, k);
    }
    pushup(l0); pushup(r0);
  }
  Data query(int l, int r) {
    propagate(l += N); propagate(r += N); Data ql = C.qdef, qr = C.qdef;
    for (; l <= r; l /= 2, r /= 2) {
      if (l & 1) ql = C.merge(ql, TR[l++]);
      if (!(r & 1)) qr = C.merge(TR[r--], qr);
    }
    return C.merge(ql, qr);
  }
};

// maintaining paths that pass through centroid
int fst[LG][MN], lst[LG][MN];
struct DS {
    int n, lg;
    vi tour;
    vector<pair<int, ll>> dis;
    SegmentTreeLazyBottomUp<Combine> seg;
    void dfs(int c, int p, ll cdis) {
        tour.pb(c);
        fst[lg][c] = tour.size() - 1;
        dis.emplace_back(c, cdis);
        for (auto to : g[c]) {
            if (to.v != p && !block[to.v]) {
                dfs(to.v, c, cdis + to.w());
            }
        }
        lst[lg][c] = tour.size() - 1;
    }
    void init(int c, int lg0) {
        // dfs and init tour
        // dblb("init"); db(c); db(pre); dbln;
        lg = lg0;
        dfs(c, -1, 0);
        // init seg
        n = tour.size();
        seg.init(n, -LLINF);
        sort(all(dis));
        for (auto p : dis) {
            int id = fst[lg][p.first];
            seg.update(id, id, LLINF + p.second); // to counteract the infinity (TM)
        }
    }
    ll get(int node) {
        return seg.query(fst[lg][node], lst[lg][node]);
    }
    int getBottomNode(int a, int b) {
        ll da = lower_bound(all(dis), mpr(a, -1LL))->second, db = lower_bound(all(dis), mpr(b, -1LL))->second;
        return da > db ? a : b;
    }
    void inc(int root, ll amt) {
        seg.update(fst[lg][root], lst[lg][root], amt);
    }
};
SegmentTreeBottomUp<CombineSingle> allDist;
SegmentTreeBottomUp<CombinePair> centDist[MN];
ll preAllDist[MN];
DS paths[MN];
int chForEdge[LG][MN];
vi hasEdge[MN]; // centroids that have that edge

void setupEdge(int c, int p, int cent, int chid) {
    for (auto to : g[c]) {
        if (to.v != p && !block[to.v]) {
            hasEdge[to.i].pb(cent);
            chForEdge[lv[cent]][to.i] = chid;
            setupEdge(to.v, c, cent, chid);
        }
    }
}

// build centroid tree
void decomp(int c, int clv) {
    gsz(c, -1);
    if (sz[c] == 1) return;
    int cent = gcent(c, -1, sz[c] / 2);
    lv[cent] = clv;

    paths[cent].init(cent, clv);
    centDist[cent].init(g[cent].size(), mpr(0, 0));
    repi(0, int(g[cent].size())) {
        auto to = g[cent][i];
        if (!block[to.v]) {
            centDist[cent].update(i, mpr(paths[cent].get(to.v), 0));

            setupEdge(to.v, cent, cent, i);
            hasEdge[to.i].pb(cent);
            chForEdge[clv][to.i] = i;
        }
    }

    pll dia = centDist[cent].query(0, g[cent].size() - 1);
    preAllDist[cent] = dia.first + dia.second;
    allDist.update(cent - 1, preAllDist[cent]);

    block[cent] = true;
    for (auto to : g[cent]) {
        if (!block[to.v])
            decomp(to.v, clv + 1);
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    scan(N, Q, W);
    repi(0, N - 1) {
        scn(int, a, b);
        scn(ll, w);
        g[a].pb({i, b});
        g[b].pb({i, a});
        weight[i] = w;
        A[i] = a;
        B[i] = b;
    }

    // init
    allDist.init(N, -LLINF);
    decomp(1, 0);

    ll lastAns = 0;
    while (Q--) {
        scn(ll, e, w);
        e = (e + lastAns) % (N - 1);
        w = (w + lastAns) % W;
        
        // update centroid tree 
        ll dif = w - weight[e];
        for (int cent : hasEdge[e]) {
            int chid = chForEdge[lv[cent]][e], to = g[cent][chid].v;
            auto &ps = paths[cent];

            int bot = ps.getBottomNode(A[e], B[e]);
            ps.inc(bot, dif);
            centDist[cent].update(chid, mpr(ps.get(to), 0));
            pll dia = centDist[cent].query(0, g[cent].size() - 1);
            preAllDist[cent] = dia.first + dia.second;
            allDist.update(cent - 1, preAllDist[cent]);
        }
        weight[e] = w;

        // print ans
        lastAns = allDist.query(0, N - 1);
        println(lastAns);
    }

    return 0;
}

Compilation message

diameter.cpp:1:0: warning: ignoring #pragma region  [-Wunknown-pragmas]
 #pragma region
 
diameter.cpp:68:0: warning: ignoring #pragma endregion  [-Wunknown-pragmas]
 #pragma endregion

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22400 KB Output is correct
2 Correct 17 ms 22400 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 20 ms 22400 KB Output is correct
5 Correct 21 ms 22400 KB Output is correct
6 Correct 18 ms 22392 KB Output is correct
7 Correct 20 ms 22400 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 21 ms 22400 KB Output is correct
10 Correct 18 ms 22400 KB Output is correct
11 Correct 29 ms 22400 KB Output is correct
12 Correct 18 ms 22400 KB Output is correct
13 Correct 22 ms 22400 KB Output is correct
14 Correct 21 ms 22400 KB Output is correct
15 Correct 22 ms 22392 KB Output is correct
16 Correct 18 ms 22400 KB Output is correct
17 Correct 22 ms 22392 KB Output is correct
18 Correct 18 ms 22400 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22400 KB Output is correct
2 Correct 17 ms 22400 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 20 ms 22400 KB Output is correct
5 Correct 21 ms 22400 KB Output is correct
6 Correct 18 ms 22392 KB Output is correct
7 Correct 20 ms 22400 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 21 ms 22400 KB Output is correct
10 Correct 18 ms 22400 KB Output is correct
11 Correct 29 ms 22400 KB Output is correct
12 Correct 18 ms 22400 KB Output is correct
13 Correct 22 ms 22400 KB Output is correct
14 Correct 21 ms 22400 KB Output is correct
15 Correct 22 ms 22392 KB Output is correct
16 Correct 18 ms 22400 KB Output is correct
17 Correct 22 ms 22392 KB Output is correct
18 Correct 18 ms 22400 KB Output is correct
19 Correct 34 ms 23032 KB Output is correct
20 Correct 34 ms 23168 KB Output is correct
21 Correct 36 ms 23168 KB Output is correct
22 Correct 38 ms 23296 KB Output is correct
23 Correct 48 ms 25600 KB Output is correct
24 Correct 61 ms 26364 KB Output is correct
25 Correct 73 ms 26872 KB Output is correct
26 Correct 97 ms 27644 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 22272 KB Output is correct
2 Correct 19 ms 22344 KB Output is correct
3 Correct 21 ms 22392 KB Output is correct
4 Correct 27 ms 22608 KB Output is correct
5 Correct 66 ms 23416 KB Output is correct
6 Correct 18 ms 22272 KB Output is correct
7 Correct 18 ms 22400 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 20 ms 22400 KB Output is correct
10 Correct 35 ms 22776 KB Output is correct
11 Correct 89 ms 23928 KB Output is correct
12 Correct 21 ms 23296 KB Output is correct
13 Correct 26 ms 23424 KB Output is correct
14 Correct 26 ms 23424 KB Output is correct
15 Correct 42 ms 23680 KB Output is correct
16 Correct 112 ms 24824 KB Output is correct
17 Correct 105 ms 42576 KB Output is correct
18 Correct 108 ms 42596 KB Output is correct
19 Correct 111 ms 42600 KB Output is correct
20 Correct 140 ms 42728 KB Output is correct
21 Correct 312 ms 43240 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 23168 KB Output is correct
2 Correct 44 ms 23168 KB Output is correct
3 Correct 127 ms 23776 KB Output is correct
4 Correct 218 ms 24440 KB Output is correct
5 Correct 56 ms 31224 KB Output is correct
6 Correct 104 ms 31352 KB Output is correct
7 Correct 309 ms 31980 KB Output is correct
8 Correct 546 ms 32760 KB Output is correct
9 Correct 270 ms 72304 KB Output is correct
10 Correct 366 ms 72560 KB Output is correct
11 Correct 715 ms 72944 KB Output is correct
12 Correct 1004 ms 73456 KB Output is correct
13 Correct 533 ms 126920 KB Output is correct
14 Correct 575 ms 126928 KB Output is correct
15 Correct 940 ms 127220 KB Output is correct
16 Correct 1415 ms 127636 KB Output is correct
17 Correct 2448 ms 127620 KB Output is correct

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2443 ms 114664 KB Output is correct
2 Correct 2512 ms 117128 KB Output is correct
3 Correct 2454 ms 115448 KB Output is correct
4 Correct 2770 ms 117100 KB Output is correct
5 Correct 2354 ms 111932 KB Output is correct
6 Correct 2058 ms 90192 KB Output is correct
7 Correct 3423 ms 136660 KB Output is correct
8 Correct 3553 ms 136324 KB Output is correct
9 Correct 3327 ms 136524 KB Output is correct
10 Correct 3181 ms 135916 KB Output is correct
11 Correct 3221 ms 130464 KB Output is correct
12 Correct 2880 ms 101948 KB Output is correct
13 Correct 3531 ms 146764 KB Output is correct
14 Correct 3399 ms 146332 KB Output is correct
15 Correct 3659 ms 146276 KB Output is correct
16 Correct 3381 ms 145784 KB Output is correct
17 Correct 3426 ms 139456 KB Output is correct
18 Correct 2903 ms 106364 KB Output is correct
19 Correct 3651 ms 146372 KB Output is correct
20 Correct 3558 ms 146452 KB Output is correct
21 Correct 3497 ms 146276 KB Output is correct
22 Correct 3753 ms 145956 KB Output is correct
23 Correct 3683 ms 139304 KB Output is correct
24 Correct 3115 ms 106380 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 22400 KB Output is correct
2 Correct 17 ms 22400 KB Output is correct
3 Correct 17 ms 22400 KB Output is correct
4 Correct 20 ms 22400 KB Output is correct
5 Correct 21 ms 22400 KB Output is correct
6 Correct 18 ms 22392 KB Output is correct
7 Correct 20 ms 22400 KB Output is correct
8 Correct 18 ms 22400 KB Output is correct
9 Correct 21 ms 22400 KB Output is correct
10 Correct 18 ms 22400 KB Output is correct
11 Correct 29 ms 22400 KB Output is correct
12 Correct 18 ms 22400 KB Output is correct
13 Correct 22 ms 22400 KB Output is correct
14 Correct 21 ms 22400 KB Output is correct
15 Correct 22 ms 22392 KB Output is correct
16 Correct 18 ms 22400 KB Output is correct
17 Correct 22 ms 22392 KB Output is correct
18 Correct 18 ms 22400 KB Output is correct
19 Correct 34 ms 23032 KB Output is correct
20 Correct 34 ms 23168 KB Output is correct
21 Correct 36 ms 23168 KB Output is correct
22 Correct 38 ms 23296 KB Output is correct
23 Correct 48 ms 25600 KB Output is correct
24 Correct 61 ms 26364 KB Output is correct
25 Correct 73 ms 26872 KB Output is correct
26 Correct 97 ms 27644 KB Output is correct
27 Correct 18 ms 22272 KB Output is correct
28 Correct 19 ms 22344 KB Output is correct
29 Correct 21 ms 22392 KB Output is correct
30 Correct 27 ms 22608 KB Output is correct
31 Correct 66 ms 23416 KB Output is correct
32 Correct 18 ms 22272 KB Output is correct
33 Correct 18 ms 22400 KB Output is correct
34 Correct 18 ms 22400 KB Output is correct
35 Correct 20 ms 22400 KB Output is correct
36 Correct 35 ms 22776 KB Output is correct
37 Correct 89 ms 23928 KB Output is correct
38 Correct 21 ms 23296 KB Output is correct
39 Correct 26 ms 23424 KB Output is correct
40 Correct 26 ms 23424 KB Output is correct
41 Correct 42 ms 23680 KB Output is correct
42 Correct 112 ms 24824 KB Output is correct
43 Correct 105 ms 42576 KB Output is correct
44 Correct 108 ms 42596 KB Output is correct
45 Correct 111 ms 42600 KB Output is correct
46 Correct 140 ms 42728 KB Output is correct
47 Correct 312 ms 43240 KB Output is correct
48 Correct 35 ms 23168 KB Output is correct
49 Correct 44 ms 23168 KB Output is correct
50 Correct 127 ms 23776 KB Output is correct
51 Correct 218 ms 24440 KB Output is correct
52 Correct 56 ms 31224 KB Output is correct
53 Correct 104 ms 31352 KB Output is correct
54 Correct 309 ms 31980 KB Output is correct
55 Correct 546 ms 32760 KB Output is correct
56 Correct 270 ms 72304 KB Output is correct
57 Correct 366 ms 72560 KB Output is correct
58 Correct 715 ms 72944 KB Output is correct
59 Correct 1004 ms 73456 KB Output is correct
60 Correct 533 ms 126920 KB Output is correct
61 Correct 575 ms 126928 KB Output is correct
62 Correct 940 ms 127220 KB Output is correct
63 Correct 1415 ms 127636 KB Output is correct
64 Correct 2448 ms 127620 KB Output is correct
65 Correct 2443 ms 114664 KB Output is correct
66 Correct 2512 ms 117128 KB Output is correct
67 Correct 2454 ms 115448 KB Output is correct
68 Correct 2770 ms 117100 KB Output is correct
69 Correct 2354 ms 111932 KB Output is correct
70 Correct 2058 ms 90192 KB Output is correct
71 Correct 3423 ms 136660 KB Output is correct
72 Correct 3553 ms 136324 KB Output is correct
73 Correct 3327 ms 136524 KB Output is correct
74 Correct 3181 ms 135916 KB Output is correct
75 Correct 3221 ms 130464 KB Output is correct
76 Correct 2880 ms 101948 KB Output is correct
77 Correct 3531 ms 146764 KB Output is correct
78 Correct 3399 ms 146332 KB Output is correct
79 Correct 3659 ms 146276 KB Output is correct
80 Correct 3381 ms 145784 KB Output is correct
81 Correct 3426 ms 139456 KB Output is correct
82 Correct 2903 ms 106364 KB Output is correct
83 Correct 3651 ms 146372 KB Output is correct
84 Correct 3558 ms 146452 KB Output is correct
85 Correct 3497 ms 146276 KB Output is correct
86 Correct 3753 ms 145956 KB Output is correct
87 Correct 3683 ms 139304 KB Output is correct
88 Correct 3115 ms 106380 KB Output is correct
89 Correct 2428 ms 115508 KB Output is correct
90 Correct 3523 ms 123356 KB Output is correct
91 Correct 3649 ms 132548 KB Output is correct
92 Correct 3422 ms 135348 KB Output is correct
93 Correct 3291 ms 138756 KB Output is correct
94 Correct 3399 ms 144880 KB Output is correct
95 Correct 3845 ms 148096 KB Output is correct
96 Correct 4269 ms 148316 KB Output is correct
97 Correct 4054 ms 148264 KB Output is correct
98 Correct 3897 ms 148900 KB Output is correct
99 Correct 3633 ms 148200 KB Output is correct
100 Correct 3391 ms 148156 KB Output is correct