oj.uz

Submission #412304

# Submission time Handle Problem Language Result Execution time Memory
412304 2021-05-26T17:03:58 Z model_code Hexagonal Territory (APIO21_hexagon) C++17
100 / 100
 271 ms 49464 KB 
#include "hexagon.h"
#include <bits/stdc++.h>

using namespace std;

struct Point {
  int x, y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) {}
  Point operator+(Point p) const { return Point(x+p.x, y+p.y); }
  Point operator-(Point p) const { return Point(x-p.x, y-p.y); }
  Point operator*(int s) const { return Point(x * s, y * s); }
  bool operator==(Point p) const { return x == p.x && y == p.y; }
  bool operator<(Point p) const { return x == p.x ? y < p.y : x < p.x; }
};

ostream& operator<<(ostream& os, Point p) {
  return os << "(" << p.x << ", " << p.y << ")";
}

constexpr int mod = 1e9 + 7;
const vector<Point> pdirs = { Point(0, 1), Point(1, 1), Point(1, 0),
                              Point(0, -1), Point(-1, -1), Point(-1, 0) };

long long signed_twice_area(vector<Point> & vp) {
  long long ret = 0;
  int n = (int)vp.size() - 1;
  for (int i = 0; i < n; ++i) {
    ret += 1LL * vp[i].x * vp[i+1].y - 1LL * vp[i+1].x * vp[i].y;
  }
  return ret;
}

// assumption: vp circulating the territory in counter-clockwise direction
vector<tuple<Point, Point, int>> find_top_bottom(vector<Point> & vp) {
  vector<tuple<Point, Point, int>> result;
  int n = (int)vp.size()-1;
  for (int i = 0; i < n; ++i) {
    Point a = vp[i], b = vp[(i+1) % n];
    Point bef = vp[(i+n-1) % n], aft = vp[(i+2) % n];
    if (a.x == b.x)
      continue;
    if (a.x < b.x) { // bottom
      int dir;
      if (a.y < b.y) {
        dir = 1;
      } else {
        assert(a.y == b.y);
        dir = 2;
      }
      if (bef.x < a.x || bef.y < a.y)
        a = a + pdirs[dir];
      if (aft.x <= b.x && aft.y < b.y)
        b = b - pdirs[dir];
      if (b < a)
        continue;
      --a.y;
      --b.y;
      result.emplace_back(a, b, -1);
    } else { // top
      int dir;
      if (a.y > b.y) {
        dir = 4;
      } else {
        assert(a.y == b.y);
        dir = 5;
      }
      if (bef.x > a.x || bef.y > a.y)
        a = a + pdirs[dir];
      if (aft.x >= b.x && aft.y > b.y)
        b = b - pdirs[dir];
      if (a < b)
        continue;
      result.emplace_back(b, a, +1);
    }
  }
  return result;
}

struct Column {
  int x, bot, top;
  int minval, mbot, mtop;
  Column(int _x, int _bot, int _top,
         int _minval = -1, int _mbot = -1, int _mtop = -1)
    : x(_x), bot(_bot), top(_top), minval(_minval), mbot(_mbot), mtop(_mtop) {}
  void update(int _minval, int _mbot, int _mtop) {
    minval = _minval;
    mbot = _mbot;
    mtop = _mtop;
    if (mbot > top) {
      minval += mbot - top;
      minval %= mod;
      mbot = mtop = top;
    }
    if (mtop < bot) {
      minval += bot - mtop;
      minval %= mod;
      mbot = mtop = bot;
    }
    mtop = min(mtop, top);
    mbot = max(mbot, bot);
  }
};

constexpr long long inv2 = (mod + 1LL) / 2;
// calc: sum(a + (i-1) * b)) for i = 1..n
long long calc_1(long long a, long long b, long long n) {
  long long ret = (2LL * a + (n-1LL) * b) % mod;
  ret = ret * n % mod;
  ret = ret * inv2 % mod;
  return ret;
}

constexpr long long inv3 = ((mod % 3) == 2 ? (mod + 1LL) : (2LL * mod + 1)) / 3;
// calc: sum(i * (a + (i-1) * b)) for i = 1..n
long long calc_2(long long a, long long b, long long n) {
  long long ret = n * (n + 1LL) % mod;
  ret = ret * inv2 % mod;
  long long mul = (2LL * n + 1LL) * inv3 % mod;
  mul = (a - b + mul * b) % mod;
  ret = ret * mul % mod;
  return ret;
}

long long calc_rectangle(int width, int minval, int same, int down, int up) {
  long long ret = 0;
  long long a = 1LL * minval * same %  mod;
  if (down) {
    a = (a + calc_1(minval+1, 1, down)) % mod;
  }
  ret += calc_1(a, same + down, width);
  if (up) {
    int len = min(up, width);
    ret += calc_2(minval+1, 1, len) + calc_2(minval+1, 1, len-1);
    if (len < width) {
      ret += calc_1(1LL * (minval + len) * up % mod, up, width - len);
    }
    if (len < up) {
      ret += calc_1(1LL * (minval + len + 1) * width % mod, width, up - len);
    }
  }
  return ret % mod;
}

long long calc(int width, int minval, int same, int down, int up,
               bool del_topleft, bool del_botright) {
  long long ret = calc_rectangle(width, minval, same, down, up);
  if (width > 1) {
    int d = width - 1;
    if (del_topleft) {
      assert(up >= d);
      ret -= calc_2(minval + (up - d + 1), 1, d);
    }
    if (del_botright) {
      int len = min(down, d);
      ret -= calc_2(minval + len + down, mod-1, len);
      if (len < d) {
        ret -= calc_2(minval + len+1, 1, d - len);
        long long a = calc_1(minval + len+2, 1, down);
        ret -= calc_1(a, down, d - len);
      }
    }
  }
  ret %= mod;
  if (ret < 0)
    ret += mod;
  return ret;
}

struct Block {
  Column left, right;
  Block(Column _left, Column _right) : left(_left), right(_right) {}

  long long move_right(long long a, long long b) {
    int dx = right.x - left.x;
    long long ret = (left.top - left.bot + right.top - right.bot + 2LL);
    ret = ((ret * (dx + 1) % mod) * inv2 % mod) * a % mod;

    right.update(left.minval + dx, left.mbot, left.mtop + dx);
    int width = right.x - left.x + 1;
    int same = left.mtop - left.mbot + 1;
    int up = right.top - left.mtop;
    int down = left.mbot - left.bot;
    bool del_toplef = left.top < right.top, del_botrig = left.bot < right.bot;
    ret += b * calc(width, left.minval, same, down, up, del_toplef, del_botrig);
    return ret % mod;
  }

  long long move_left(long long a, long long b) {
    int dx = right.x - left.x;
    long long ret = (left.top - left.bot + right.top - right.bot + 2LL);
    ret = ((ret * (dx + 1) % mod) * inv2 % mod) * a % mod;

    left.update(right.minval + dx, right.mbot - dx, right.mtop);
    int width = right.x - left.x + 1;
    int same = right.mtop - right.mbot + 1;
    int down = right.top - right.mtop;
    int up = right.mbot - left.bot;
    bool del_botrig = left.top < right.top, del_toplef = left.bot < right.bot;
    ret += b * calc(width, right.minval, same, down, up, del_toplef,
                    del_botrig);
    return ret % mod;
  }
};

struct Line {
  Point pstart, pdir;
  int id;
  Point get(int x) const {
    return pstart + (pdir * (x - pstart.x));
  }
  bool operator<(const Line & rig) const {
    int x_common = max(pstart.x, rig.pstart.x);
    return get(x_common).y < rig.get(x_common).y;
  }
};

vector<Block> find_blocks(vector<Point> & vp) {
  auto y_events = find_top_bottom(vp);
  vector<int> last(y_events.size()), sign(y_events.size());
  vector<Line> lines(y_events.size());
  vector<pair<int, int>> x_events;
  for (int i = 0; i < (int)y_events.size(); ++i) {
    Point pleft, pright;
    tie(pleft, pright, sign[i]) = y_events[i];
    last[i] = pleft.x;
    lines[i] = {pleft, (pright.y > pleft.y ? Point(1, 1) : Point(1, 0)), i};
    x_events.emplace_back(pleft.x, i);
    x_events.emplace_back(pright.x+1, ~i);
  }
  sort(x_events.begin(), x_events.end());
  set<Line> st;
  vector<Block> result;
  auto check_block = [&](set<Line>::iterator nxt, int x) {
    if (nxt != st.begin() && nxt != st.end() && sign[nxt->id] > 0) {
      auto prv = prev(nxt);
      if (sign[prv->id] < 0 && min(last[prv->id], last[nxt->id]) < x) {
        assert(last[prv->id] == last[nxt->id]);
        int xleft = last[prv->id], xright = x - 1;
        result.emplace_back(
            Column(xleft, prv->get(xleft).y+1, nxt->get(xleft).y),
            Column(xright, prv->get(xright).y+1, nxt->get(xright).y));
        last[prv->id] = last[nxt->id] = x;
      }
    }
  };
  for (auto & e : x_events) {
    int id = e.second;
    if (id < 0) {
      id = ~id;
      auto it = st.upper_bound(lines[id]);
      if (it != st.end())
        check_block(it, e.first);
      assert(it != st.begin());
      --it;
      assert(it->id == id);
      check_block(it, e.first);
      st.erase(it);
    } else {
      auto nxt = st.lower_bound(lines[id]);
      check_block(nxt, e.first);
      st.insert(lines[id]);
    }
  }
  return result;
}

vector<Block> blocks;
vector<vector<pair<int, int>>> tree;

void construct_tree() {
  tree.resize(blocks.size());
  vector<tuple<int, int, int>> events;
  for (int i = 0; i < (int)blocks.size(); ++i) {
    events.emplace_back(blocks[i].left.x, blocks[i].left.bot, i);
    events.emplace_back(blocks[i].right.x+1, blocks[i].right.bot, ~i);
  }
  int idl = -1, idr = -1;
  sort(events.begin(), events.end());
  int cnt = 0;
  for (auto & e : events) {
    int id = get<2>(e);
    if (id < 0)
      idl = ~id;
    else
      idr = id;
    if (idl >= 0 && idr >= 0 && blocks[idl].right.x+1 == blocks[idr].left.x) {
      if (blocks[idl].right.bot <= blocks[idr].left.top &&
          blocks[idr].left.bot <= blocks[idl].right.top) {
        tree[idl].emplace_back(idr, 1);
        tree[idr].emplace_back(idl, -1);
        ++cnt;
      }
    }
  }
  assert(cnt + 1 == (int)blocks.size());
}

int dfs(int v, int par, long long a, long long b) {
  int ret = 0;
  for (auto & e : tree[v]) {
    int u = e.first;
    if (u == par) continue;
    if (e.second > 0) {
      blocks[u].left.update(blocks[v].right.minval+1, blocks[v].right.mbot,
                            blocks[v].right.mtop+1);
      ret = (ret + blocks[u].move_right(a, b)) % mod;
    } else {
      blocks[u].right.update(blocks[v].left.minval+1, blocks[v].left.mbot-1,
                             blocks[v].left.mtop);
      ret = (ret + blocks[u].move_left(a, b)) % mod;
    }
    ret = (ret + dfs(u, v, a, b)) % mod;
  }
  return ret;
}

int draw_territory(int N, int A, int B, vector<int> D, vector<int> L) {
  vector<Point> vp(N+1);
  for (int i = 0; i < N; ++i) {
    vp[i+1] = vp[i] + pdirs[D[i]-1] * L[i];
  }
  if (signed_twice_area(vp) < 0) {
    reverse(vp.begin(), vp.end());
  }
  blocks = find_blocks(vp);
  construct_tree();
  long long ans = 0;
  int root = -1;
  for (int i = 0; i < (int)blocks.size(); ++i) {
    if (blocks[i].left.x > 0) continue;
    if (blocks[i].right.x < 0) continue;
    int top = blocks[i].left.top, bot = blocks[i].left.bot;
    if (blocks[i].left.top < blocks[i].right.top)
      top += -blocks[i].left.x;
    if (blocks[i].left.bot < blocks[i].right.bot)
      bot += -blocks[i].left.x;
    if (bot <= 0 && 0 <= top) {
      assert(root == -1);
      root = i;
      Block left = blocks[root], right = blocks[root];
      left.right = right.left = Column(0, bot, top, 0, 0, 0);
      ans = (ans + left.move_left(A, B)) % mod;
      ans = (ans + right.move_right(A, B)) % mod;
      ans = (ans - calc_1(A, B, top+1) - calc_1(A+B, B, -bot)) % mod;
      blocks[root].left = left.left;
      blocks[root].right = right.right;
    }
  }
  assert(root != -1);
  ans = (ans + dfs(root, -1, A, B)) % mod;
  if (ans < 0)
    ans += mod;
  return ans;
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 208 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2 ms 332 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 208 KB Output is correct
20 Correct 1 ms 208 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 7 ms 1264 KB Output is correct
3 Correct 2 ms 592 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 5 ms 960 KB Output is correct
6 Correct 8 ms 1500 KB Output is correct
7 Correct 24 ms 3620 KB Output is correct
8 Correct 2 ms 588 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 39 ms 9748 KB Output is correct
12 Correct 28 ms 7180 KB Output is correct
13 Correct 25 ms 6216 KB Output is correct
14 Correct 44 ms 8000 KB Output is correct
15 Correct 2 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 212 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 9 ms 1264 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 4 ms 960 KB Output is correct
8 Correct 8 ms 1416 KB Output is correct
9 Correct 24 ms 3652 KB Output is correct
10 Correct 2 ms 592 KB Output is correct
11 Correct 2 ms 464 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 39 ms 9684 KB Output is correct
14 Correct 28 ms 7184 KB Output is correct
15 Correct 23 ms 6196 KB Output is correct
16 Correct 44 ms 8076 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 1 ms 216 KB Output is correct
20 Correct 67 ms 9444 KB Output is correct
21 Correct 7 ms 1264 KB Output is correct
22 Correct 4 ms 848 KB Output is correct
23 Correct 86 ms 12704 KB Output is correct
24 Correct 150 ms 21756 KB Output is correct
25 Correct 159 ms 23756 KB Output is correct
26 Correct 98 ms 15760 KB Output is correct
27 Correct 76 ms 12596 KB Output is correct
28 Correct 59 ms 6772 KB Output is correct
29 Correct 192 ms 49344 KB Output is correct
30 Correct 125 ms 24756 KB Output is correct
31 Correct 145 ms 27368 KB Output is correct
32 Correct 250 ms 41184 KB Output is correct
33 Correct 73 ms 13584 KB Output is correct
34 Correct 24 ms 4912 KB Output is correct
35 Correct 1 ms 204 KB Output is correct
36 Correct 1 ms 204 KB Output is correct
37 Correct 1 ms 208 KB Output is correct

Subtask #6
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 208 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 2 ms 332 KB Output is correct
14 Correct 2 ms 332 KB Output is correct
15 Correct 2 ms 364 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 7 ms 1264 KB Output is correct
20 Correct 2 ms 588 KB Output is correct
21 Correct 2 ms 332 KB Output is correct
22 Correct 5 ms 956 KB Output is correct
23 Correct 9 ms 1436 KB Output is correct
24 Correct 25 ms 3652 KB Output is correct
25 Correct 3 ms 588 KB Output is correct
26 Correct 2 ms 460 KB Output is correct
27 Correct 2 ms 332 KB Output is correct
28 Correct 45 ms 9792 KB Output is correct
29 Correct 32 ms 7168 KB Output is correct
30 Correct 25 ms 6188 KB Output is correct
31 Correct 50 ms 8024 KB Output is correct
32 Correct 2 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 9 ms 1384 KB Output is correct
36 Correct 2 ms 460 KB Output is correct
37 Correct 2 ms 332 KB Output is correct
38 Correct 10 ms 1392 KB Output is correct
39 Correct 10 ms 1508 KB Output is correct
40 Correct 31 ms 4420 KB Output is correct
41 Correct 2 ms 460 KB Output is correct
42 Correct 2 ms 460 KB Output is correct
43 Correct 2 ms 444 KB Output is correct
44 Correct 54 ms 12436 KB Output is correct
45 Correct 33 ms 7184 KB Output is correct
46 Correct 36 ms 6792 KB Output is correct
47 Correct 36 ms 5228 KB Output is correct
48 Correct 2 ms 460 KB Output is correct
49 Correct 1 ms 332 KB Output is correct
50 Correct 1 ms 204 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 204 KB Output is correct
54 Correct 1 ms 204 KB Output is correct
55 Correct 1 ms 208 KB Output is correct
56 Correct 1 ms 204 KB Output is correct
57 Correct 1 ms 204 KB Output is correct

Subtask #7
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 110 ms 15920 KB Output is correct
7 Correct 98 ms 16012 KB Output is correct
8 Correct 109 ms 16980 KB Output is correct
9 Correct 4 ms 992 KB Output is correct
10 Correct 13 ms 2412 KB Output is correct
11 Correct 13 ms 2120 KB Output is correct
12 Correct 217 ms 35416 KB Output is correct
13 Correct 218 ms 37676 KB Output is correct
14 Correct 187 ms 31112 KB Output is correct
15 Correct 106 ms 24500 KB Output is correct
16 Correct 131 ms 25552 KB Output is correct
17 Correct 122 ms 22452 KB Output is correct
18 Correct 236 ms 42776 KB Output is correct
19 Correct 39 ms 4760 KB Output is correct
20 Correct 118 ms 34576 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 1 ms 204 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct

Subtask #8
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 2 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 2 ms 332 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Correct 1 ms 208 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 8 ms 1260 KB Output is correct
24 Correct 2 ms 612 KB Output is correct
25 Correct 2 ms 332 KB Output is correct
26 Correct 5 ms 960 KB Output is correct
27 Correct 10 ms 1448 KB Output is correct
28 Correct 24 ms 3652 KB Output is correct
29 Correct 2 ms 588 KB Output is correct
30 Correct 2 ms 460 KB Output is correct
31 Correct 2 ms 332 KB Output is correct
32 Correct 52 ms 9676 KB Output is correct
33 Correct 27 ms 7172 KB Output is correct
34 Correct 23 ms 6116 KB Output is correct
35 Correct 44 ms 8060 KB Output is correct
36 Correct 2 ms 332 KB Output is correct
37 Correct 2 ms 388 KB Output is correct
38 Correct 1 ms 204 KB Output is correct
39 Correct 69 ms 9432 KB Output is correct
40 Correct 8 ms 1264 KB Output is correct
41 Correct 4 ms 844 KB Output is correct
42 Correct 92 ms 12736 KB Output is correct
43 Correct 142 ms 21748 KB Output is correct
44 Correct 162 ms 23736 KB Output is correct
45 Correct 92 ms 15776 KB Output is correct
46 Correct 69 ms 12532 KB Output is correct
47 Correct 52 ms 6768 KB Output is correct
48 Correct 194 ms 49464 KB Output is correct
49 Correct 107 ms 24760 KB Output is correct
50 Correct 105 ms 27304 KB Output is correct
51 Correct 249 ms 41096 KB Output is correct
52 Correct 82 ms 13572 KB Output is correct
53 Correct 33 ms 4992 KB Output is correct
54 Correct 1 ms 204 KB Output is correct
55 Correct 10 ms 1392 KB Output is correct
56 Correct 2 ms 460 KB Output is correct
57 Correct 2 ms 332 KB Output is correct
58 Correct 7 ms 1392 KB Output is correct
59 Correct 8 ms 1508 KB Output is correct
60 Correct 39 ms 4376 KB Output is correct
61 Correct 3 ms 460 KB Output is correct
62 Correct 3 ms 460 KB Output is correct
63 Correct 2 ms 316 KB Output is correct
64 Correct 66 ms 12500 KB Output is correct
65 Correct 31 ms 7220 KB Output is correct
66 Correct 31 ms 6792 KB Output is correct
67 Correct 26 ms 5204 KB Output is correct
68 Correct 2 ms 460 KB Output is correct
69 Correct 2 ms 324 KB Output is correct
70 Correct 1 ms 204 KB Output is correct
71 Correct 103 ms 16044 KB Output is correct
72 Correct 102 ms 16032 KB Output is correct
73 Correct 104 ms 16980 KB Output is correct
74 Correct 5 ms 992 KB Output is correct
75 Correct 14 ms 2464 KB Output is correct
76 Correct 12 ms 2172 KB Output is correct
77 Correct 220 ms 35356 KB Output is correct
78 Correct 215 ms 37700 KB Output is correct
79 Correct 179 ms 31180 KB Output is correct
80 Correct 106 ms 24500 KB Output is correct
81 Correct 117 ms 25656 KB Output is correct
82 Correct 132 ms 22360 KB Output is correct
83 Correct 271 ms 42812 KB Output is correct
84 Correct 38 ms 4676 KB Output is correct
85 Correct 117 ms 34512 KB Output is correct
86 Correct 1 ms 204 KB Output is correct
87 Correct 60 ms 8848 KB Output is correct
88 Correct 9 ms 1580 KB Output is correct
89 Correct 4 ms 716 KB Output is correct
90 Correct 87 ms 12800 KB Output is correct
91 Correct 140 ms 23132 KB Output is correct
92 Correct 163 ms 25520 KB Output is correct
93 Correct 94 ms 17972 KB Output is correct
94 Correct 73 ms 11316 KB Output is correct
95 Correct 59 ms 7612 KB Output is correct
96 Correct 199 ms 44720 KB Output is correct
97 Correct 118 ms 29368 KB Output is correct
98 Correct 114 ms 27856 KB Output is correct
99 Correct 170 ms 24724 KB Output is correct
100 Correct 102 ms 13212 KB Output is correct
101 Correct 26 ms 4900 KB Output is correct
102 Correct 1 ms 204 KB Output is correct
103 Correct 1 ms 204 KB Output is correct
104 Correct 1 ms 204 KB Output is correct
105 Correct 1 ms 204 KB Output is correct
106 Correct 2 ms 204 KB Output is correct
107 Correct 1 ms 204 KB Output is correct
108 Correct 1 ms 204 KB Output is correct
109 Correct 1 ms 204 KB Output is correct