oj.uz

Submission #827944

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

#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 = 4206900;

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

int LG2[UNTIL];

int csqrt[UNTIL], fsqrt[UNTIL];

void init() {
  LG2[1] = 0;
  for (int i = 2; i < UNTIL; ++i) LG2[i] = LG2[i >> 1] + 1;
  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:3:9: warning: #pragma once in main file
    3 | #pragma once
      |         ^~~~
Main.cpp:24:5: warning: built-in function 'csqrt' declared as non-function [-Wbuiltin-declaration-mismatch]
   24 | int csqrt[UNTIL], fsqrt[UNTIL];
      |     ^~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49608 KB Output is correct
2 Correct 29 ms 49708 KB Output is correct
3 Correct 29 ms 49932 KB Output is correct
4 Correct 29 ms 49836 KB Output is correct
5 Correct 30 ms 49876 KB Output is correct
6 Correct 29 ms 49920 KB Output is correct
7 Correct 28 ms 49816 KB Output is correct
8 Correct 29 ms 50164 KB Output is correct
9 Correct 29 ms 49636 KB Output is correct
10 Correct 29 ms 49696 KB Output is correct
11 Correct 29 ms 49608 KB Output is correct
12 Correct 29 ms 49684 KB Output is correct
13 Correct 30 ms 49660 KB Output is correct
14 Correct 27 ms 49684 KB Output is correct
15 Correct 28 ms 49664 KB Output is correct
16 Correct 31 ms 49940 KB Output is correct
17 Correct 33 ms 49868 KB Output is correct
18 Correct 28 ms 49832 KB Output is correct
19 Correct 75 ms 60832 KB Output is correct
20 Correct 45 ms 75968 KB Output is correct
21 Correct 67 ms 60300 KB Output is correct
22 Correct 75 ms 60836 KB Output is correct
23 Correct 72 ms 60876 KB Output is correct
24 Correct 41 ms 56732 KB Output is correct
25 Correct 51 ms 87432 KB Output is correct
26 Correct 76 ms 60736 KB Output is correct
27 Correct 78 ms 60552 KB Output is correct
28 Correct 64 ms 60592 KB Output is correct
29 Correct 152 ms 79612 KB Output is correct
30 Correct 50 ms 63020 KB Output is correct
31 Correct 146 ms 79076 KB Output is correct
32 Correct 177 ms 79432 KB Output is correct
33 Correct 157 ms 79852 KB Output is correct
34 Correct 56 ms 68252 KB Output is correct
35 Correct 87 ms 144496 KB Output is correct
36 Correct 172 ms 79088 KB Output is correct
37 Correct 186 ms 79168 KB Output is correct
38 Correct 142 ms 79308 KB Output is correct
39 Correct 1975 ms 366276 KB Output is correct
40 Correct 140 ms 90900 KB Output is correct
41 Correct 74 ms 86860 KB Output is correct
42 Correct 252 ms 94752 KB Output is correct
43 Correct 125 ms 117104 KB Output is correct
44 Correct 423 ms 196520 KB Output is correct
45 Correct 403 ms 239796 KB Output is correct
46 Correct 1752 ms 363752 KB Output is correct
47 Execution timed out 2074 ms 360284 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #2
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49620 KB Output is correct
2 Correct 28 ms 49656 KB Output is correct
3 Correct 31 ms 49668 KB Output is correct
4 Correct 29 ms 49616 KB Output is correct
5 Correct 29 ms 49840 KB Output is correct
6 Correct 29 ms 49696 KB Output is correct
7 Correct 28 ms 49716 KB Output is correct
8 Correct 28 ms 49700 KB Output is correct
9 Correct 29 ms 49896 KB Output is correct
10 Correct 30 ms 49876 KB Output is correct
11 Correct 32 ms 50100 KB Output is correct
12 Correct 29 ms 49908 KB Output is correct
13 Correct 29 ms 49892 KB Output is correct
14 Correct 28 ms 49868 KB Output is correct
15 Correct 28 ms 49812 KB Output is correct
16 Correct 29 ms 50084 KB Output is correct
17 Correct 29 ms 49908 KB Output is correct
18 Correct 28 ms 49608 KB Output is correct
19 Correct 29 ms 49808 KB Output is correct
20 Correct 30 ms 49800 KB Output is correct
21 Correct 30 ms 49664 KB Output is correct
22 Correct 29 ms 49868 KB Output is correct
23 Correct 29 ms 49752 KB Output is correct
24 Correct 28 ms 49708 KB Output is correct
25 Correct 28 ms 49600 KB Output is correct
26 Correct 28 ms 49748 KB Output is correct
27 Correct 28 ms 49664 KB Output is correct
28 Correct 27 ms 49932 KB Output is correct
29 Correct 28 ms 49708 KB Output is correct
30 Correct 30 ms 49932 KB Output is correct
31 Correct 30 ms 49832 KB Output is correct
32 Correct 29 ms 49844 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49708 KB Output is correct
2 Correct 27 ms 49704 KB Output is correct
3 Correct 28 ms 49668 KB Output is correct
4 Correct 27 ms 49620 KB Output is correct
5 Correct 32 ms 49696 KB Output is correct
6 Correct 28 ms 49612 KB Output is correct
7 Correct 28 ms 49868 KB Output is correct
8 Correct 27 ms 49872 KB Output is correct
9 Correct 27 ms 49824 KB Output is correct
10 Correct 28 ms 49832 KB Output is correct
11 Correct 28 ms 49888 KB Output is correct
12 Correct 28 ms 49740 KB Output is correct
13 Correct 29 ms 49648 KB Output is correct
14 Correct 28 ms 49848 KB Output is correct
15 Correct 28 ms 49620 KB Output is correct
16 Correct 29 ms 49756 KB Output is correct
17 Correct 28 ms 49648 KB Output is correct
18 Correct 29 ms 49692 KB Output is correct
19 Correct 29 ms 49672 KB Output is correct
20 Correct 29 ms 49640 KB Output is correct
21 Correct 28 ms 49872 KB Output is correct
22 Correct 29 ms 49876 KB Output is correct
23 Correct 29 ms 49904 KB Output is correct
24 Correct 29 ms 50196 KB Output is correct
25 Correct 55 ms 59108 KB Output is correct
26 Correct 70 ms 60804 KB Output is correct
27 Correct 68 ms 60288 KB Output is correct
28 Correct 71 ms 60236 KB Output is correct
29 Correct 52 ms 60728 KB Output is correct
30 Correct 51 ms 60688 KB Output is correct
31 Correct 52 ms 62540 KB Output is correct
32 Correct 76 ms 60720 KB Output is correct
33 Correct 85 ms 60532 KB Output is correct
34 Correct 143 ms 78004 KB Output is correct
35 Correct 147 ms 79052 KB Output is correct
36 Correct 129 ms 79092 KB Output is correct
37 Correct 94 ms 80220 KB Output is correct
38 Correct 96 ms 80212 KB Output is correct
39 Correct 533 ms 152148 KB Output is correct
40 Correct 1322 ms 331192 KB Output is correct
41 Correct 1745 ms 362260 KB Output is correct
42 Correct 1417 ms 362308 KB Output is correct
43 Correct 871 ms 374348 KB Output is correct
44 Correct 854 ms 374392 KB Output is correct
45 Correct 1098 ms 398940 KB Output is correct
46 Correct 1112 ms 384180 KB Output is correct

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49620 KB Output is correct
2 Correct 28 ms 49656 KB Output is correct
3 Correct 31 ms 49668 KB Output is correct
4 Correct 29 ms 49616 KB Output is correct
5 Correct 29 ms 49840 KB Output is correct
6 Correct 29 ms 49696 KB Output is correct
7 Correct 28 ms 49716 KB Output is correct
8 Correct 28 ms 49700 KB Output is correct
9 Correct 29 ms 49896 KB Output is correct
10 Correct 30 ms 49876 KB Output is correct
11 Correct 32 ms 50100 KB Output is correct
12 Correct 29 ms 49908 KB Output is correct
13 Correct 29 ms 49892 KB Output is correct
14 Correct 28 ms 49868 KB Output is correct
15 Correct 28 ms 49812 KB Output is correct
16 Correct 29 ms 50084 KB Output is correct
17 Correct 29 ms 49908 KB Output is correct
18 Correct 28 ms 49608 KB Output is correct
19 Correct 29 ms 49808 KB Output is correct
20 Correct 30 ms 49800 KB Output is correct
21 Correct 30 ms 49664 KB Output is correct
22 Correct 29 ms 49868 KB Output is correct
23 Correct 29 ms 49752 KB Output is correct
24 Correct 28 ms 49708 KB Output is correct
25 Correct 28 ms 49600 KB Output is correct
26 Correct 28 ms 49748 KB Output is correct
27 Correct 28 ms 49664 KB Output is correct
28 Correct 27 ms 49932 KB Output is correct
29 Correct 28 ms 49708 KB Output is correct
30 Correct 30 ms 49932 KB Output is correct
31 Correct 30 ms 49832 KB Output is correct
32 Correct 29 ms 49844 KB Output is correct
33 Correct 75 ms 60828 KB Output is correct
34 Correct 29 ms 50224 KB Output is correct
35 Correct 30 ms 51028 KB Output is correct
36 Correct 56 ms 59188 KB Output is correct
37 Correct 45 ms 75980 KB Output is correct
38 Correct 64 ms 60856 KB Output is correct
39 Correct 66 ms 60232 KB Output is correct
40 Correct 75 ms 60756 KB Output is correct
41 Correct 71 ms 60856 KB Output is correct
42 Correct 73 ms 60208 KB Output is correct
43 Correct 52 ms 60748 KB Output is correct
44 Correct 52 ms 60756 KB Output is correct
45 Correct 39 ms 56768 KB Output is correct
46 Correct 53 ms 87416 KB Output is correct
47 Correct 46 ms 63392 KB Output is correct
48 Correct 62 ms 64624 KB Output is correct
49 Correct 67 ms 66172 KB Output is correct
50 Correct 50 ms 62712 KB Output is correct
51 Correct 51 ms 62580 KB Output is correct
52 Correct 76 ms 60740 KB Output is correct
53 Correct 76 ms 60592 KB Output is correct
54 Correct 67 ms 60552 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 49620 KB Output is correct
2 Correct 28 ms 49656 KB Output is correct
3 Correct 31 ms 49668 KB Output is correct
4 Correct 29 ms 49616 KB Output is correct
5 Correct 29 ms 49840 KB Output is correct
6 Correct 29 ms 49696 KB Output is correct
7 Correct 28 ms 49716 KB Output is correct
8 Correct 28 ms 49700 KB Output is correct
9 Correct 29 ms 49896 KB Output is correct
10 Correct 30 ms 49876 KB Output is correct
11 Correct 32 ms 50100 KB Output is correct
12 Correct 29 ms 49908 KB Output is correct
13 Correct 29 ms 49892 KB Output is correct
14 Correct 28 ms 49868 KB Output is correct
15 Correct 28 ms 49812 KB Output is correct
16 Correct 29 ms 50084 KB Output is correct
17 Correct 29 ms 49908 KB Output is correct
18 Correct 28 ms 49608 KB Output is correct
19 Correct 29 ms 49808 KB Output is correct
20 Correct 30 ms 49800 KB Output is correct
21 Correct 30 ms 49664 KB Output is correct
22 Correct 29 ms 49868 KB Output is correct
23 Correct 29 ms 49752 KB Output is correct
24 Correct 28 ms 49708 KB Output is correct
25 Correct 28 ms 49600 KB Output is correct
26 Correct 28 ms 49748 KB Output is correct
27 Correct 28 ms 49664 KB Output is correct
28 Correct 27 ms 49932 KB Output is correct
29 Correct 28 ms 49708 KB Output is correct
30 Correct 30 ms 49932 KB Output is correct
31 Correct 30 ms 49832 KB Output is correct
32 Correct 29 ms 49844 KB Output is correct
33 Correct 75 ms 60828 KB Output is correct
34 Correct 29 ms 50224 KB Output is correct
35 Correct 30 ms 51028 KB Output is correct
36 Correct 56 ms 59188 KB Output is correct
37 Correct 45 ms 75980 KB Output is correct
38 Correct 64 ms 60856 KB Output is correct
39 Correct 66 ms 60232 KB Output is correct
40 Correct 75 ms 60756 KB Output is correct
41 Correct 71 ms 60856 KB Output is correct
42 Correct 73 ms 60208 KB Output is correct
43 Correct 52 ms 60748 KB Output is correct
44 Correct 52 ms 60756 KB Output is correct
45 Correct 39 ms 56768 KB Output is correct
46 Correct 53 ms 87416 KB Output is correct
47 Correct 46 ms 63392 KB Output is correct
48 Correct 62 ms 64624 KB Output is correct
49 Correct 67 ms 66172 KB Output is correct
50 Correct 50 ms 62712 KB Output is correct
51 Correct 51 ms 62580 KB Output is correct
52 Correct 76 ms 60740 KB Output is correct
53 Correct 76 ms 60592 KB Output is correct
54 Correct 67 ms 60552 KB Output is correct
55 Correct 155 ms 79636 KB Output is correct
56 Correct 51 ms 62924 KB Output is correct
57 Correct 142 ms 78076 KB Output is correct
58 Correct 111 ms 82712 KB Output is correct
59 Correct 148 ms 79064 KB Output is correct
60 Correct 175 ms 79436 KB Output is correct
61 Correct 156 ms 79836 KB Output is correct
62 Correct 137 ms 79024 KB Output is correct
63 Correct 96 ms 80288 KB Output is correct
64 Correct 95 ms 80312 KB Output is correct
65 Correct 56 ms 68320 KB Output is correct
66 Correct 82 ms 144428 KB Output is correct
67 Correct 84 ms 84428 KB Output is correct
68 Correct 113 ms 87840 KB Output is correct
69 Correct 113 ms 86656 KB Output is correct
70 Correct 145 ms 89852 KB Output is correct
71 Correct 113 ms 82020 KB Output is correct
72 Correct 171 ms 79128 KB Output is correct
73 Correct 176 ms 79068 KB Output is correct
74 Correct 142 ms 79308 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49608 KB Output is correct
2 Correct 29 ms 49708 KB Output is correct
3 Correct 29 ms 49932 KB Output is correct
4 Correct 29 ms 49836 KB Output is correct
5 Correct 30 ms 49876 KB Output is correct
6 Correct 29 ms 49920 KB Output is correct
7 Correct 28 ms 49816 KB Output is correct
8 Correct 29 ms 50164 KB Output is correct
9 Correct 29 ms 49636 KB Output is correct
10 Correct 29 ms 49696 KB Output is correct
11 Correct 29 ms 49608 KB Output is correct
12 Correct 29 ms 49684 KB Output is correct
13 Correct 30 ms 49660 KB Output is correct
14 Correct 27 ms 49684 KB Output is correct
15 Correct 28 ms 49664 KB Output is correct
16 Correct 31 ms 49940 KB Output is correct
17 Correct 33 ms 49868 KB Output is correct
18 Correct 28 ms 49832 KB Output is correct
19 Correct 75 ms 60832 KB Output is correct
20 Correct 45 ms 75968 KB Output is correct
21 Correct 67 ms 60300 KB Output is correct
22 Correct 75 ms 60836 KB Output is correct
23 Correct 72 ms 60876 KB Output is correct
24 Correct 41 ms 56732 KB Output is correct
25 Correct 51 ms 87432 KB Output is correct
26 Correct 76 ms 60736 KB Output is correct
27 Correct 78 ms 60552 KB Output is correct
28 Correct 64 ms 60592 KB Output is correct
29 Correct 152 ms 79612 KB Output is correct
30 Correct 50 ms 63020 KB Output is correct
31 Correct 146 ms 79076 KB Output is correct
32 Correct 177 ms 79432 KB Output is correct
33 Correct 157 ms 79852 KB Output is correct
34 Correct 56 ms 68252 KB Output is correct
35 Correct 87 ms 144496 KB Output is correct
36 Correct 172 ms 79088 KB Output is correct
37 Correct 186 ms 79168 KB Output is correct
38 Correct 142 ms 79308 KB Output is correct
39 Correct 1975 ms 366276 KB Output is correct
40 Correct 140 ms 90900 KB Output is correct
41 Correct 74 ms 86860 KB Output is correct
42 Correct 252 ms 94752 KB Output is correct
43 Correct 125 ms 117104 KB Output is correct
44 Correct 423 ms 196520 KB Output is correct
45 Correct 403 ms 239796 KB Output is correct
46 Correct 1752 ms 363752 KB Output is correct
47 Execution timed out 2074 ms 360284 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49608 KB Output is correct
2 Correct 29 ms 49708 KB Output is correct
3 Correct 29 ms 49932 KB Output is correct
4 Correct 29 ms 49836 KB Output is correct
5 Correct 30 ms 49876 KB Output is correct
6 Correct 29 ms 49920 KB Output is correct
7 Correct 28 ms 49816 KB Output is correct
8 Correct 29 ms 50164 KB Output is correct
9 Correct 29 ms 49636 KB Output is correct
10 Correct 29 ms 49696 KB Output is correct
11 Correct 29 ms 49608 KB Output is correct
12 Correct 29 ms 49684 KB Output is correct
13 Correct 30 ms 49660 KB Output is correct
14 Correct 27 ms 49684 KB Output is correct
15 Correct 28 ms 49664 KB Output is correct
16 Correct 31 ms 49940 KB Output is correct
17 Correct 33 ms 49868 KB Output is correct
18 Correct 28 ms 49832 KB Output is correct
19 Correct 75 ms 60832 KB Output is correct
20 Correct 45 ms 75968 KB Output is correct
21 Correct 67 ms 60300 KB Output is correct
22 Correct 75 ms 60836 KB Output is correct
23 Correct 72 ms 60876 KB Output is correct
24 Correct 41 ms 56732 KB Output is correct
25 Correct 51 ms 87432 KB Output is correct
26 Correct 76 ms 60736 KB Output is correct
27 Correct 78 ms 60552 KB Output is correct
28 Correct 64 ms 60592 KB Output is correct
29 Correct 152 ms 79612 KB Output is correct
30 Correct 50 ms 63020 KB Output is correct
31 Correct 146 ms 79076 KB Output is correct
32 Correct 177 ms 79432 KB Output is correct
33 Correct 157 ms 79852 KB Output is correct
34 Correct 56 ms 68252 KB Output is correct
35 Correct 87 ms 144496 KB Output is correct
36 Correct 172 ms 79088 KB Output is correct
37 Correct 186 ms 79168 KB Output is correct
38 Correct 142 ms 79308 KB Output is correct
39 Correct 1975 ms 366276 KB Output is correct
40 Correct 140 ms 90900 KB Output is correct
41 Correct 74 ms 86860 KB Output is correct
42 Correct 252 ms 94752 KB Output is correct
43 Correct 125 ms 117104 KB Output is correct
44 Correct 423 ms 196520 KB Output is correct
45 Correct 403 ms 239796 KB Output is correct
46 Correct 1752 ms 363752 KB Output is correct
47 Execution timed out 2074 ms 360284 KB Time limit exceeded
48 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49608 KB Output is correct
2 Correct 29 ms 49708 KB Output is correct
3 Correct 29 ms 49932 KB Output is correct
4 Correct 29 ms 49836 KB Output is correct
5 Correct 30 ms 49876 KB Output is correct
6 Correct 29 ms 49920 KB Output is correct
7 Correct 28 ms 49816 KB Output is correct
8 Correct 29 ms 50164 KB Output is correct
9 Correct 29 ms 49636 KB Output is correct
10 Correct 29 ms 49696 KB Output is correct
11 Correct 29 ms 49608 KB Output is correct
12 Correct 29 ms 49684 KB Output is correct
13 Correct 30 ms 49660 KB Output is correct
14 Correct 27 ms 49684 KB Output is correct
15 Correct 28 ms 49664 KB Output is correct
16 Correct 31 ms 49940 KB Output is correct
17 Correct 33 ms 49868 KB Output is correct
18 Correct 28 ms 49832 KB Output is correct
19 Correct 75 ms 60832 KB Output is correct
20 Correct 45 ms 75968 KB Output is correct
21 Correct 67 ms 60300 KB Output is correct
22 Correct 75 ms 60836 KB Output is correct
23 Correct 72 ms 60876 KB Output is correct
24 Correct 41 ms 56732 KB Output is correct
25 Correct 51 ms 87432 KB Output is correct
26 Correct 76 ms 60736 KB Output is correct
27 Correct 78 ms 60552 KB Output is correct
28 Correct 64 ms 60592 KB Output is correct
29 Correct 152 ms 79612 KB Output is correct
30 Correct 50 ms 63020 KB Output is correct
31 Correct 146 ms 79076 KB Output is correct
32 Correct 177 ms 79432 KB Output is correct
33 Correct 157 ms 79852 KB Output is correct
34 Correct 56 ms 68252 KB Output is correct
35 Correct 87 ms 144496 KB Output is correct
36 Correct 172 ms 79088 KB Output is correct
37 Correct 186 ms 79168 KB Output is correct
38 Correct 142 ms 79308 KB Output is correct
39 Correct 1975 ms 366276 KB Output is correct
40 Correct 140 ms 90900 KB Output is correct
41 Correct 74 ms 86860 KB Output is correct
42 Correct 252 ms 94752 KB Output is correct
43 Correct 125 ms 117104 KB Output is correct
44 Correct 423 ms 196520 KB Output is correct
45 Correct 403 ms 239796 KB Output is correct
46 Correct 1752 ms 363752 KB Output is correct
47 Execution timed out 2074 ms 360284 KB Time limit exceeded
48 Halted 0 ms 0 KB -