oj.uz

Submission #827957

# Submission time Handle Problem Language Result Execution time Memory
827957 2023-08-16T23:57:03 Z null_awe Maze (JOI23_ho_t3) C++14
59 / 100
 2000 ms 372996 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int, int>

static char buf[450 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf;
	assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}

const int UNTIL = 3000001;

vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};

int csqrt[UNTIL], fsqrt[UNTIL];

void init() {
  csqrt[1] = fsqrt[1] = 1;
  for (int i = 2; i < UNTIL; ++i) {
    fsqrt[i] = fsqrt[i - 1];
    while ((fsqrt[i] + 1) * (fsqrt[i] + 1) <= i) ++fsqrt[i];
    csqrt[i] = fsqrt[i];
    if (fsqrt[i] * fsqrt[i] < i) ++csqrt[i];
  }
}

struct VEB {

  int u, mn, mx, sz;
  VEB *summary;
  vector<VEB*> galaxy;

  inline int high(int k) { return k / sz; }
  inline int low(int k) { return k % sz; }
  inline int index(int k, int kk) { return k * sz + kk; }

  VEB(int u) : u(u) {
    mn = INT_MAX, mx = INT_MIN;
    if (u <= 2) summary = nullptr, galaxy.resize(0, nullptr);
    else {
      int ngalaxy = csqrt[u];
      sz = (u + ngalaxy - 1) / ngalaxy;
      summary = new VEB(ngalaxy);
      galaxy.resize(ngalaxy, nullptr);
      for (int i = 0; i < ngalaxy - 1; ++i) galaxy[i] = new VEB(sz);
      galaxy[ngalaxy - 1] = new VEB(u - (ngalaxy - 1) * sz);
    }
  }

  void insert(int x) {
    if (mn == INT_MAX) mn = mx = x;
    else {
      if (x < mn) swap(x, mn);
      if (x > mx) mx = x;
      if (u <= 2) return;
      int i = high(x), j = low(x);
      if (galaxy[i]->mn == INT_MAX) summary->insert(i);
      galaxy[i]->insert(j);
    }
  }

  void erase(int x) {
    if (mn == INT_MAX) return;
    if (mn == mx) {
      mn = INT_MAX, mx = INT_MIN;
      return;
    }
    if (u <= 2) {
      if (x != mx) mn = mx;
      else if (x == mn) mn = INT_MAX, mx = INT_MIN;
      else if (x == 0) mn = 1;
      else mx = 0;
      return;
    }
    if (x == mn) {
      int i = summary->mn;
      if (i == INT_MAX) {
        mn = INT_MAX, mx = INT_MIN;
        return;
      }
      x = mn = index(i, galaxy[i]->mn);
    }
    int i = high(x), j = low(x);
    galaxy[i]->erase(j);
    if (galaxy[i]->mn == INT_MAX) summary->erase(i);
    if (x == mx) {
      if (summary->mx == INT_MIN) mx = mn;
      else {
        i = summary->mx;
        mx = index(i, galaxy[i]->mx);
      }
    }
  }

  int lower_bound(int x) {
    if (x <= mn) return mn;
    if (u <= 2) {
      if (x <= mx) return mx;
      return INT_MAX;
    }
    int i = high(x), j = low(x);
    if (j <= galaxy[i]->mx) j = galaxy[i]->lower_bound(j);
    else {
      i = summary->lower_bound(i + 1);
      j = galaxy[i]->mn;
    }
    return index(i, j);
  }
};

VEB* build_veb(int u) {
  VEB* root = new VEB(u);
  for (int i = 0; i < u; ++i) root->insert(i);
  return root;
}

struct Sustree {

  int n, m;
  vector<VEB*> has;

  Sustree() {}

  Sustree(int n, int m) : n(n), m(m), has(4 * n, nullptr) {}

  void build(int t, int tl, int tr) {
    has[t] = build_veb(m + 1);
    if (tl == tr) return;
    build(2 * t, tl, (tl + tr) / 2);
    build(2 * t + 1, (tl + tr) / 2 + 1, tr);
  }

  void build() {
    build(1, 0, n - 1);
  }


  void upd(int t, int tl, int tr, int p, int py) {
    if (tl == tr) {
      has[t]->erase(py);
      return;
    }
    if (p <= (tl + tr) / 2) upd(2 * t, tl, (tl + tr) / 2, p, py);
    else upd(2 * t + 1, (tl + tr) / 2 + 1, tr, p, py);
    int a = has[2 * t]->lower_bound(py);
    int b = has[2 * t + 1]->lower_bound(py);
    if (a != py && b != py) {
      has[t]->erase(py);
    }
  }

  void upd(int x, int y) {
    upd(1, 0, n - 1, x, y);
  }

  pii qry(int t, int tl, int tr, int l, int r, int lo, int hi) {
    l = max(l, tl), r = min(r, tr);
    if (l > r) return {-1, -1};
    if (tl == l && tr == r) {
      int gr = has[t]->lower_bound(lo);
      if (gr > hi) return {-1, -1};
      if (tl == tr) {
        return {tl, gr};
      }
      int mm = (tl + tr) / 2;
      if (has[2 * t]->lower_bound(lo) <= hi) return qry(2 * t, tl, mm, l, r, lo, hi);
      return qry(2 * t + 1, mm + 1, tr, l, r, lo, hi);
    }
    int mm = (tl + tr) / 2;
    pii f = qry(2 * t, tl, mm, l, r, lo, hi);
    if (f.first >= 0) return f;
    return qry(2 * t + 1, mm + 1, tr, l, r, lo, hi);
  }

  pii qry(int x1, int y1, int x2, int y2) {
    return qry(1, 0, n - 1, max(x1, 0), min(x2, n - 1), max(y1, 0), min(y2, m - 1));
  }
};

int main() {
  init();
  ios_base::sync_with_stdio(false); cin.tie(NULL);
  int r, c, n; cin >> r >> c >> n;
  int sx, sy; cin >> sx >> sy; --sx, --sy;
  int gx, gy; cin >> gx >> gy; --gx, --gy;
  vector<string> arr(r);
  for (int i = 0; i < r; ++i) cin >> arr[i];
  if (r > c) {
    vector<string> arr2(c);
    for (int i = 0; i < r; ++i) {
      for (int j = 0; j < c; ++j) {
        arr2[j] += arr[i][j];
      }
    }
    swap(arr, arr2);
    swap(r, c);
    swap(sx, sy);
    swap(gx, gy);
  }
  // . = empty
  // # = wall
  Sustree sus(r, c); sus.build();
  vector<vector<int>> dists(r, vector<int>(c, INT_MAX));
  dists[sx][sy] = 0;
  sus.upd(sx, sy);
  vector<pii> q; q.push_back({sx, sy});
  queue<pii> rq; for (pii _p : q) rq.push(_p);
  while (rq.size()) {
    pii front = rq.front(); rq.pop();
    int xx = front.first, yy = front.second;
    for (int d = 0; d < 4; ++d) {
      int nx = xx + dx[d], ny = yy + dy[d];
      if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
      if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
      rq.push({nx, ny});
      q.push_back({nx, ny});
      dists[nx][ny] = dists[xx][yy];
      sus.upd(nx, ny);
    }
  }
  while (q.size()) {
    vector<pii> nq;
    for (pii p : q) {
      int x = p.first, y = p.second;
      if (x > 0 && dists[x - 1][y] <= dists[x][y]) {
        // query down:
        int cur;
        while ((cur = sus.qry(x + n, y - n + 1, x + n, y + n - 1).second) != -1) {
          nq.push_back({x + n, cur});
          dists[x + n][cur] = dists[x][y] + 1;
          sus.upd(x + n, cur);
        }
        if (x + n - 1 < r && y - n >= 0 && dists[x + n - 1][y - n] == INT_MAX) {
          nq.push_back({x + n - 1, y - n});
          dists[x + n - 1][y - n] = dists[x][y] + 1;
          sus.upd(x + n - 1, y - n);
        }
        if (x + n - 1 < r && y + n < c && dists[x + n - 1][y + n] == INT_MAX) {
          nq.push_back({x + n - 1, y + n});
          dists[x + n - 1][y + n] = dists[x][y] + 1;
          sus.upd(x + n - 1, y + n);
        }
      } else if (y < r - 1 && dists[x][y + 1] <= dists[x][y]) {
        // query left:
        int cur;
        while ((cur = sus.qry(x - n + 1, y - n, x + n - 1, y - n).first) != -1) {
          nq.push_back({cur, y - n});
          dists[cur][y - n] = dists[x][y] + 1;
          sus.upd(cur, y - n);
        }
        if (y - n + 1 >= 0 && x - n >= 0 && dists[x - n][y - n + 1] == INT_MAX) {
          nq.push_back({x - n, y - n + 1});
          dists[x - n][y - n + 1] = dists[x][y] + 1;
          sus.upd(x - n, y - n + 1);
        }
        if (y - n + 1 >= 0 && x + n < r && dists[x + n][y - n + 1] == INT_MAX) {
          nq.push_back({x + n, y - n + 1});
          dists[x + n][y - n + 1] = dists[x][y] + 1;
          sus.upd(x + n, y - n + 1);
        }
      } else {
        // query all:
        for (int i = -n; i <= n; i += 2 * n) {
          int cx = x + i, cyl = y - n + 1, cyr = y + n - 1, cur;
          while ((cur = sus.qry(cx, cyl, cx, cyr).second) != -1) {
            nq.push_back({cx, cur});
            dists[cx][cur] = dists[x][y] + 1;
            sus.upd(cx, cur);
          }
        }
        pii cur;
        while ((cur = sus.qry(x - n + 1, y - n, x + n - 1, y + n)).first != -1) {
          int nx = cur.first, ny = cur.second;
          nq.push_back({nx, ny});
          dists[nx][ny] = dists[x][y] + 1;
          sus.upd(nx, ny);
        }
      }
    }
    queue<pii> rq; for (pii _p : nq) rq.push(_p);
    while (rq.size()) {
      pii front = rq.front(); rq.pop();
      int xx = front.first, yy = front.second;
      for (int d = 0; d < 4; ++d) {
        int nx = xx + dx[d], ny = yy + dy[d];
        if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
        if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
        rq.push({nx, ny});
        nq.push_back({nx, ny});
        dists[nx][ny] = dists[xx][yy];
        sus.upd(nx, ny);
      }
    }
    q = nq;
  }
  cout << dists[gx][gy] << '\n';
  return 0;
}

Compilation message

Main.cpp:21:5: warning: built-in function 'csqrt' declared as non-function [-Wbuiltin-declaration-mismatch]
   21 | int csqrt[UNTIL], fsqrt[UNTIL];
      |     ^~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23716 KB Output is correct
2 Correct 15 ms 23744 KB Output is correct
3 Correct 20 ms 24020 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 18 ms 23904 KB Output is correct
6 Correct 16 ms 24020 KB Output is correct
7 Correct 16 ms 23824 KB Output is correct
8 Correct 17 ms 24200 KB Output is correct
9 Correct 17 ms 23752 KB Output is correct
10 Correct 15 ms 23764 KB Output is correct
11 Correct 16 ms 23764 KB Output is correct
12 Correct 16 ms 23732 KB Output is correct
13 Correct 16 ms 23764 KB Output is correct
14 Correct 16 ms 23768 KB Output is correct
15 Correct 16 ms 23828 KB Output is correct
16 Correct 16 ms 23992 KB Output is correct
17 Correct 16 ms 24012 KB Output is correct
18 Correct 17 ms 23940 KB Output is correct
19 Correct 64 ms 34800 KB Output is correct
20 Correct 33 ms 50016 KB Output is correct
21 Correct 57 ms 34368 KB Output is correct
22 Correct 63 ms 34892 KB Output is correct
23 Correct 58 ms 34972 KB Output is correct
24 Correct 29 ms 30736 KB Output is correct
25 Correct 39 ms 61580 KB Output is correct
26 Correct 64 ms 34836 KB Output is correct
27 Correct 63 ms 34640 KB Output is correct
28 Correct 51 ms 34652 KB Output is correct
29 Correct 156 ms 53720 KB Output is correct
30 Correct 38 ms 37088 KB Output is correct
31 Correct 144 ms 53140 KB Output is correct
32 Correct 166 ms 53552 KB Output is correct
33 Correct 148 ms 53908 KB Output is correct
34 Correct 44 ms 42384 KB Output is correct
35 Correct 71 ms 118516 KB Output is correct
36 Correct 172 ms 53076 KB Output is correct
37 Correct 168 ms 53196 KB Output is correct
38 Correct 139 ms 53320 KB Output is correct
39 Correct 1987 ms 340296 KB Output is correct
40 Correct 130 ms 64760 KB Output is correct
41 Correct 61 ms 60820 KB Output is correct
42 Correct 240 ms 68528 KB Output is correct
43 Correct 119 ms 91008 KB Output is correct
44 Correct 412 ms 169852 KB Output is correct
45 Correct 406 ms 213144 KB Output is correct
46 Correct 1764 ms 336388 KB Output is correct
47 Execution timed out 2100 ms 336600 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 16 ms 23780 KB Output is correct
4 Correct 16 ms 23776 KB Output is correct
5 Correct 17 ms 23908 KB Output is correct
6 Correct 15 ms 23764 KB Output is correct
7 Correct 16 ms 23764 KB Output is correct
8 Correct 16 ms 23760 KB Output is correct
9 Correct 16 ms 23892 KB Output is correct
10 Correct 16 ms 24020 KB Output is correct
11 Correct 25 ms 24020 KB Output is correct
12 Correct 16 ms 23992 KB Output is correct
13 Correct 16 ms 23924 KB Output is correct
14 Correct 17 ms 23992 KB Output is correct
15 Correct 16 ms 23892 KB Output is correct
16 Correct 16 ms 24244 KB Output is correct
17 Correct 17 ms 23956 KB Output is correct
18 Correct 16 ms 23716 KB Output is correct
19 Correct 17 ms 23876 KB Output is correct
20 Correct 16 ms 23820 KB Output is correct
21 Correct 16 ms 23752 KB Output is correct
22 Correct 16 ms 23848 KB Output is correct
23 Correct 16 ms 23752 KB Output is correct
24 Correct 16 ms 23712 KB Output is correct
25 Correct 16 ms 23764 KB Output is correct
26 Correct 16 ms 23732 KB Output is correct
27 Correct 16 ms 23732 KB Output is correct
28 Correct 16 ms 23948 KB Output is correct
29 Correct 16 ms 23752 KB Output is correct
30 Correct 18 ms 24004 KB Output is correct
31 Correct 16 ms 23948 KB Output is correct
32 Correct 16 ms 24020 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23768 KB Output is correct
2 Correct 16 ms 23728 KB Output is correct
3 Correct 16 ms 23732 KB Output is correct
4 Correct 16 ms 23764 KB Output is correct
5 Correct 16 ms 23740 KB Output is correct
6 Correct 16 ms 23720 KB Output is correct
7 Correct 16 ms 23892 KB Output is correct
8 Correct 18 ms 23932 KB Output is correct
9 Correct 16 ms 23892 KB Output is correct
10 Correct 16 ms 23892 KB Output is correct
11 Correct 16 ms 23992 KB Output is correct
12 Correct 17 ms 23932 KB Output is correct
13 Correct 16 ms 23712 KB Output is correct
14 Correct 16 ms 23892 KB Output is correct
15 Correct 16 ms 23744 KB Output is correct
16 Correct 17 ms 23892 KB Output is correct
17 Correct 16 ms 23812 KB Output is correct
18 Correct 16 ms 23764 KB Output is correct
19 Correct 16 ms 23792 KB Output is correct
20 Correct 16 ms 23764 KB Output is correct
21 Correct 16 ms 24020 KB Output is correct
22 Correct 16 ms 24020 KB Output is correct
23 Correct 18 ms 23968 KB Output is correct
24 Correct 17 ms 24208 KB Output is correct
25 Correct 45 ms 33200 KB Output is correct
26 Correct 51 ms 34844 KB Output is correct
27 Correct 55 ms 34376 KB Output is correct
28 Correct 55 ms 34376 KB Output is correct
29 Correct 39 ms 34808 KB Output is correct
30 Correct 39 ms 34848 KB Output is correct
31 Correct 40 ms 36640 KB Output is correct
32 Correct 79 ms 34780 KB Output is correct
33 Correct 72 ms 34660 KB Output is correct
34 Correct 134 ms 52140 KB Output is correct
35 Correct 138 ms 53056 KB Output is correct
36 Correct 126 ms 53160 KB Output is correct
37 Correct 83 ms 54276 KB Output is correct
38 Correct 82 ms 54284 KB Output is correct
39 Correct 507 ms 126256 KB Output is correct
40 Correct 1301 ms 305400 KB Output is correct
41 Correct 1796 ms 336456 KB Output is correct
42 Correct 1427 ms 336388 KB Output is correct
43 Correct 842 ms 348404 KB Output is correct
44 Correct 841 ms 348484 KB Output is correct
45 Correct 1112 ms 372996 KB Output is correct
46 Correct 1133 ms 358308 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 16 ms 23780 KB Output is correct
4 Correct 16 ms 23776 KB Output is correct
5 Correct 17 ms 23908 KB Output is correct
6 Correct 15 ms 23764 KB Output is correct
7 Correct 16 ms 23764 KB Output is correct
8 Correct 16 ms 23760 KB Output is correct
9 Correct 16 ms 23892 KB Output is correct
10 Correct 16 ms 24020 KB Output is correct
11 Correct 25 ms 24020 KB Output is correct
12 Correct 16 ms 23992 KB Output is correct
13 Correct 16 ms 23924 KB Output is correct
14 Correct 17 ms 23992 KB Output is correct
15 Correct 16 ms 23892 KB Output is correct
16 Correct 16 ms 24244 KB Output is correct
17 Correct 17 ms 23956 KB Output is correct
18 Correct 16 ms 23716 KB Output is correct
19 Correct 17 ms 23876 KB Output is correct
20 Correct 16 ms 23820 KB Output is correct
21 Correct 16 ms 23752 KB Output is correct
22 Correct 16 ms 23848 KB Output is correct
23 Correct 16 ms 23752 KB Output is correct
24 Correct 16 ms 23712 KB Output is correct
25 Correct 16 ms 23764 KB Output is correct
26 Correct 16 ms 23732 KB Output is correct
27 Correct 16 ms 23732 KB Output is correct
28 Correct 16 ms 23948 KB Output is correct
29 Correct 16 ms 23752 KB Output is correct
30 Correct 18 ms 24004 KB Output is correct
31 Correct 16 ms 23948 KB Output is correct
32 Correct 16 ms 24020 KB Output is correct
33 Correct 64 ms 34892 KB Output is correct
34 Correct 16 ms 24276 KB Output is correct
35 Correct 17 ms 25172 KB Output is correct
36 Correct 43 ms 33232 KB Output is correct
37 Correct 34 ms 50112 KB Output is correct
38 Correct 52 ms 34896 KB Output is correct
39 Correct 54 ms 34380 KB Output is correct
40 Correct 61 ms 34876 KB Output is correct
41 Correct 59 ms 35020 KB Output is correct
42 Correct 51 ms 34368 KB Output is correct
43 Correct 39 ms 34768 KB Output is correct
44 Correct 38 ms 34840 KB Output is correct
45 Correct 25 ms 30820 KB Output is correct
46 Correct 39 ms 61524 KB Output is correct
47 Correct 33 ms 37436 KB Output is correct
48 Correct 50 ms 38628 KB Output is correct
49 Correct 55 ms 40268 KB Output is correct
50 Correct 38 ms 36720 KB Output is correct
51 Correct 38 ms 36588 KB Output is correct
52 Correct 64 ms 34756 KB Output is correct
53 Correct 67 ms 34736 KB Output is correct
54 Correct 52 ms 34636 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 16 ms 23764 KB Output is correct
3 Correct 16 ms 23780 KB Output is correct
4 Correct 16 ms 23776 KB Output is correct
5 Correct 17 ms 23908 KB Output is correct
6 Correct 15 ms 23764 KB Output is correct
7 Correct 16 ms 23764 KB Output is correct
8 Correct 16 ms 23760 KB Output is correct
9 Correct 16 ms 23892 KB Output is correct
10 Correct 16 ms 24020 KB Output is correct
11 Correct 25 ms 24020 KB Output is correct
12 Correct 16 ms 23992 KB Output is correct
13 Correct 16 ms 23924 KB Output is correct
14 Correct 17 ms 23992 KB Output is correct
15 Correct 16 ms 23892 KB Output is correct
16 Correct 16 ms 24244 KB Output is correct
17 Correct 17 ms 23956 KB Output is correct
18 Correct 16 ms 23716 KB Output is correct
19 Correct 17 ms 23876 KB Output is correct
20 Correct 16 ms 23820 KB Output is correct
21 Correct 16 ms 23752 KB Output is correct
22 Correct 16 ms 23848 KB Output is correct
23 Correct 16 ms 23752 KB Output is correct
24 Correct 16 ms 23712 KB Output is correct
25 Correct 16 ms 23764 KB Output is correct
26 Correct 16 ms 23732 KB Output is correct
27 Correct 16 ms 23732 KB Output is correct
28 Correct 16 ms 23948 KB Output is correct
29 Correct 16 ms 23752 KB Output is correct
30 Correct 18 ms 24004 KB Output is correct
31 Correct 16 ms 23948 KB Output is correct
32 Correct 16 ms 24020 KB Output is correct
33 Correct 64 ms 34892 KB Output is correct
34 Correct 16 ms 24276 KB Output is correct
35 Correct 17 ms 25172 KB Output is correct
36 Correct 43 ms 33232 KB Output is correct
37 Correct 34 ms 50112 KB Output is correct
38 Correct 52 ms 34896 KB Output is correct
39 Correct 54 ms 34380 KB Output is correct
40 Correct 61 ms 34876 KB Output is correct
41 Correct 59 ms 35020 KB Output is correct
42 Correct 51 ms 34368 KB Output is correct
43 Correct 39 ms 34768 KB Output is correct
44 Correct 38 ms 34840 KB Output is correct
45 Correct 25 ms 30820 KB Output is correct
46 Correct 39 ms 61524 KB Output is correct
47 Correct 33 ms 37436 KB Output is correct
48 Correct 50 ms 38628 KB Output is correct
49 Correct 55 ms 40268 KB Output is correct
50 Correct 38 ms 36720 KB Output is correct
51 Correct 38 ms 36588 KB Output is correct
52 Correct 64 ms 34756 KB Output is correct
53 Correct 67 ms 34736 KB Output is correct
54 Correct 52 ms 34636 KB Output is correct
55 Correct 146 ms 53752 KB Output is correct
56 Correct 39 ms 37024 KB Output is correct
57 Correct 135 ms 52172 KB Output is correct
58 Correct 97 ms 56736 KB Output is correct
59 Correct 136 ms 53148 KB Output is correct
60 Correct 167 ms 53524 KB Output is correct
61 Correct 151 ms 53996 KB Output is correct
62 Correct 125 ms 53064 KB Output is correct
63 Correct 85 ms 54368 KB Output is correct
64 Correct 83 ms 54288 KB Output is correct
65 Correct 44 ms 42316 KB Output is correct
66 Correct 73 ms 118476 KB Output is correct
67 Correct 74 ms 58720 KB Output is correct
68 Correct 96 ms 61808 KB Output is correct
69 Correct 100 ms 60748 KB Output is correct
70 Correct 134 ms 63876 KB Output is correct
71 Correct 98 ms 56080 KB Output is correct
72 Correct 164 ms 53140 KB Output is correct
73 Correct 170 ms 53144 KB Output is correct
74 Correct 130 ms 53320 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23716 KB Output is correct
2 Correct 15 ms 23744 KB Output is correct
3 Correct 20 ms 24020 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 18 ms 23904 KB Output is correct
6 Correct 16 ms 24020 KB Output is correct
7 Correct 16 ms 23824 KB Output is correct
8 Correct 17 ms 24200 KB Output is correct
9 Correct 17 ms 23752 KB Output is correct
10 Correct 15 ms 23764 KB Output is correct
11 Correct 16 ms 23764 KB Output is correct
12 Correct 16 ms 23732 KB Output is correct
13 Correct 16 ms 23764 KB Output is correct
14 Correct 16 ms 23768 KB Output is correct
15 Correct 16 ms 23828 KB Output is correct
16 Correct 16 ms 23992 KB Output is correct
17 Correct 16 ms 24012 KB Output is correct
18 Correct 17 ms 23940 KB Output is correct
19 Correct 64 ms 34800 KB Output is correct
20 Correct 33 ms 50016 KB Output is correct
21 Correct 57 ms 34368 KB Output is correct
22 Correct 63 ms 34892 KB Output is correct
23 Correct 58 ms 34972 KB Output is correct
24 Correct 29 ms 30736 KB Output is correct
25 Correct 39 ms 61580 KB Output is correct
26 Correct 64 ms 34836 KB Output is correct
27 Correct 63 ms 34640 KB Output is correct
28 Correct 51 ms 34652 KB Output is correct
29 Correct 156 ms 53720 KB Output is correct
30 Correct 38 ms 37088 KB Output is correct
31 Correct 144 ms 53140 KB Output is correct
32 Correct 166 ms 53552 KB Output is correct
33 Correct 148 ms 53908 KB Output is correct
34 Correct 44 ms 42384 KB Output is correct
35 Correct 71 ms 118516 KB Output is correct
36 Correct 172 ms 53076 KB Output is correct
37 Correct 168 ms 53196 KB Output is correct
38 Correct 139 ms 53320 KB Output is correct
39 Correct 1987 ms 340296 KB Output is correct
40 Correct 130 ms 64760 KB Output is correct
41 Correct 61 ms 60820 KB Output is correct
42 Correct 240 ms 68528 KB Output is correct
43 Correct 119 ms 91008 KB Output is correct
44 Correct 412 ms 169852 KB Output is correct
45 Correct 406 ms 213144 KB Output is correct
46 Correct 1764 ms 336388 KB Output is correct
47 Execution timed out 2100 ms 336600 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23716 KB Output is correct
2 Correct 15 ms 23744 KB Output is correct
3 Correct 20 ms 24020 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 18 ms 23904 KB Output is correct
6 Correct 16 ms 24020 KB Output is correct
7 Correct 16 ms 23824 KB Output is correct
8 Correct 17 ms 24200 KB Output is correct
9 Correct 17 ms 23752 KB Output is correct
10 Correct 15 ms 23764 KB Output is correct
11 Correct 16 ms 23764 KB Output is correct
12 Correct 16 ms 23732 KB Output is correct
13 Correct 16 ms 23764 KB Output is correct
14 Correct 16 ms 23768 KB Output is correct
15 Correct 16 ms 23828 KB Output is correct
16 Correct 16 ms 23992 KB Output is correct
17 Correct 16 ms 24012 KB Output is correct
18 Correct 17 ms 23940 KB Output is correct
19 Correct 64 ms 34800 KB Output is correct
20 Correct 33 ms 50016 KB Output is correct
21 Correct 57 ms 34368 KB Output is correct
22 Correct 63 ms 34892 KB Output is correct
23 Correct 58 ms 34972 KB Output is correct
24 Correct 29 ms 30736 KB Output is correct
25 Correct 39 ms 61580 KB Output is correct
26 Correct 64 ms 34836 KB Output is correct
27 Correct 63 ms 34640 KB Output is correct
28 Correct 51 ms 34652 KB Output is correct
29 Correct 156 ms 53720 KB Output is correct
30 Correct 38 ms 37088 KB Output is correct
31 Correct 144 ms 53140 KB Output is correct
32 Correct 166 ms 53552 KB Output is correct
33 Correct 148 ms 53908 KB Output is correct
34 Correct 44 ms 42384 KB Output is correct
35 Correct 71 ms 118516 KB Output is correct
36 Correct 172 ms 53076 KB Output is correct
37 Correct 168 ms 53196 KB Output is correct
38 Correct 139 ms 53320 KB Output is correct
39 Correct 1987 ms 340296 KB Output is correct
40 Correct 130 ms 64760 KB Output is correct
41 Correct 61 ms 60820 KB Output is correct
42 Correct 240 ms 68528 KB Output is correct
43 Correct 119 ms 91008 KB Output is correct
44 Correct 412 ms 169852 KB Output is correct
45 Correct 406 ms 213144 KB Output is correct
46 Correct 1764 ms 336388 KB Output is correct
47 Execution timed out 2100 ms 336600 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23716 KB Output is correct
2 Correct 15 ms 23744 KB Output is correct
3 Correct 20 ms 24020 KB Output is correct
4 Correct 16 ms 23884 KB Output is correct
5 Correct 18 ms 23904 KB Output is correct
6 Correct 16 ms 24020 KB Output is correct
7 Correct 16 ms 23824 KB Output is correct
8 Correct 17 ms 24200 KB Output is correct
9 Correct 17 ms 23752 KB Output is correct
10 Correct 15 ms 23764 KB Output is correct
11 Correct 16 ms 23764 KB Output is correct
12 Correct 16 ms 23732 KB Output is correct
13 Correct 16 ms 23764 KB Output is correct
14 Correct 16 ms 23768 KB Output is correct
15 Correct 16 ms 23828 KB Output is correct
16 Correct 16 ms 23992 KB Output is correct
17 Correct 16 ms 24012 KB Output is correct
18 Correct 17 ms 23940 KB Output is correct
19 Correct 64 ms 34800 KB Output is correct
20 Correct 33 ms 50016 KB Output is correct
21 Correct 57 ms 34368 KB Output is correct
22 Correct 63 ms 34892 KB Output is correct
23 Correct 58 ms 34972 KB Output is correct
24 Correct 29 ms 30736 KB Output is correct
25 Correct 39 ms 61580 KB Output is correct
26 Correct 64 ms 34836 KB Output is correct
27 Correct 63 ms 34640 KB Output is correct
28 Correct 51 ms 34652 KB Output is correct
29 Correct 156 ms 53720 KB Output is correct
30 Correct 38 ms 37088 KB Output is correct
31 Correct 144 ms 53140 KB Output is correct
32 Correct 166 ms 53552 KB Output is correct
33 Correct 148 ms 53908 KB Output is correct
34 Correct 44 ms 42384 KB Output is correct
35 Correct 71 ms 118516 KB Output is correct
36 Correct 172 ms 53076 KB Output is correct
37 Correct 168 ms 53196 KB Output is correct
38 Correct 139 ms 53320 KB Output is correct
39 Correct 1987 ms 340296 KB Output is correct
40 Correct 130 ms 64760 KB Output is correct
41 Correct 61 ms 60820 KB Output is correct
42 Correct 240 ms 68528 KB Output is correct
43 Correct 119 ms 91008 KB Output is correct
44 Correct 412 ms 169852 KB Output is correct
45 Correct 406 ms 213144 KB Output is correct
46 Correct 1764 ms 336388 KB Output is correct
47 Execution timed out 2100 ms 336600 KB Time limit exceeded
48 Halted 0 ms 0 KB -