oj.uz

Submission #659015

# Submission time Handle Problem Language Result Execution time Memory
659015 2022-11-15T19:28:18 Z 600Mihnea New Home (APIO18_new_home) C++17
100 / 100
 4484 ms 175708 KB 
bool home = 0;

#include <bits/stdc++.h>

using namespace std;

struct MinSegmentTree {
  vector<int> tree;
  int nn;
  void upd(int v, int tl, int tr, int i, int x) {
    if (tr < i || i < tl) {
      return;
    }
    if (tl == tr) {
      assert(tl == i);
      assert(tr == i);
      tree[v] = x;

      return;
    }
    int tm = (tl + tr) / 2;
    upd(2 * v, tl, tm, i, x);
    upd(2 * v + 1, tm + 1, tr, i, x);
    tree[v] = min(tree[2 * v], tree[2 * v + 1]);
  }
  int getmin(int v, int tl, int tr, int l, int r) {
    if (tr < l || r < tl) {
      return (int) 1e9 + 7;
    }
    if (l <= tl && tr <= r) {
      return tree[v];
    }
    int tm = (tl + tr) / 2;
    return min(getmin(2 * v, tl, tm, l, r), getmin(2 * v + 1, tm + 1, tr, l, r));
  }
  void init(int n) {
    nn = n;
    tree.clear();
    tree.resize(4 * (n + 7), (int) 1e9 + 7);
  }
  void upd(int i, int x) {

    assert(0 <= i && i < nn);
    upd(1, 0, nn - 1, i, x);
  }
  int getmin(int l, int r) {
    if (l > r) {
      return (int) 1e9 + 7;
    }
    assert(0 <= l && l <= r && r < nn);
    return getmin(1, 0, nn - 1, l, r);
  }
};

struct Store {
  int x;
  int type;
  int first_time;
  int last_time;
};

struct Query {
  int x;
  int t;
};

const int N = (int) 3e5 + 7;
int n;
int k;
int q;
vector<int> whereType[N];
Store stores[N];
Query queries[N];
bool negative[N];
vector<int> events;

int getTimeOfEvent(int i) {
  if (i >= 1) {
    assert(1 <= i && i <= n);
    return stores[i].first_time;
  } else {
    i *= -1;
    assert(1 <= i && i <= n);
    return stores[i].last_time + 1;
  }
}

bool cmpEvents(int i, int j) {
  return getTimeOfEvent(i) < getTimeOfEvent(j);
}

struct Position {
  int i;
};

bool operator < (Position a, Position b) {
  int i = a.i, j = b.i;
  if (stores[i].x == stores[j].x) {
    return i < j;
  } else {
    return stores[i].x < stores[j].x;
  }
}

struct Segment {
  int first_time;
  int last_time;
  int x1;
  int x2;
};

struct RelaxSegment {
  int first_time;
  int last_time;
  int limit;
  int x;
};

vector<RelaxSegment> rels[2];

vector<Segment> segments;

void addSegment(int first_time, int last_time, int i, int j) {
  assert(1 <= i && i <= n + 2);
  assert(1 <= j && j <= n + 2);

  if (first_time > last_time) {
    return;
  }

  assert(0 <= first_time && first_time <= last_time && last_time < q);

  assert(stores[i].x <= stores[j].x);

  segments.push_back({first_time, last_time, stores[i].x, stores[j].x});
}

vector<RelaxSegment> relaxSegments;

int getTimeOfRelaxSegmentEvent(int i) {
  if (i >= 1) {
    i--;
    assert(0 <= i && i < (int) relaxSegments.size());
    return relaxSegments[i].first_time;
  } else {
    i *= -1;
    i--;
    assert(0 <= i && i < (int) relaxSegments.size());
    return relaxSegments[i].last_time + 1;
  }
}

bool cmpRelaxSegmentEvents(int i, int j) {
  return getTimeOfRelaxSegmentEvent(i) < getTimeOfRelaxSegmentEvent(j);
}

int print[N];
int small[N];

int main() {
  if (home) {
    freopen ("input.txt", "r", stdin);
  } else {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  }
  {
    /// Read
    cin >> n >> k >> q;
    for (int i = 1; i <= n; i++) {
      cin >> stores[i].x >> stores[i].type >> stores[i].first_time >> stores[i].last_time;
    }
    for (int i = 1; i <= q; i++) {
      cin >> queries[i].x >> queries[i].t;
    }
  }
  {
    /// Normalize time
    vector<int> interestingTimes;
    for (int i = 1; i <= q; i++) {
      interestingTimes.push_back(queries[i].t);
    }
    sort(interestingTimes.begin(), interestingTimes.end());
    interestingTimes.resize(unique(interestingTimes.begin(), interestingTimes.end()) - interestingTimes.begin());
    for (int i = 1; i <= q; i++) {
      queries[i].t = lower_bound(interestingTimes.begin(), interestingTimes.end(), queries[i].t) - interestingTimes.begin();
    }
    int y = 0;
    for (int i = 1; i <= n; i++) {
      stores[i].first_time = lower_bound(interestingTimes.begin(), interestingTimes.end(), stores[i].first_time) - interestingTimes.begin();
      stores[i].last_time = lower_bound(interestingTimes.begin(), interestingTimes.end(), stores[i].last_time + 1) - interestingTimes.begin() - 1;
      if (stores[i].first_time <= stores[i].last_time) {
        stores[++y] = stores[i];
      }
    }
    n = y;
  }

  {
    /// Some more computation
    for (int i = 1; i <= n; i++) {
      whereType[stores[i].type].push_back(i);
    }
    stores[n + 1].x = -((int) 1e8 + 7);
    stores[n + 2].x = +((int) 2e8 + 7);
    for (int type = 1; type <= k; type++) {
      set<Position> positions;
      map<pair<int, int>, int> sinceWhen;
      positions.insert({n + 1});
      positions.insert({n + 2});

      sinceWhen[{n + 1, n + 2}] = 0;
      events.clear();
      for (auto &i : whereType[type]) {
        events.push_back(+i);
        events.push_back(-i);
      }
      sort(events.begin(), events.end(), cmpEvents);
      int l_events = 0;
      while (l_events < (int) events.size()) {
        int r_events = l_events;
        while (r_events + 1 < (int) events.size() && getTimeOfEvent(events[r_events + 1]) == getTimeOfEvent(events[r_events])) {
          r_events++;
        }
        int current_time = getTimeOfEvent(events[l_events]);
        for (int iter_events = l_events; iter_events <= r_events; iter_events++) {
          int i = events[iter_events];

          if (i >= 1) {
            assert(1 <= i && i <= n);
            positions.insert({i});


            auto it = positions.find({i});
            assert(it != positions.end());
            auto nxt = it;
            auto ant = it;
            nxt++;
            assert(nxt != positions.end());
            assert(ant != positions.begin());
            ant--;

            addSegment(sinceWhen[{ant->i, nxt->i}], current_time - 1, ant->i, nxt->i);

            assert(sinceWhen.count({ant->i, nxt->i}));
            sinceWhen.erase({ant->i, nxt->i});
            assert(!sinceWhen.count({ant->i, nxt->i}));
            sinceWhen[{ant->i, it->i}] = current_time;
            sinceWhen[{it->i, nxt->i}] = current_time;
          } else {
            i *= -1;
            assert(1 <= i && i <= n);
            assert(positions.count({i}));

            auto it = positions.find({i});
            assert(it != positions.end());
            auto nxt = it;
            auto ant = it;
            nxt++;
            assert(nxt != positions.end());
            assert(ant != positions.begin());
            ant--;

            assert(!sinceWhen.count({ant->i, nxt->i}));
            sinceWhen[{ant->i, nxt->i}] = current_time;
            assert(sinceWhen.count({ant->i, nxt->i}));


            addSegment(sinceWhen[{ant->i, it->i}], current_time - 1, ant->i, it->i);
            assert(sinceWhen.count({ant->i, it->i}));
            sinceWhen.erase({ant->i, it->i});

            addSegment(sinceWhen[{it->i, nxt->i}], current_time - 1, it->i, nxt->i);
            assert(sinceWhen.count({it->i, nxt->i}));
            sinceWhen.erase({it->i, nxt->i});

            positions.erase({i});
          }
        }
        l_events = r_events + 1;
      }
      for (auto &it : sinceWhen) {
        addSegment(it.second, q - 1, it.first.first, it.first.second);
      }
    }
  }
  {
    /// Some other Brute

    for (auto &segment : segments) {
      int t1 = segment.first_time;
      int t2 = segment.last_time;
      int x1 = segment.x1;
      int x2 = segment.x2;

      int xmid = (x1 + x2) / 2;
      int xmid2 = (x1 + x2 + 1) / 2;
      rels[0].push_back({t1, t2, xmid, x1});
      rels[1].push_back({t1, t2, -xmid2, -x2});
    }

    for (int inv = 0; inv <= 1; inv++) {
      for (int iq = 1; iq <= q; iq++) {
        small[iq] = (int) 1e9 + 7;
      }
      relaxSegments = rels[inv];
      MinSegmentTree tree;
      tree.init((int) relaxSegments.size());

      sort(relaxSegments.begin(), relaxSegments.end(), [&] (RelaxSegment a, RelaxSegment b) {
        return a.limit > b.limit;
      });

      vector<int> relaxSegmentEvents;
      for (int i = 0; i < (int) relaxSegments.size(); i++) {
        relaxSegmentEvents.push_back((i + 1));
        relaxSegmentEvents.push_back(-(i + 1));
      }

      sort(relaxSegmentEvents.begin(), relaxSegmentEvents.end(), cmpRelaxSegmentEvents);
      int p = 0;
      vector<int> ord;
      for (int iq = 1; iq <= q; iq++) {
        ord.push_back(iq);
      }
      sort(ord.begin(), ord.end(), [&] (int i, int j) {
        return queries[i].t < queries[j].t;
      });

      /*int l_events = 0;
      while (l_events < (int) relaxSegmentEvents.size()) {
        int r_events = l_events;
        while (r_events + 1 < (int) relaxSegmentEvents.size() && getTimeOfRelaxSegmentEvent(relaxSegmentEvents[r_events + 1]) == getTimeOfRelaxSegmentEvent(relaxSegmentEvents[r_events])) {
          r_events++;
        }
        int current_time = getTimeOfRelaxSegmentEvent(events[l_events]);
        for (int iter_events = l_events; iter_events <= r_events; iter_events++) {
          int i = relaxSegmentEvents[iter_events];

          if (i >= 1) {
            i--;
            assert(0 <= i && i < (int) relaxSegments.size());
          } else {
            i *= -1;
            i--;
            assert(0 <= i && i < (int) relaxSegments.size());
          }
        }
        l_events = r_events + 1;
      }*/
      for (auto &iq : ord) {
        while (p < (int) relaxSegmentEvents.size() && getTimeOfRelaxSegmentEvent(relaxSegmentEvents[p]) <= queries[iq].t) {
          int i = relaxSegmentEvents[p++];

          if (i >= 1) {
            i--;
            assert(0 <= i && i < (int) relaxSegments.size());
            /// add
            tree.upd(i, relaxSegments[i].x);
          } else {
            i *= -1;
            i--;
            assert(0 <= i && i < (int) relaxSegments.size());
            tree.upd(i, (int) 1e9 + 7);
            /// delete
          }
        }
        int cnt = 0, L = 0, R = (int) relaxSegments.size() - 1;
        while (L <= R) {
          int m = (L + R) / 2;
          if (queries[iq].x <= relaxSegments[m].limit) {
            cnt = m + 1;
            L = m + 1;
          } else {
            R = m - 1;
          }
        }
        if (cnt >= 1) {
          small[iq] = tree.getmin(0, cnt - 1);
        }
      }
      for (int iq = 1; iq <= q; iq++) {
        print[iq] = max(print[iq], queries[iq].x - small[iq]);
        queries[iq].x *= -1;
      }
    }

    for (int iq = 1; iq <= q; iq++) {
      int maxDist = print[iq];
      if (maxDist > (int) 1e8) {
        maxDist = -1;
      }
      cout << maxDist << "\n";
    }
  }
  if (0) {
    /// Brute
    for (int iq = 1; iq <= q; iq++) {
      int maxDist = 0;
      for (int t = 1; t <= k; t++) {
        int minDist = (int) 1e9 + 7;
        for (auto &i : whereType[t]) {
          if (stores[i].first_time <= queries[iq].t && queries[iq].t <= stores[i].last_time) {
            minDist = min(minDist, abs(stores[i].x - queries[iq].x));
          }
        }
        maxDist = max(maxDist, minDist);
      }
      if (maxDist == (int) 1e9 + 7) {
        maxDist = -1;
      }
      cout << maxDist << "\n";
    }
  }
  return 0;
}

Compilation message

new_home.cpp: In function 'int main()':
new_home.cpp:162:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     freopen ("input.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 6 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 6 ms 7508 KB Output is correct
13 Correct 5 ms 7636 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 6 ms 7508 KB Output is correct
18 Correct 6 ms 7464 KB Output is correct
19 Correct 6 ms 7592 KB Output is correct
20 Correct 6 ms 7508 KB Output is correct
21 Correct 4 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 6 ms 7508 KB Output is correct
24 Correct 6 ms 7508 KB Output is correct
25 Correct 6 ms 7508 KB Output is correct
26 Correct 6 ms 7520 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7500 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 6 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 6 ms 7508 KB Output is correct
13 Correct 5 ms 7636 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 6 ms 7508 KB Output is correct
18 Correct 6 ms 7464 KB Output is correct
19 Correct 6 ms 7592 KB Output is correct
20 Correct 6 ms 7508 KB Output is correct
21 Correct 4 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 6 ms 7508 KB Output is correct
24 Correct 6 ms 7508 KB Output is correct
25 Correct 6 ms 7508 KB Output is correct
26 Correct 6 ms 7520 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7500 KB Output is correct
31 Correct 554 ms 27232 KB Output is correct
32 Correct 352 ms 22888 KB Output is correct
33 Correct 612 ms 31636 KB Output is correct
34 Correct 559 ms 31612 KB Output is correct
35 Correct 581 ms 31384 KB Output is correct
36 Correct 605 ms 31740 KB Output is correct
37 Correct 517 ms 31352 KB Output is correct
38 Correct 557 ms 31556 KB Output is correct
39 Correct 452 ms 29764 KB Output is correct
40 Correct 474 ms 31452 KB Output is correct
41 Correct 493 ms 29980 KB Output is correct
42 Correct 504 ms 30176 KB Output is correct
43 Correct 160 ms 17868 KB Output is correct
44 Correct 493 ms 29992 KB Output is correct
45 Correct 496 ms 31288 KB Output is correct
46 Correct 480 ms 30380 KB Output is correct
47 Correct 360 ms 30120 KB Output is correct
48 Correct 327 ms 27480 KB Output is correct
49 Correct 385 ms 30452 KB Output is correct
50 Correct 411 ms 31348 KB Output is correct
51 Correct 390 ms 30056 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1147 ms 61632 KB Output is correct
2 Correct 1837 ms 49764 KB Output is correct
3 Correct 1353 ms 111988 KB Output is correct
4 Correct 1171 ms 67792 KB Output is correct
5 Correct 2583 ms 81040 KB Output is correct
6 Correct 2087 ms 53912 KB Output is correct
7 Correct 1259 ms 111984 KB Output is correct
8 Correct 1127 ms 67468 KB Output is correct
9 Correct 1134 ms 56592 KB Output is correct
10 Correct 1394 ms 48972 KB Output is correct
11 Correct 1222 ms 52312 KB Output is correct
12 Correct 1184 ms 48584 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2581 ms 79192 KB Output is correct
2 Correct 1893 ms 73516 KB Output is correct
3 Correct 3154 ms 100016 KB Output is correct
4 Correct 2516 ms 125708 KB Output is correct
5 Correct 2418 ms 98172 KB Output is correct
6 Correct 2449 ms 102180 KB Output is correct
7 Correct 4128 ms 118180 KB Output is correct
8 Correct 3454 ms 95124 KB Output is correct
9 Correct 2410 ms 125584 KB Output is correct
10 Correct 2394 ms 99436 KB Output is correct
11 Correct 2514 ms 93108 KB Output is correct
12 Correct 2673 ms 91592 KB Output is correct
13 Correct 1783 ms 90580 KB Output is correct
14 Correct 1826 ms 99692 KB Output is correct
15 Correct 1923 ms 97524 KB Output is correct
16 Correct 1929 ms 90612 KB Output is correct
17 Correct 2099 ms 91472 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 6 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 6 ms 7508 KB Output is correct
13 Correct 5 ms 7636 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 6 ms 7508 KB Output is correct
18 Correct 6 ms 7464 KB Output is correct
19 Correct 6 ms 7592 KB Output is correct
20 Correct 6 ms 7508 KB Output is correct
21 Correct 4 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 6 ms 7508 KB Output is correct
24 Correct 6 ms 7508 KB Output is correct
25 Correct 6 ms 7508 KB Output is correct
26 Correct 6 ms 7520 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7500 KB Output is correct
31 Correct 554 ms 27232 KB Output is correct
32 Correct 352 ms 22888 KB Output is correct
33 Correct 612 ms 31636 KB Output is correct
34 Correct 559 ms 31612 KB Output is correct
35 Correct 581 ms 31384 KB Output is correct
36 Correct 605 ms 31740 KB Output is correct
37 Correct 517 ms 31352 KB Output is correct
38 Correct 557 ms 31556 KB Output is correct
39 Correct 452 ms 29764 KB Output is correct
40 Correct 474 ms 31452 KB Output is correct
41 Correct 493 ms 29980 KB Output is correct
42 Correct 504 ms 30176 KB Output is correct
43 Correct 160 ms 17868 KB Output is correct
44 Correct 493 ms 29992 KB Output is correct
45 Correct 496 ms 31288 KB Output is correct
46 Correct 480 ms 30380 KB Output is correct
47 Correct 360 ms 30120 KB Output is correct
48 Correct 327 ms 27480 KB Output is correct
49 Correct 385 ms 30452 KB Output is correct
50 Correct 411 ms 31348 KB Output is correct
51 Correct 390 ms 30056 KB Output is correct
52 Correct 565 ms 36988 KB Output is correct
53 Correct 581 ms 36968 KB Output is correct
54 Correct 539 ms 32272 KB Output is correct
55 Correct 508 ms 32528 KB Output is correct
56 Correct 512 ms 33636 KB Output is correct
57 Correct 513 ms 30700 KB Output is correct
58 Correct 539 ms 32500 KB Output is correct
59 Correct 537 ms 33608 KB Output is correct
60 Correct 505 ms 30900 KB Output is correct
61 Correct 211 ms 31100 KB Output is correct
62 Correct 554 ms 36944 KB Output is correct
63 Correct 530 ms 33496 KB Output is correct
64 Correct 557 ms 32300 KB Output is correct
65 Correct 522 ms 30904 KB Output is correct
66 Correct 512 ms 30288 KB Output is correct
67 Correct 360 ms 28116 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 4 ms 7380 KB Output is correct
5 Correct 5 ms 7508 KB Output is correct
6 Correct 6 ms 7508 KB Output is correct
7 Correct 5 ms 7508 KB Output is correct
8 Correct 6 ms 7508 KB Output is correct
9 Correct 6 ms 7508 KB Output is correct
10 Correct 6 ms 7508 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 6 ms 7508 KB Output is correct
13 Correct 5 ms 7636 KB Output is correct
14 Correct 5 ms 7508 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 5 ms 7508 KB Output is correct
17 Correct 6 ms 7508 KB Output is correct
18 Correct 6 ms 7464 KB Output is correct
19 Correct 6 ms 7592 KB Output is correct
20 Correct 6 ms 7508 KB Output is correct
21 Correct 4 ms 7508 KB Output is correct
22 Correct 7 ms 7508 KB Output is correct
23 Correct 6 ms 7508 KB Output is correct
24 Correct 6 ms 7508 KB Output is correct
25 Correct 6 ms 7508 KB Output is correct
26 Correct 6 ms 7520 KB Output is correct
27 Correct 5 ms 7508 KB Output is correct
28 Correct 5 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7500 KB Output is correct
31 Correct 554 ms 27232 KB Output is correct
32 Correct 352 ms 22888 KB Output is correct
33 Correct 612 ms 31636 KB Output is correct
34 Correct 559 ms 31612 KB Output is correct
35 Correct 581 ms 31384 KB Output is correct
36 Correct 605 ms 31740 KB Output is correct
37 Correct 517 ms 31352 KB Output is correct
38 Correct 557 ms 31556 KB Output is correct
39 Correct 452 ms 29764 KB Output is correct
40 Correct 474 ms 31452 KB Output is correct
41 Correct 493 ms 29980 KB Output is correct
42 Correct 504 ms 30176 KB Output is correct
43 Correct 160 ms 17868 KB Output is correct
44 Correct 493 ms 29992 KB Output is correct
45 Correct 496 ms 31288 KB Output is correct
46 Correct 480 ms 30380 KB Output is correct
47 Correct 360 ms 30120 KB Output is correct
48 Correct 327 ms 27480 KB Output is correct
49 Correct 385 ms 30452 KB Output is correct
50 Correct 411 ms 31348 KB Output is correct
51 Correct 390 ms 30056 KB Output is correct
52 Correct 1147 ms 61632 KB Output is correct
53 Correct 1837 ms 49764 KB Output is correct
54 Correct 1353 ms 111988 KB Output is correct
55 Correct 1171 ms 67792 KB Output is correct
56 Correct 2583 ms 81040 KB Output is correct
57 Correct 2087 ms 53912 KB Output is correct
58 Correct 1259 ms 111984 KB Output is correct
59 Correct 1127 ms 67468 KB Output is correct
60 Correct 1134 ms 56592 KB Output is correct
61 Correct 1394 ms 48972 KB Output is correct
62 Correct 1222 ms 52312 KB Output is correct
63 Correct 1184 ms 48584 KB Output is correct
64 Correct 2581 ms 79192 KB Output is correct
65 Correct 1893 ms 73516 KB Output is correct
66 Correct 3154 ms 100016 KB Output is correct
67 Correct 2516 ms 125708 KB Output is correct
68 Correct 2418 ms 98172 KB Output is correct
69 Correct 2449 ms 102180 KB Output is correct
70 Correct 4128 ms 118180 KB Output is correct
71 Correct 3454 ms 95124 KB Output is correct
72 Correct 2410 ms 125584 KB Output is correct
73 Correct 2394 ms 99436 KB Output is correct
74 Correct 2514 ms 93108 KB Output is correct
75 Correct 2673 ms 91592 KB Output is correct
76 Correct 1783 ms 90580 KB Output is correct
77 Correct 1826 ms 99692 KB Output is correct
78 Correct 1923 ms 97524 KB Output is correct
79 Correct 1929 ms 90612 KB Output is correct
80 Correct 2099 ms 91472 KB Output is correct
81 Correct 565 ms 36988 KB Output is correct
82 Correct 581 ms 36968 KB Output is correct
83 Correct 539 ms 32272 KB Output is correct
84 Correct 508 ms 32528 KB Output is correct
85 Correct 512 ms 33636 KB Output is correct
86 Correct 513 ms 30700 KB Output is correct
87 Correct 539 ms 32500 KB Output is correct
88 Correct 537 ms 33608 KB Output is correct
89 Correct 505 ms 30900 KB Output is correct
90 Correct 211 ms 31100 KB Output is correct
91 Correct 554 ms 36944 KB Output is correct
92 Correct 530 ms 33496 KB Output is correct
93 Correct 557 ms 32300 KB Output is correct
94 Correct 522 ms 30904 KB Output is correct
95 Correct 512 ms 30288 KB Output is correct
96 Correct 360 ms 28116 KB Output is correct
97 Correct 4006 ms 175544 KB Output is correct
98 Correct 2295 ms 94152 KB Output is correct
99 Correct 4484 ms 121204 KB Output is correct
100 Correct 3918 ms 175708 KB Output is correct
101 Correct 3854 ms 129924 KB Output is correct
102 Correct 4303 ms 122944 KB Output is correct
103 Correct 3072 ms 120856 KB Output is correct
104 Correct 3285 ms 122076 KB Output is correct
105 Correct 2713 ms 118100 KB Output is correct
106 Correct 2794 ms 121500 KB Output is correct
107 Correct 3300 ms 130532 KB Output is correct
108 Correct 3338 ms 160996 KB Output is correct
109 Correct 3321 ms 125384 KB Output is correct
110 Correct 3541 ms 131756 KB Output is correct
111 Correct 3668 ms 144740 KB Output is correct
112 Correct 3417 ms 124884 KB Output is correct
113 Correct 1086 ms 124500 KB Output is correct
114 Correct 3638 ms 175536 KB Output is correct
115 Correct 3824 ms 160248 KB Output is correct
116 Correct 3799 ms 129772 KB Output is correct
117 Correct 3661 ms 122912 KB Output is correct
118 Correct 3548 ms 119540 KB Output is correct
119 Correct 2386 ms 108980 KB Output is correct
120 Correct 1709 ms 105680 KB Output is correct
121 Correct 1913 ms 114300 KB Output is correct
122 Correct 1812 ms 105884 KB Output is correct
123 Correct 2123 ms 117144 KB Output is correct
124 Correct 2354 ms 120876 KB Output is correct
125 Correct 2223 ms 112576 KB Output is correct
126 Correct 2395 ms 121512 KB Output is correct