oj.uz

Submission #892143

# Submission time Handle Problem Language Result Execution time Memory
892143 2023-12-25T00:59:48 Z MilosMilutinovic New Home (APIO18_new_home) C++14
57 / 100
 5000 ms 418568 KB 
#include <bits/stdc++.h>
 
using namespace std;

const int N = (int) 4e6;

const int inf = (int) 1e9;

int mn[N], mx[N], sz;

void Build(int x, int l, int r) {
  mn[x] = inf;
  mx[x] = -inf;
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  Build(x << 1, l, mid);
  Build(x << 1 | 1, mid + 1, r);
}

void ModifyMin(int x, int l, int r, int p, int v) {
  if (l == r) {
    mn[x] = v;
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid) {
    ModifyMin(x << 1, l, mid, p, v);
  } else {
    ModifyMin(x << 1 | 1, mid + 1, r, p, v);
  }
  mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}

void ModifyMax(int x, int l, int r, int p, int v) {
  if (l == r) {
    mx[x] = v;
    return;
  }
  int mid = l + r >> 1;
  if (p <= mid) {
    ModifyMax(x << 1, l, mid, p, v);
  } else {
    ModifyMax(x << 1 | 1, mid + 1, r, p, v);
  }
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}

void ChangeMin(int p, int v) {
  ModifyMin(1, 0, sz - 1, p, v);
}

void ChangeMax(int p, int v) {
  ModifyMax(1, 0, sz - 1, p, v);
}

int query_max(int x, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll) {
    return -inf;
  }
  if (ll <= l && r <= rr) {
    return mx[x];
  }
  int mid = l + r >> 1;
  return max(query_max(x << 1, l, mid, ll, rr), query_max(x << 1 | 1, mid + 1, r, ll, rr));
}

int query_min(int x, int l, int r, int ll, int rr) {
  if (l > r || l > rr || r < ll) {
    return inf;
  }
  if (ll <= l && r <= rr) {
    return mn[x];
  }
  int mid = l + r >> 1;
  return min(query_min(x << 1, l, mid, ll, rr), query_min(x << 1 | 1, mid + 1, r, ll, rr));
}

int get_max(int l, int r) {
  return query_max(1, 0, sz - 1, l, r);
}

int get_min(int l, int r) {
  return query_min(1, 0, sz - 1, l, r);
}

vector<multiset<tuple<int, int, int>>> open;
vector<array<int, 4>> ev;
vector<multiset<int>> my;

void Insert(int t, int x, int y) {
  auto ptr = my[t].lower_bound(x);
  if (ptr != my[t].begin() && ptr != my[t].end()) {
    auto it = open[t].lower_bound({*prev(ptr), *ptr, -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  } else if (ptr != my[t].begin()) {
    auto it = open[t].lower_bound({*prev(ptr), inf, -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  } else if (ptr != my[t].end()) {
    auto it = open[t].lower_bound({-inf, *ptr, -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  }
  if (ptr != my[t].end()) {
    open[t].emplace(x, *ptr, y);
  } else {
    open[t].emplace(x, inf, y);
  }
  if (ptr != my[t].begin()) {
    ptr = prev(ptr);
    open[t].emplace(*ptr, x, y);
  } else {
    open[t].emplace(-inf, x, y);
  }
  my[t].insert(x);
}

void Remove(int t, int x, int y) {
  auto ptr = my[t].lower_bound(x);
  if (ptr != prev(my[t].end())) {
    auto it = open[t].lower_bound({x, *next(ptr), -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  } else {
    auto it = open[t].lower_bound({x, inf, -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  }
  if (ptr != my[t].begin()) {
    auto it = open[t].lower_bound({*prev(ptr), x, -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  } else {
    auto it = open[t].lower_bound({-inf, x, -1});
    ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
    open[t].erase(it);
  }
  if (ptr != my[t].begin() && ptr != prev(my[t].end())) {
    open[t].emplace(*prev(ptr), *next(ptr), y);
  } else if (ptr != my[t].begin()) {
    open[t].emplace(*prev(ptr), inf, y);
  } else if (ptr != prev(my[t].end())) {
    open[t].emplace(-inf, *next(ptr), y);
  }
  my[t].erase(my[t].find(x));
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k, q;
  cin >> n >> k >> q;
  vector<int> x(n);
  vector<int> t(n);
  vector<int> a(n);
  vector<int> b(n);
  map<pair<int, int>, vector<pair<int, int>>> mp;
  for (int i = 0; i < n; i++) {
    cin >> x[i] >> t[i] >> a[i] >> b[i];
    --t[i]; ++b[i];
    mp[{x[i], t[i]}].emplace_back(a[i], b[i]);
  }
  vector<int> new_x;
  vector<int> new_t;
  vector<int> new_a;
  vector<int> new_b;
  for (auto& p : mp) {
    vector<pair<int, int>> v = p.second;
    sort(v.begin(), v.end());
    int sz = (int) v.size();
    for (int i = 0; i < sz; i++) {
      int ptr = i;
      int mx = v[i].second;
      while (ptr + 1 < sz && v[ptr + 1].first < mx) {
        ptr += 1;
        mx = max(mx, v[ptr].second);
      }
      new_x.push_back(p.first.first);
      new_t.push_back(p.first.second);
      new_a.push_back(v[i].first);
      new_b.push_back(mx);
      i = ptr;
    }
  }
  x = new_x;
  t = new_t;
  a = new_a;
  b = new_b;
  n = (int) x.size();
  vector<int> l(q);
  vector<int> y(q);
  for (int i = 0; i < q; i++) {
    cin >> l[i] >> y[i];
  }
  vector<int> xs(1, 1e9);
  for (int i = 0; i < n; i++) {
    xs.push_back(a[i]);
    xs.push_back(b[i]);
  }
  for (int i = 0; i < q; i++) {
    xs.push_back(y[i]);
  }
  sort(xs.begin(), xs.end());
  xs.erase(unique(xs.begin(), xs.end()), xs.end());
  for (int i = 0; i < n; i++) {
    a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
    b[i] = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
  }
  for (int i = 0; i < q; i++) {
    y[i] = (int) (lower_bound(xs.begin(), xs.end(), y[i]) - xs.begin());
  }
  int T = (int) xs.size();
  vector<vector<int>> ids(T);
  for (int i = 0; i < n; i++) {
    ids[a[i]].push_back(i);
    ids[b[i]].push_back(~i);
  }
  open.resize(k);
  my.resize(k);
  for (int i = 0; i < T; i++) {
    sort(ids[i].begin(), ids[i].end());
    for (int j : ids[i]) {
      if (j >= 0) {
        Insert(t[j], x[j], i);
      } else {
        j = ~j;
        Remove(t[j], x[j], i);
      }
    }
  }
  for (int i = 0; i < k; i++) {
    for (auto& p : open[i]) {
      ev.push_back({get<0>(p), get<1>(p), get<2>(p), T - 1});
    }
  }
  vector<vector<int>> qs(T);
  for (int i = 0; i < q; i++) {
    qs[y[i]].push_back(i);
  }
  vector<pair<int, int>> min_with;
  vector<pair<int, int>> max_with;
  for (auto& p : ev) {
    int L = p[0];
    int R = p[1];
    int mid = (L + R) / 2;
    min_with.emplace_back(L, mid);
    max_with.emplace_back(R, mid + (L % 2 != R % 2));
  }
  sort(min_with.begin(), min_with.end(), [&](pair<int, int> p, pair<int, int> q) {
    return p.second > q.second;
  });
  sort(max_with.begin(), max_with.end(), [&](pair<int, int> p, pair<int, int> q) {
    return p.second < q.second;
  });
  map<pair<int, int>, vector<int>> idx_mn;
  map<pair<int, int>, vector<int>> idx_mx;
  sz = (int) ev.size();
  for (int i = 0; i < sz; i++) {
    idx_mn[min_with[i]].push_back(i);
  }
  for (int i = 0; i < sz; i++) {
    idx_mx[max_with[i]].push_back(i);
  }
  vector<vector<int>> qs_mn(T);
  vector<vector<int>> qs_mx(T);
  for (int i = 0; i < sz; i++) {
    int L = ev[i][0];
    int R = ev[i][1];
    int from = ev[i][2];
    int to = ev[i][3];
    int mid = (L + R) / 2;
    {
      int idx = idx_mn[{L, mid}].back();
      idx_mn[{L, mid}].pop_back();
      qs_mn[from].push_back(idx);
      qs_mn[to].push_back(~idx);
    }
    {
      int idx = idx_mx[{R, mid + (L % 2 != R % 2)}].back();
      idx_mx[{R, mid + (L % 2 != R % 2)}].pop_back();
      qs_mx[from].push_back(idx);
      qs_mx[to].push_back(~idx);
    }
  }
  Build(1, 0, sz - 1);
  vector<int> res(q);
  for (int i = 0; i < T; i++) {
    for (int j : qs_mn[i]) {
      if (j >= 0) {
        ChangeMin(j, min_with[j].first);
      } else {
        j = ~j;
        ChangeMin(j, inf);
      }
    }
    for (int j : qs_mx[i]) {
      if (j >= 0) {
        ChangeMax(j, max_with[j].first);
      } else {
        j = ~j;
        ChangeMax(j, -inf);
      }
    }
    for (int j : qs[i]) {
      {
        int low = 0, high = sz - 1, pos = -1;
        while (low <= high) {
          int mid = low + high >> 1;
          if (min_with[mid].second >= l[j]) {
            pos = mid;
            low = mid + 1;
          } else {
            high = mid - 1;
          }
        }
        if (pos != -1) {
          res[j] = max(res[j], l[j] - get_min(0, pos));
        }
      }
      {
        int low = 0, high = sz - 1, pos = -1;
        while (low <= high) {
          int mid = low + high >> 1;
          if (max_with[mid].second <= l[j]) {
            pos = mid;
            low = mid + 1;
          } else {
            high = mid - 1;
          }
        }
        if (pos != -1) {
          res[j] = max(res[j], get_max(0, pos) - l[j]);
        }
      }
    }
  }
  vector<vector<int>> qs_type(T);
  for (int i = 0; i < n; i++) {
    qs_type[a[i]].push_back(t[i]);
    qs_type[b[i]].push_back(~t[i]);
  }
  int bal = 0;
  vector<int> cnt(k);
  for (int i = 0; i < T; i++) {
    for (int j : qs_type[i]) {
      if (j >= 0) {
        cnt[j] += 1;
        if (cnt[j] == 1) {
          bal += 1;
        }
      } else {
        j = ~j;
        cnt[j] -= 1;
        if (cnt[j] == 0) {
          bal -= 1;
        }
      }
    }
    for (int j : qs[i]) {
      if (bal != k) {
        res[j] = -1;
      }
    }
  }
  for (int i = 0; i < q; i++) {
    cout << res[i] << '\n';
  }
  return 0;
}

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


2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7


1 1 1
100000000 1 1 1
1 1
*/

Compilation message

new_home.cpp: In function 'void Build(int, int, int)':
new_home.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   17 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'void ModifyMin(int, int, int, int, int)':
new_home.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'void ModifyMax(int, int, int, int, int)':
new_home.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'int query_max(int, int, int, int, int)':
new_home.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   65 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'int query_min(int, int, int, int, int)':
new_home.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |   int mid = l + r >> 1;
      |             ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:311:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  311 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~
new_home.cpp:326:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  326 |           int mid = low + high >> 1;
      |                     ~~~~^~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 2 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 3 ms 3164 KB Output is correct
18 Correct 2 ms 2904 KB Output is correct
19 Correct 3 ms 2908 KB Output is correct
20 Correct 4 ms 3076 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 3 ms 3164 KB Output is correct
25 Correct 3 ms 3164 KB Output is correct
26 Correct 3 ms 3164 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2908 KB Output is correct
29 Correct 3 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 2 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 3 ms 3164 KB Output is correct
18 Correct 2 ms 2904 KB Output is correct
19 Correct 3 ms 2908 KB Output is correct
20 Correct 4 ms 3076 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 3 ms 3164 KB Output is correct
25 Correct 3 ms 3164 KB Output is correct
26 Correct 3 ms 3164 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2908 KB Output is correct
29 Correct 3 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 877 ms 98008 KB Output is correct
32 Correct 34 ms 5592 KB Output is correct
33 Correct 802 ms 97832 KB Output is correct
34 Correct 822 ms 97916 KB Output is correct
35 Correct 844 ms 98616 KB Output is correct
36 Correct 843 ms 98252 KB Output is correct
37 Correct 593 ms 98736 KB Output is correct
38 Correct 572 ms 98108 KB Output is correct
39 Correct 488 ms 97744 KB Output is correct
40 Correct 511 ms 97756 KB Output is correct
41 Correct 709 ms 100708 KB Output is correct
42 Correct 696 ms 101248 KB Output is correct
43 Correct 31 ms 6252 KB Output is correct
44 Correct 677 ms 102068 KB Output is correct
45 Correct 684 ms 101580 KB Output is correct
46 Correct 672 ms 101600 KB Output is correct
47 Correct 382 ms 95372 KB Output is correct
48 Correct 392 ms 95160 KB Output is correct
49 Correct 443 ms 97720 KB Output is correct
50 Correct 484 ms 99756 KB Output is correct
51 Correct 479 ms 97572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2722 ms 304768 KB Output is correct
2 Correct 2202 ms 299412 KB Output is correct
3 Correct 1734 ms 328840 KB Output is correct
4 Correct 2641 ms 307408 KB Output is correct
5 Correct 2301 ms 298908 KB Output is correct
6 Correct 2212 ms 299856 KB Output is correct
7 Correct 1709 ms 329164 KB Output is correct
8 Correct 2648 ms 308604 KB Output is correct
9 Correct 2776 ms 304564 KB Output is correct
10 Correct 2468 ms 298660 KB Output is correct
11 Correct 1888 ms 294072 KB Output is correct
12 Correct 2098 ms 298192 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5047 ms 418568 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 2 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 3 ms 3164 KB Output is correct
18 Correct 2 ms 2904 KB Output is correct
19 Correct 3 ms 2908 KB Output is correct
20 Correct 4 ms 3076 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 3 ms 3164 KB Output is correct
25 Correct 3 ms 3164 KB Output is correct
26 Correct 3 ms 3164 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2908 KB Output is correct
29 Correct 3 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 877 ms 98008 KB Output is correct
32 Correct 34 ms 5592 KB Output is correct
33 Correct 802 ms 97832 KB Output is correct
34 Correct 822 ms 97916 KB Output is correct
35 Correct 844 ms 98616 KB Output is correct
36 Correct 843 ms 98252 KB Output is correct
37 Correct 593 ms 98736 KB Output is correct
38 Correct 572 ms 98108 KB Output is correct
39 Correct 488 ms 97744 KB Output is correct
40 Correct 511 ms 97756 KB Output is correct
41 Correct 709 ms 100708 KB Output is correct
42 Correct 696 ms 101248 KB Output is correct
43 Correct 31 ms 6252 KB Output is correct
44 Correct 677 ms 102068 KB Output is correct
45 Correct 684 ms 101580 KB Output is correct
46 Correct 672 ms 101600 KB Output is correct
47 Correct 382 ms 95372 KB Output is correct
48 Correct 392 ms 95160 KB Output is correct
49 Correct 443 ms 97720 KB Output is correct
50 Correct 484 ms 99756 KB Output is correct
51 Correct 479 ms 97572 KB Output is correct
52 Correct 478 ms 90812 KB Output is correct
53 Correct 475 ms 90776 KB Output is correct
54 Correct 717 ms 94048 KB Output is correct
55 Correct 615 ms 98244 KB Output is correct
56 Correct 574 ms 96192 KB Output is correct
57 Correct 697 ms 99692 KB Output is correct
58 Correct 633 ms 98268 KB Output is correct
59 Correct 606 ms 96312 KB Output is correct
60 Correct 689 ms 100472 KB Output is correct
61 Correct 113 ms 33228 KB Output is correct
62 Correct 488 ms 91044 KB Output is correct
63 Correct 672 ms 96428 KB Output is correct
64 Correct 721 ms 96948 KB Output is correct
65 Correct 773 ms 99716 KB Output is correct
66 Correct 711 ms 101012 KB Output is correct
67 Correct 222 ms 30768 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 1 ms 2524 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 3 ms 2908 KB Output is correct
7 Correct 2 ms 2908 KB Output is correct
8 Correct 3 ms 2908 KB Output is correct
9 Correct 2 ms 2908 KB Output is correct
10 Correct 3 ms 3164 KB Output is correct
11 Correct 3 ms 2904 KB Output is correct
12 Correct 3 ms 3164 KB Output is correct
13 Correct 2 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 3 ms 3164 KB Output is correct
18 Correct 2 ms 2904 KB Output is correct
19 Correct 3 ms 2908 KB Output is correct
20 Correct 4 ms 3076 KB Output is correct
21 Correct 1 ms 2652 KB Output is correct
22 Correct 2 ms 2908 KB Output is correct
23 Correct 2 ms 2908 KB Output is correct
24 Correct 3 ms 3164 KB Output is correct
25 Correct 3 ms 3164 KB Output is correct
26 Correct 3 ms 3164 KB Output is correct
27 Correct 2 ms 2652 KB Output is correct
28 Correct 2 ms 2908 KB Output is correct
29 Correct 3 ms 2908 KB Output is correct
30 Correct 2 ms 2908 KB Output is correct
31 Correct 877 ms 98008 KB Output is correct
32 Correct 34 ms 5592 KB Output is correct
33 Correct 802 ms 97832 KB Output is correct
34 Correct 822 ms 97916 KB Output is correct
35 Correct 844 ms 98616 KB Output is correct
36 Correct 843 ms 98252 KB Output is correct
37 Correct 593 ms 98736 KB Output is correct
38 Correct 572 ms 98108 KB Output is correct
39 Correct 488 ms 97744 KB Output is correct
40 Correct 511 ms 97756 KB Output is correct
41 Correct 709 ms 100708 KB Output is correct
42 Correct 696 ms 101248 KB Output is correct
43 Correct 31 ms 6252 KB Output is correct
44 Correct 677 ms 102068 KB Output is correct
45 Correct 684 ms 101580 KB Output is correct
46 Correct 672 ms 101600 KB Output is correct
47 Correct 382 ms 95372 KB Output is correct
48 Correct 392 ms 95160 KB Output is correct
49 Correct 443 ms 97720 KB Output is correct
50 Correct 484 ms 99756 KB Output is correct
51 Correct 479 ms 97572 KB Output is correct
52 Correct 2722 ms 304768 KB Output is correct
53 Correct 2202 ms 299412 KB Output is correct
54 Correct 1734 ms 328840 KB Output is correct
55 Correct 2641 ms 307408 KB Output is correct
56 Correct 2301 ms 298908 KB Output is correct
57 Correct 2212 ms 299856 KB Output is correct
58 Correct 1709 ms 329164 KB Output is correct
59 Correct 2648 ms 308604 KB Output is correct
60 Correct 2776 ms 304564 KB Output is correct
61 Correct 2468 ms 298660 KB Output is correct
62 Correct 1888 ms 294072 KB Output is correct
63 Correct 2098 ms 298192 KB Output is correct
64 Execution timed out 5047 ms 418568 KB Time limit exceeded
65 Halted 0 ms 0 KB -