oj.uz

Submission #394135

# Submission time Handle Problem Language Result Execution time Memory
394135 2021-04-25T18:15:22 Z usachevd0 Food Court (JOI21_foodcourt) C++14
100 / 100
 961 ms 39956 KB 
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define all(a) (a).begin(), (a).end()
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
using ld = long double;
template<typename T1, typename T2> bool chkmin(T1& x, T2 y) {
  return y < x ? (x = y, true) : false;
}
template<typename T1, typename T2> bool chkmax(T1& x, T2 y) {
  return y > x ? (x = y, true) : false;
}
void debug_out() {
  cerr << endl;
}
template<typename T1, typename... T2> void debug_out(T1 A, T2... B) {
  cerr << ' ' << A;
  debug_out(B...);
}
template<typename T> void mdebug_out(T* a, int n) {
  for (int i = 0; i < n; ++i) cerr << a[i];
  cerr << endl;
}
template<typename T> ostream& operator << (ostream& stream, const vector<T>& v) {
  for (auto& x : v) {
    stream << x << ' ';
  }
  return stream;
}
template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) {
  return stream << p.first << ' ' << p.second;
}

#ifdef DEBUG
  #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
  #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n)
#else
  #define debug(...) 1337
  #define mdebug(a, n) 1337
#endif

const ll INF64 = 1e18;
const int maxN = 250005;
int N, M, Q;

int VL[maxN], VR[maxN], VM[maxN];
vector<int> qb[maxN];

namespace sgt1 {
  const int logN = 18;
  const int N = 1 << logN;

  struct Node {
    ll sz;
    ll min1, min2;
    ll lazy_all, lazy_min;

    Node() {
      sz = 0;
      min1 = 0;
      min2 = +INF64;
      lazy_all = lazy_min = 0;
    }
  } t[2 * N];

  void upd(int v) {
    t[v].min1 = t[v << 1].min1;
    t[v].min2 = t[v << 1].min2;
    if (t[v << 1 | 1].min1 < t[v].min1) {
      t[v].min2 = t[v].min1;
      t[v].min1 = t[v << 1 | 1].min1;
      chkmin(t[v].min2, t[v << 1 | 1].min2);
    } else if (t[v << 1 | 1].min1 > t[v].min1) {
      chkmin(t[v].min2, t[v << 1 | 1].min1);
    } else {
      chkmin(t[v].min2, t[v << 1 | 1].min2);
    }
  }

  void apply1(int v, ll d) {
    t[v].sz += d;
  }

  void apply2_all(int v, ll d) {
    t[v].min1 += d;
    t[v].min2 += d;
    t[v].lazy_all += d;
  }

  void apply2_min(int v, ll d) {
    t[v].min1 += d;
    t[v].lazy_min += d;
  }

  void push(int v) {
    for (int u : {v << 1, v << 1 | 1}) {
      if (t[v].sz) {
        apply1(u, t[v].sz);
      }
      if (t[v].lazy_all) {
        apply2_all(u, t[v].lazy_all);
      }
      if (t[v].lazy_min && t[v].min1 - t[v].lazy_min == t[u].min1) {
        apply2_min(u, t[v].lazy_min);
      }
    }
    t[v].sz = t[v].lazy_all = t[v].lazy_min = 0;
  }

  void add1(int v, int vl, int vr, int l, int r, ll d) {
    if (l > r || vr < l || r < vl) return;
    if (l <= vl && vr <= r) {
      apply1(v, d);
      apply2_all(v, d);
      return;
    } 
    int vm = (vl + vr) >> 1;
    push(v);
    add1(v << 1, vl, vm, l, r, d);
    add1(v << 1 | 1, vm + 1, vr, l, r, d);
    upd(v);
  }

  void add2(int v, int vl, int vr, int l, int r, ll d) {
    if (l > r || vr < l || r < vl) return;
    if (l <= vl && vr <= r) {
      apply2_all(v, d);
      return;
    }
    int vm = (vl + vr) >> 1;
    push(v);
    add2(v << 1, vl, vm, l, r, d);
    add2(v << 1 | 1, vm + 1, vr, l, r, d);
    upd(v);
  }

  void umax0(int v, int vl, int vr, int l, int r) {
    if (l > r || vr < l || r < vl || t[v].min1 >= 0) return;
    if (l <= vl && vr <= r && t[v].min2 > 0) {
      apply2_min(v, -t[v].min1);
      return;
    }
    int vm = (vl + vr) >> 1;
    push(v);
    umax0(v << 1, vl, vm, l, r);
    umax0(v << 1 | 1, vm + 1, vr, l, r);
    upd(v);
  }

  pll gt(int v, int vl, int vr, int i) {
    if (vl == vr) {
      return {t[v].sz, t[v].lazy_all + t[v].lazy_min};
    }
    int vm = (vl + vr) >> 1;
    push(v);
    if (i <= vm) {
      return gt(v << 1, vl, vm, i);
    } else {
      return gt(v << 1 | 1, vm + 1, vr, i);
    }
  }
}

struct Query1 {
  int l, r, c, k;
  
  Query1() {}

  void read() {
    cin >> l >> r >> c >> k;
  }
} qr1[maxN];
int qr1_t[maxN];

struct Query3 {
  int i;
  ll k;
} qr3[maxN];
int qr3_t[maxN];

namespace fnw {
  ll f[maxN];
  void reset() {
    fill(f, f + N + 1, 0);
  }
  void add(int i, ll d) {
    for (; i <= N; i += i & -i) {
      f[i] += d;
    }
  }
  void add(int l, int r, ll d) {
    add(l, d);
    add(r + 1, -d);
  }
  ll gt(int i) {
    ll ans = 0;
    for (; i >= 1; i -= i & -i) {
      ans += f[i];
    }
    return ans;
  }
}


int32_t main() {
#ifdef DEBUG
  freopen("in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> N >> M >> Q;
  int T = 0;
  int Q1 = 0;
  for (int qi = 0; qi < Q; ++qi) {
    int tp;
    cin >> tp;
    if (tp == 1) {
      auto& q = qr1[Q1];
      q.read();
      qr1_t[Q1++] = T;

      sgt1::add1(1, 1, N, q.l, q.r, q.k);
    } else if (tp == 2) {
      int l, r, k;
      cin >> l >> r >> k;
      sgt1::add2(1, 1, N, l, r, -k);
      sgt1::umax0(1, 1, N, l, r);
    } else {
      auto& q = qr3[T];
      cin >> q.i >> q.k;
      --q.k;
      qr3_t[T++] = Q1;

      auto f = sgt1::gt(1, 1, N, q.i);
      q.k += f.fi - f.se;
    }
  }
  for (int i = 0; i < T; ++i) {
    VL[i] = -1;
    VR[i] = qr3_t[i];
  }
  while (true) {
    bool found = false;
    for (int i = 0; i < T; ++i) {
      if (VR[i] - VL[i] > 1) {
        found = true;
        VM[i] = (VL[i] + VR[i]) / 2;
        qb[VM[i]].push_back(i);
      }
    }
    if (!found) {
      break;
    }
    fnw::reset();
    for (int j = 0; j < Q1; ++j) {
      auto& q = qr1[j];
      fnw::add(q.l, q.r, q.k);
      for (int i : qb[j]) {
        if (fnw::gt(qr3[i].i) <= qr3[i].k) {
          VL[i] = VM[i];
        } else {
          VR[i] = VM[i];
        }
      }
      qb[j].clear();
    }
  }
  for (int i = 0; i < T; ++i) {
    if (VR[i] == qr3_t[i]) {
      cout << "0\n";
    } else {
      cout << qr1[VR[i]].c << '\n';
    }
  }

  return 0;
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26700 KB Output is correct
2 Correct 20 ms 26828 KB Output is correct
3 Correct 15 ms 26796 KB Output is correct
4 Correct 20 ms 26768 KB Output is correct
5 Correct 14 ms 26744 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 16 ms 26828 KB Output is correct
8 Correct 16 ms 26828 KB Output is correct
9 Correct 18 ms 26828 KB Output is correct
10 Correct 18 ms 26748 KB Output is correct
11 Correct 17 ms 26748 KB Output is correct
12 Correct 19 ms 26728 KB Output is correct
13 Correct 14 ms 26700 KB Output is correct
14 Correct 15 ms 26828 KB Output is correct
15 Correct 14 ms 26712 KB Output is correct
16 Correct 18 ms 26772 KB Output is correct
17 Correct 20 ms 26768 KB Output is correct
18 Correct 20 ms 26764 KB Output is correct
19 Correct 19 ms 26840 KB Output is correct
20 Correct 19 ms 26844 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26700 KB Output is correct
2 Correct 20 ms 26828 KB Output is correct
3 Correct 15 ms 26796 KB Output is correct
4 Correct 20 ms 26768 KB Output is correct
5 Correct 14 ms 26744 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 16 ms 26828 KB Output is correct
8 Correct 16 ms 26828 KB Output is correct
9 Correct 18 ms 26828 KB Output is correct
10 Correct 18 ms 26748 KB Output is correct
11 Correct 17 ms 26748 KB Output is correct
12 Correct 19 ms 26728 KB Output is correct
13 Correct 14 ms 26700 KB Output is correct
14 Correct 15 ms 26828 KB Output is correct
15 Correct 14 ms 26712 KB Output is correct
16 Correct 18 ms 26772 KB Output is correct
17 Correct 20 ms 26768 KB Output is correct
18 Correct 20 ms 26764 KB Output is correct
19 Correct 19 ms 26840 KB Output is correct
20 Correct 19 ms 26844 KB Output is correct
21 Correct 16 ms 26772 KB Output is correct
22 Correct 16 ms 26724 KB Output is correct
23 Correct 16 ms 26752 KB Output is correct
24 Correct 17 ms 26828 KB Output is correct
25 Correct 14 ms 26708 KB Output is correct
26 Correct 16 ms 26736 KB Output is correct
27 Correct 16 ms 26828 KB Output is correct
28 Correct 17 ms 26756 KB Output is correct
29 Correct 16 ms 26804 KB Output is correct
30 Correct 16 ms 26780 KB Output is correct
31 Correct 19 ms 26744 KB Output is correct
32 Correct 16 ms 26828 KB Output is correct
33 Correct 16 ms 26712 KB Output is correct
34 Correct 15 ms 26880 KB Output is correct
35 Correct 14 ms 26828 KB Output is correct
36 Correct 16 ms 26828 KB Output is correct
37 Correct 15 ms 26828 KB Output is correct
38 Correct 16 ms 26764 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 29244 KB Output is correct
2 Correct 159 ms 29384 KB Output is correct
3 Correct 154 ms 29236 KB Output is correct
4 Correct 154 ms 29248 KB Output is correct
5 Correct 153 ms 29380 KB Output is correct
6 Correct 152 ms 29440 KB Output is correct
7 Correct 60 ms 28680 KB Output is correct
8 Correct 47 ms 28612 KB Output is correct
9 Correct 142 ms 29568 KB Output is correct
10 Correct 162 ms 29116 KB Output is correct
11 Correct 148 ms 29248 KB Output is correct
12 Correct 192 ms 29124 KB Output is correct
13 Correct 154 ms 29312 KB Output is correct
14 Correct 145 ms 29808 KB Output is correct
15 Correct 231 ms 29980 KB Output is correct
16 Correct 276 ms 30148 KB Output is correct

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 697 ms 35436 KB Output is correct
2 Correct 599 ms 33820 KB Output is correct
3 Correct 738 ms 36204 KB Output is correct
4 Correct 563 ms 34748 KB Output is correct
5 Correct 623 ms 34504 KB Output is correct
6 Correct 753 ms 37228 KB Output is correct
7 Correct 164 ms 34280 KB Output is correct
8 Correct 171 ms 34496 KB Output is correct
9 Correct 803 ms 39488 KB Output is correct
10 Correct 877 ms 39672 KB Output is correct
11 Correct 734 ms 37756 KB Output is correct
12 Correct 882 ms 35880 KB Output is correct
13 Correct 672 ms 37764 KB Output is correct
14 Correct 767 ms 35936 KB Output is correct
15 Correct 765 ms 36056 KB Output is correct
16 Correct 780 ms 36548 KB Output is correct
17 Correct 870 ms 35844 KB Output is correct
18 Correct 797 ms 36760 KB Output is correct
19 Correct 824 ms 35832 KB Output is correct
20 Correct 818 ms 36764 KB Output is correct
21 Correct 877 ms 35968 KB Output is correct
22 Correct 860 ms 35908 KB Output is correct
23 Correct 820 ms 35996 KB Output is correct
24 Correct 886 ms 35716 KB Output is correct
25 Correct 578 ms 35732 KB Output is correct
26 Correct 556 ms 36220 KB Output is correct
27 Correct 754 ms 38320 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26700 KB Output is correct
2 Correct 20 ms 26828 KB Output is correct
3 Correct 15 ms 26796 KB Output is correct
4 Correct 20 ms 26768 KB Output is correct
5 Correct 14 ms 26744 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 16 ms 26828 KB Output is correct
8 Correct 16 ms 26828 KB Output is correct
9 Correct 18 ms 26828 KB Output is correct
10 Correct 18 ms 26748 KB Output is correct
11 Correct 17 ms 26748 KB Output is correct
12 Correct 19 ms 26728 KB Output is correct
13 Correct 14 ms 26700 KB Output is correct
14 Correct 15 ms 26828 KB Output is correct
15 Correct 14 ms 26712 KB Output is correct
16 Correct 18 ms 26772 KB Output is correct
17 Correct 20 ms 26768 KB Output is correct
18 Correct 20 ms 26764 KB Output is correct
19 Correct 19 ms 26840 KB Output is correct
20 Correct 19 ms 26844 KB Output is correct
21 Correct 196 ms 29244 KB Output is correct
22 Correct 159 ms 29384 KB Output is correct
23 Correct 154 ms 29236 KB Output is correct
24 Correct 154 ms 29248 KB Output is correct
25 Correct 153 ms 29380 KB Output is correct
26 Correct 152 ms 29440 KB Output is correct
27 Correct 60 ms 28680 KB Output is correct
28 Correct 47 ms 28612 KB Output is correct
29 Correct 142 ms 29568 KB Output is correct
30 Correct 162 ms 29116 KB Output is correct
31 Correct 148 ms 29248 KB Output is correct
32 Correct 192 ms 29124 KB Output is correct
33 Correct 154 ms 29312 KB Output is correct
34 Correct 145 ms 29808 KB Output is correct
35 Correct 231 ms 29980 KB Output is correct
36 Correct 276 ms 30148 KB Output is correct
37 Correct 130 ms 29000 KB Output is correct
38 Correct 144 ms 28924 KB Output is correct
39 Correct 38 ms 28200 KB Output is correct
40 Correct 44 ms 28416 KB Output is correct
41 Correct 139 ms 29552 KB Output is correct
42 Correct 178 ms 29112 KB Output is correct
43 Correct 158 ms 29044 KB Output is correct
44 Correct 138 ms 29288 KB Output is correct
45 Correct 144 ms 29124 KB Output is correct
46 Correct 180 ms 29060 KB Output is correct
47 Correct 70 ms 29220 KB Output is correct
48 Correct 129 ms 29252 KB Output is correct
49 Correct 147 ms 28320 KB Output is correct
50 Correct 172 ms 28744 KB Output is correct
51 Correct 182 ms 29012 KB Output is correct
52 Correct 169 ms 29024 KB Output is correct
53 Correct 130 ms 29372 KB Output is correct
54 Correct 156 ms 30148 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 29852 KB Output is correct
2 Correct 149 ms 29968 KB Output is correct
3 Correct 183 ms 30208 KB Output is correct
4 Correct 109 ms 29300 KB Output is correct
5 Correct 126 ms 29760 KB Output is correct
6 Correct 178 ms 30112 KB Output is correct
7 Correct 70 ms 29292 KB Output is correct
8 Correct 58 ms 29124 KB Output is correct
9 Correct 101 ms 30128 KB Output is correct
10 Correct 97 ms 29144 KB Output is correct
11 Correct 145 ms 30148 KB Output is correct
12 Correct 260 ms 30124 KB Output is correct

Subtask #7
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26700 KB Output is correct
2 Correct 20 ms 26828 KB Output is correct
3 Correct 15 ms 26796 KB Output is correct
4 Correct 20 ms 26768 KB Output is correct
5 Correct 14 ms 26744 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 16 ms 26828 KB Output is correct
8 Correct 16 ms 26828 KB Output is correct
9 Correct 18 ms 26828 KB Output is correct
10 Correct 18 ms 26748 KB Output is correct
11 Correct 17 ms 26748 KB Output is correct
12 Correct 19 ms 26728 KB Output is correct
13 Correct 14 ms 26700 KB Output is correct
14 Correct 15 ms 26828 KB Output is correct
15 Correct 14 ms 26712 KB Output is correct
16 Correct 18 ms 26772 KB Output is correct
17 Correct 20 ms 26768 KB Output is correct
18 Correct 20 ms 26764 KB Output is correct
19 Correct 19 ms 26840 KB Output is correct
20 Correct 19 ms 26844 KB Output is correct
21 Correct 16 ms 26772 KB Output is correct
22 Correct 16 ms 26724 KB Output is correct
23 Correct 16 ms 26752 KB Output is correct
24 Correct 17 ms 26828 KB Output is correct
25 Correct 14 ms 26708 KB Output is correct
26 Correct 16 ms 26736 KB Output is correct
27 Correct 16 ms 26828 KB Output is correct
28 Correct 17 ms 26756 KB Output is correct
29 Correct 16 ms 26804 KB Output is correct
30 Correct 16 ms 26780 KB Output is correct
31 Correct 19 ms 26744 KB Output is correct
32 Correct 16 ms 26828 KB Output is correct
33 Correct 16 ms 26712 KB Output is correct
34 Correct 15 ms 26880 KB Output is correct
35 Correct 14 ms 26828 KB Output is correct
36 Correct 16 ms 26828 KB Output is correct
37 Correct 15 ms 26828 KB Output is correct
38 Correct 16 ms 26764 KB Output is correct
39 Correct 196 ms 29244 KB Output is correct
40 Correct 159 ms 29384 KB Output is correct
41 Correct 154 ms 29236 KB Output is correct
42 Correct 154 ms 29248 KB Output is correct
43 Correct 153 ms 29380 KB Output is correct
44 Correct 152 ms 29440 KB Output is correct
45 Correct 60 ms 28680 KB Output is correct
46 Correct 47 ms 28612 KB Output is correct
47 Correct 142 ms 29568 KB Output is correct
48 Correct 162 ms 29116 KB Output is correct
49 Correct 148 ms 29248 KB Output is correct
50 Correct 192 ms 29124 KB Output is correct
51 Correct 154 ms 29312 KB Output is correct
52 Correct 145 ms 29808 KB Output is correct
53 Correct 231 ms 29980 KB Output is correct
54 Correct 276 ms 30148 KB Output is correct
55 Correct 130 ms 29000 KB Output is correct
56 Correct 144 ms 28924 KB Output is correct
57 Correct 38 ms 28200 KB Output is correct
58 Correct 44 ms 28416 KB Output is correct
59 Correct 139 ms 29552 KB Output is correct
60 Correct 178 ms 29112 KB Output is correct
61 Correct 158 ms 29044 KB Output is correct
62 Correct 138 ms 29288 KB Output is correct
63 Correct 144 ms 29124 KB Output is correct
64 Correct 180 ms 29060 KB Output is correct
65 Correct 70 ms 29220 KB Output is correct
66 Correct 129 ms 29252 KB Output is correct
67 Correct 147 ms 28320 KB Output is correct
68 Correct 172 ms 28744 KB Output is correct
69 Correct 182 ms 29012 KB Output is correct
70 Correct 169 ms 29024 KB Output is correct
71 Correct 130 ms 29372 KB Output is correct
72 Correct 156 ms 30148 KB Output is correct
73 Correct 129 ms 29852 KB Output is correct
74 Correct 149 ms 29968 KB Output is correct
75 Correct 183 ms 30208 KB Output is correct
76 Correct 109 ms 29300 KB Output is correct
77 Correct 126 ms 29760 KB Output is correct
78 Correct 178 ms 30112 KB Output is correct
79 Correct 70 ms 29292 KB Output is correct
80 Correct 58 ms 29124 KB Output is correct
81 Correct 101 ms 30128 KB Output is correct
82 Correct 97 ms 29144 KB Output is correct
83 Correct 145 ms 30148 KB Output is correct
84 Correct 260 ms 30124 KB Output is correct
85 Correct 195 ms 29036 KB Output is correct
86 Correct 144 ms 29260 KB Output is correct
87 Correct 134 ms 29096 KB Output is correct
88 Correct 153 ms 29408 KB Output is correct
89 Correct 102 ms 28640 KB Output is correct
90 Correct 177 ms 29104 KB Output is correct
91 Correct 131 ms 28692 KB Output is correct
92 Correct 137 ms 28548 KB Output is correct
93 Correct 222 ms 29116 KB Output is correct
94 Correct 231 ms 29252 KB Output is correct
95 Correct 134 ms 29068 KB Output is correct
96 Correct 147 ms 29156 KB Output is correct
97 Correct 196 ms 29084 KB Output is correct
98 Correct 162 ms 28604 KB Output is correct
99 Correct 83 ms 29160 KB Output is correct
100 Correct 106 ms 28848 KB Output is correct
101 Correct 129 ms 29236 KB Output is correct
102 Correct 152 ms 29744 KB Output is correct

Subtask #8
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26700 KB Output is correct
2 Correct 20 ms 26828 KB Output is correct
3 Correct 15 ms 26796 KB Output is correct
4 Correct 20 ms 26768 KB Output is correct
5 Correct 14 ms 26744 KB Output is correct
6 Correct 14 ms 26716 KB Output is correct
7 Correct 16 ms 26828 KB Output is correct
8 Correct 16 ms 26828 KB Output is correct
9 Correct 18 ms 26828 KB Output is correct
10 Correct 18 ms 26748 KB Output is correct
11 Correct 17 ms 26748 KB Output is correct
12 Correct 19 ms 26728 KB Output is correct
13 Correct 14 ms 26700 KB Output is correct
14 Correct 15 ms 26828 KB Output is correct
15 Correct 14 ms 26712 KB Output is correct
16 Correct 18 ms 26772 KB Output is correct
17 Correct 20 ms 26768 KB Output is correct
18 Correct 20 ms 26764 KB Output is correct
19 Correct 19 ms 26840 KB Output is correct
20 Correct 19 ms 26844 KB Output is correct
21 Correct 16 ms 26772 KB Output is correct
22 Correct 16 ms 26724 KB Output is correct
23 Correct 16 ms 26752 KB Output is correct
24 Correct 17 ms 26828 KB Output is correct
25 Correct 14 ms 26708 KB Output is correct
26 Correct 16 ms 26736 KB Output is correct
27 Correct 16 ms 26828 KB Output is correct
28 Correct 17 ms 26756 KB Output is correct
29 Correct 16 ms 26804 KB Output is correct
30 Correct 16 ms 26780 KB Output is correct
31 Correct 19 ms 26744 KB Output is correct
32 Correct 16 ms 26828 KB Output is correct
33 Correct 16 ms 26712 KB Output is correct
34 Correct 15 ms 26880 KB Output is correct
35 Correct 14 ms 26828 KB Output is correct
36 Correct 16 ms 26828 KB Output is correct
37 Correct 15 ms 26828 KB Output is correct
38 Correct 16 ms 26764 KB Output is correct
39 Correct 196 ms 29244 KB Output is correct
40 Correct 159 ms 29384 KB Output is correct
41 Correct 154 ms 29236 KB Output is correct
42 Correct 154 ms 29248 KB Output is correct
43 Correct 153 ms 29380 KB Output is correct
44 Correct 152 ms 29440 KB Output is correct
45 Correct 60 ms 28680 KB Output is correct
46 Correct 47 ms 28612 KB Output is correct
47 Correct 142 ms 29568 KB Output is correct
48 Correct 162 ms 29116 KB Output is correct
49 Correct 148 ms 29248 KB Output is correct
50 Correct 192 ms 29124 KB Output is correct
51 Correct 154 ms 29312 KB Output is correct
52 Correct 145 ms 29808 KB Output is correct
53 Correct 231 ms 29980 KB Output is correct
54 Correct 276 ms 30148 KB Output is correct
55 Correct 697 ms 35436 KB Output is correct
56 Correct 599 ms 33820 KB Output is correct
57 Correct 738 ms 36204 KB Output is correct
58 Correct 563 ms 34748 KB Output is correct
59 Correct 623 ms 34504 KB Output is correct
60 Correct 753 ms 37228 KB Output is correct
61 Correct 164 ms 34280 KB Output is correct
62 Correct 171 ms 34496 KB Output is correct
63 Correct 803 ms 39488 KB Output is correct
64 Correct 877 ms 39672 KB Output is correct
65 Correct 734 ms 37756 KB Output is correct
66 Correct 882 ms 35880 KB Output is correct
67 Correct 672 ms 37764 KB Output is correct
68 Correct 767 ms 35936 KB Output is correct
69 Correct 765 ms 36056 KB Output is correct
70 Correct 780 ms 36548 KB Output is correct
71 Correct 870 ms 35844 KB Output is correct
72 Correct 797 ms 36760 KB Output is correct
73 Correct 824 ms 35832 KB Output is correct
74 Correct 818 ms 36764 KB Output is correct
75 Correct 877 ms 35968 KB Output is correct
76 Correct 860 ms 35908 KB Output is correct
77 Correct 820 ms 35996 KB Output is correct
78 Correct 886 ms 35716 KB Output is correct
79 Correct 578 ms 35732 KB Output is correct
80 Correct 556 ms 36220 KB Output is correct
81 Correct 754 ms 38320 KB Output is correct
82 Correct 130 ms 29000 KB Output is correct
83 Correct 144 ms 28924 KB Output is correct
84 Correct 38 ms 28200 KB Output is correct
85 Correct 44 ms 28416 KB Output is correct
86 Correct 139 ms 29552 KB Output is correct
87 Correct 178 ms 29112 KB Output is correct
88 Correct 158 ms 29044 KB Output is correct
89 Correct 138 ms 29288 KB Output is correct
90 Correct 144 ms 29124 KB Output is correct
91 Correct 180 ms 29060 KB Output is correct
92 Correct 70 ms 29220 KB Output is correct
93 Correct 129 ms 29252 KB Output is correct
94 Correct 147 ms 28320 KB Output is correct
95 Correct 172 ms 28744 KB Output is correct
96 Correct 182 ms 29012 KB Output is correct
97 Correct 169 ms 29024 KB Output is correct
98 Correct 130 ms 29372 KB Output is correct
99 Correct 156 ms 30148 KB Output is correct
100 Correct 129 ms 29852 KB Output is correct
101 Correct 149 ms 29968 KB Output is correct
102 Correct 183 ms 30208 KB Output is correct
103 Correct 109 ms 29300 KB Output is correct
104 Correct 126 ms 29760 KB Output is correct
105 Correct 178 ms 30112 KB Output is correct
106 Correct 70 ms 29292 KB Output is correct
107 Correct 58 ms 29124 KB Output is correct
108 Correct 101 ms 30128 KB Output is correct
109 Correct 97 ms 29144 KB Output is correct
110 Correct 145 ms 30148 KB Output is correct
111 Correct 260 ms 30124 KB Output is correct
112 Correct 195 ms 29036 KB Output is correct
113 Correct 144 ms 29260 KB Output is correct
114 Correct 134 ms 29096 KB Output is correct
115 Correct 153 ms 29408 KB Output is correct
116 Correct 102 ms 28640 KB Output is correct
117 Correct 177 ms 29104 KB Output is correct
118 Correct 131 ms 28692 KB Output is correct
119 Correct 137 ms 28548 KB Output is correct
120 Correct 222 ms 29116 KB Output is correct
121 Correct 231 ms 29252 KB Output is correct
122 Correct 134 ms 29068 KB Output is correct
123 Correct 147 ms 29156 KB Output is correct
124 Correct 196 ms 29084 KB Output is correct
125 Correct 162 ms 28604 KB Output is correct
126 Correct 83 ms 29160 KB Output is correct
127 Correct 106 ms 28848 KB Output is correct
128 Correct 129 ms 29236 KB Output is correct
129 Correct 152 ms 29744 KB Output is correct
130 Correct 775 ms 36484 KB Output is correct
131 Correct 584 ms 33876 KB Output is correct
132 Correct 954 ms 36604 KB Output is correct
133 Correct 842 ms 36852 KB Output is correct
134 Correct 731 ms 35880 KB Output is correct
135 Correct 834 ms 37316 KB Output is correct
136 Correct 818 ms 39956 KB Output is correct
137 Correct 864 ms 39912 KB Output is correct
138 Correct 790 ms 37956 KB Output is correct
139 Correct 802 ms 36064 KB Output is correct
140 Correct 799 ms 38276 KB Output is correct
141 Correct 761 ms 36176 KB Output is correct
142 Correct 762 ms 36636 KB Output is correct
143 Correct 961 ms 36160 KB Output is correct
144 Correct 773 ms 37048 KB Output is correct
145 Correct 756 ms 36036 KB Output is correct
146 Correct 720 ms 37148 KB Output is correct
147 Correct 818 ms 36024 KB Output is correct
148 Correct 791 ms 36080 KB Output is correct
149 Correct 758 ms 36028 KB Output is correct
150 Correct 394 ms 36548 KB Output is correct
151 Correct 544 ms 36712 KB Output is correct
152 Correct 598 ms 36580 KB Output is correct
153 Correct 733 ms 38440 KB Output is correct