oj.uz

Submission #659017

# Submission time Handle Problem Language Result Execution time Memory
659017 2022-11-15T19:32:00 Z 600Mihnea New Home (APIO18_new_home) C++17
100 / 100
 3908 ms 160020 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) {
      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) {
    upd(1, 0, nn - 1, i, x);
  }
  int getmin(int l, int r) {
    if (l > r) {
      return (int) 1e9 + 7;
    }
    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) {
    return stores[i].first_time;
  } else {
    i *= -1;
    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) {
  if (first_time > last_time) {
    return;
  }
  segments.push_back({first_time, last_time, stores[i].x, stores[j].x});
}

vector<RelaxSegment> relaxSegments;

int getTimeOfRelaxSegmentEvent(int i) {
  if (i >= 1) {
    i--;
    return relaxSegments[i].first_time;
  } else {
    i *= -1;
    i--;
    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) {
            positions.insert({i});


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

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

            sinceWhen.erase({ant->i, nxt->i});
            sinceWhen[{ant->i, it->i}] = current_time;
            sinceWhen[{it->i, nxt->i}] = current_time;
          } else {
            i *= -1;

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

            sinceWhen[{ant->i, nxt->i}] = current_time;


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

            addSegment(sinceWhen[{it->i, nxt->i}], current_time - 1, 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;
      });
      for (auto &iq : ord) {
        while (p < (int) relaxSegmentEvents.size() && getTimeOfRelaxSegmentEvent(relaxSegmentEvents[p]) <= queries[iq].t) {
          int i = relaxSegmentEvents[p++];

          if (i >= 1) {
            i--;
            tree.upd(i, relaxSegments[i].x);
          } else {
            i *= -1;
            i--;
            tree.upd(i, (int) 1e9 + 7);
          }
        }
        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";
    }
  }
  return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 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 7548 KB Output is correct
7 Correct 9 ms 7508 KB Output is correct
8 Correct 6 ms 7544 KB Output is correct
9 Correct 7 ms 7556 KB Output is correct
10 Correct 6 ms 7540 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7520 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7504 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 6 ms 7516 KB Output is correct
17 Correct 6 ms 7568 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 6 ms 7508 KB Output is correct
20 Correct 6 ms 7452 KB Output is correct
21 Correct 6 ms 7548 KB Output is correct
22 Correct 6 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 7 ms 7564 KB Output is correct
27 Correct 6 ms 7520 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7508 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 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 7548 KB Output is correct
7 Correct 9 ms 7508 KB Output is correct
8 Correct 6 ms 7544 KB Output is correct
9 Correct 7 ms 7556 KB Output is correct
10 Correct 6 ms 7540 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7520 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7504 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 6 ms 7516 KB Output is correct
17 Correct 6 ms 7568 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 6 ms 7508 KB Output is correct
20 Correct 6 ms 7452 KB Output is correct
21 Correct 6 ms 7548 KB Output is correct
22 Correct 6 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 7 ms 7564 KB Output is correct
27 Correct 6 ms 7520 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7508 KB Output is correct
31 Correct 516 ms 27376 KB Output is correct
32 Correct 311 ms 22048 KB Output is correct
33 Correct 566 ms 28748 KB Output is correct
34 Correct 521 ms 28696 KB Output is correct
35 Correct 536 ms 28384 KB Output is correct
36 Correct 557 ms 28988 KB Output is correct
37 Correct 464 ms 28600 KB Output is correct
38 Correct 489 ms 28656 KB Output is correct
39 Correct 389 ms 26896 KB Output is correct
40 Correct 405 ms 28588 KB Output is correct
41 Correct 450 ms 26932 KB Output is correct
42 Correct 479 ms 27340 KB Output is correct
43 Correct 123 ms 15524 KB Output is correct
44 Correct 443 ms 27252 KB Output is correct
45 Correct 440 ms 28368 KB Output is correct
46 Correct 416 ms 27528 KB Output is correct
47 Correct 299 ms 27248 KB Output is correct
48 Correct 285 ms 24808 KB Output is correct
49 Correct 330 ms 27740 KB Output is correct
50 Correct 368 ms 28552 KB Output is correct
51 Correct 339 ms 27288 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1033 ms 61616 KB Output is correct
2 Correct 1539 ms 49628 KB Output is correct
3 Correct 1097 ms 112052 KB Output is correct
4 Correct 1058 ms 67792 KB Output is correct
5 Correct 2326 ms 80840 KB Output is correct
6 Correct 1826 ms 53732 KB Output is correct
7 Correct 1025 ms 111952 KB Output is correct
8 Correct 1014 ms 67468 KB Output is correct
9 Correct 1002 ms 56476 KB Output is correct
10 Correct 1216 ms 48988 KB Output is correct
11 Correct 1047 ms 52236 KB Output is correct
12 Correct 985 ms 48456 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2296 ms 79252 KB Output is correct
2 Correct 1693 ms 69388 KB Output is correct
3 Correct 2929 ms 87672 KB Output is correct
4 Correct 2210 ms 111992 KB Output is correct
5 Correct 2188 ms 84756 KB Output is correct
6 Correct 2209 ms 88864 KB Output is correct
7 Correct 3811 ms 106096 KB Output is correct
8 Correct 2961 ms 83076 KB Output is correct
9 Correct 2031 ms 112040 KB Output is correct
10 Correct 2096 ms 85940 KB Output is correct
11 Correct 2139 ms 80020 KB Output is correct
12 Correct 2337 ms 78820 KB Output is correct
13 Correct 1525 ms 78760 KB Output is correct
14 Correct 1531 ms 87732 KB Output is correct
15 Correct 1608 ms 85380 KB Output is correct
16 Correct 1638 ms 78060 KB Output is correct
17 Correct 1767 ms 79620 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 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 7548 KB Output is correct
7 Correct 9 ms 7508 KB Output is correct
8 Correct 6 ms 7544 KB Output is correct
9 Correct 7 ms 7556 KB Output is correct
10 Correct 6 ms 7540 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7520 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7504 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 6 ms 7516 KB Output is correct
17 Correct 6 ms 7568 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 6 ms 7508 KB Output is correct
20 Correct 6 ms 7452 KB Output is correct
21 Correct 6 ms 7548 KB Output is correct
22 Correct 6 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 7 ms 7564 KB Output is correct
27 Correct 6 ms 7520 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7508 KB Output is correct
31 Correct 516 ms 27376 KB Output is correct
32 Correct 311 ms 22048 KB Output is correct
33 Correct 566 ms 28748 KB Output is correct
34 Correct 521 ms 28696 KB Output is correct
35 Correct 536 ms 28384 KB Output is correct
36 Correct 557 ms 28988 KB Output is correct
37 Correct 464 ms 28600 KB Output is correct
38 Correct 489 ms 28656 KB Output is correct
39 Correct 389 ms 26896 KB Output is correct
40 Correct 405 ms 28588 KB Output is correct
41 Correct 450 ms 26932 KB Output is correct
42 Correct 479 ms 27340 KB Output is correct
43 Correct 123 ms 15524 KB Output is correct
44 Correct 443 ms 27252 KB Output is correct
45 Correct 440 ms 28368 KB Output is correct
46 Correct 416 ms 27528 KB Output is correct
47 Correct 299 ms 27248 KB Output is correct
48 Correct 285 ms 24808 KB Output is correct
49 Correct 330 ms 27740 KB Output is correct
50 Correct 368 ms 28552 KB Output is correct
51 Correct 339 ms 27288 KB Output is correct
52 Correct 480 ms 33916 KB Output is correct
53 Correct 471 ms 33984 KB Output is correct
54 Correct 489 ms 29312 KB Output is correct
55 Correct 433 ms 29444 KB Output is correct
56 Correct 444 ms 30608 KB Output is correct
57 Correct 454 ms 27856 KB Output is correct
58 Correct 462 ms 29380 KB Output is correct
59 Correct 459 ms 30520 KB Output is correct
60 Correct 450 ms 27908 KB Output is correct
61 Correct 170 ms 28780 KB Output is correct
62 Correct 437 ms 33876 KB Output is correct
63 Correct 461 ms 30372 KB Output is correct
64 Correct 486 ms 29164 KB Output is correct
65 Correct 503 ms 27872 KB Output is correct
66 Correct 457 ms 27300 KB Output is correct
67 Correct 314 ms 26832 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7408 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 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 7548 KB Output is correct
7 Correct 9 ms 7508 KB Output is correct
8 Correct 6 ms 7544 KB Output is correct
9 Correct 7 ms 7556 KB Output is correct
10 Correct 6 ms 7540 KB Output is correct
11 Correct 6 ms 7508 KB Output is correct
12 Correct 7 ms 7520 KB Output is correct
13 Correct 5 ms 7508 KB Output is correct
14 Correct 5 ms 7504 KB Output is correct
15 Correct 6 ms 7508 KB Output is correct
16 Correct 6 ms 7516 KB Output is correct
17 Correct 6 ms 7568 KB Output is correct
18 Correct 6 ms 7508 KB Output is correct
19 Correct 6 ms 7508 KB Output is correct
20 Correct 6 ms 7452 KB Output is correct
21 Correct 6 ms 7548 KB Output is correct
22 Correct 6 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 7 ms 7564 KB Output is correct
27 Correct 6 ms 7520 KB Output is correct
28 Correct 6 ms 7508 KB Output is correct
29 Correct 6 ms 7508 KB Output is correct
30 Correct 5 ms 7508 KB Output is correct
31 Correct 516 ms 27376 KB Output is correct
32 Correct 311 ms 22048 KB Output is correct
33 Correct 566 ms 28748 KB Output is correct
34 Correct 521 ms 28696 KB Output is correct
35 Correct 536 ms 28384 KB Output is correct
36 Correct 557 ms 28988 KB Output is correct
37 Correct 464 ms 28600 KB Output is correct
38 Correct 489 ms 28656 KB Output is correct
39 Correct 389 ms 26896 KB Output is correct
40 Correct 405 ms 28588 KB Output is correct
41 Correct 450 ms 26932 KB Output is correct
42 Correct 479 ms 27340 KB Output is correct
43 Correct 123 ms 15524 KB Output is correct
44 Correct 443 ms 27252 KB Output is correct
45 Correct 440 ms 28368 KB Output is correct
46 Correct 416 ms 27528 KB Output is correct
47 Correct 299 ms 27248 KB Output is correct
48 Correct 285 ms 24808 KB Output is correct
49 Correct 330 ms 27740 KB Output is correct
50 Correct 368 ms 28552 KB Output is correct
51 Correct 339 ms 27288 KB Output is correct
52 Correct 1033 ms 61616 KB Output is correct
53 Correct 1539 ms 49628 KB Output is correct
54 Correct 1097 ms 112052 KB Output is correct
55 Correct 1058 ms 67792 KB Output is correct
56 Correct 2326 ms 80840 KB Output is correct
57 Correct 1826 ms 53732 KB Output is correct
58 Correct 1025 ms 111952 KB Output is correct
59 Correct 1014 ms 67468 KB Output is correct
60 Correct 1002 ms 56476 KB Output is correct
61 Correct 1216 ms 48988 KB Output is correct
62 Correct 1047 ms 52236 KB Output is correct
63 Correct 985 ms 48456 KB Output is correct
64 Correct 2296 ms 79252 KB Output is correct
65 Correct 1693 ms 69388 KB Output is correct
66 Correct 2929 ms 87672 KB Output is correct
67 Correct 2210 ms 111992 KB Output is correct
68 Correct 2188 ms 84756 KB Output is correct
69 Correct 2209 ms 88864 KB Output is correct
70 Correct 3811 ms 106096 KB Output is correct
71 Correct 2961 ms 83076 KB Output is correct
72 Correct 2031 ms 112040 KB Output is correct
73 Correct 2096 ms 85940 KB Output is correct
74 Correct 2139 ms 80020 KB Output is correct
75 Correct 2337 ms 78820 KB Output is correct
76 Correct 1525 ms 78760 KB Output is correct
77 Correct 1531 ms 87732 KB Output is correct
78 Correct 1608 ms 85380 KB Output is correct
79 Correct 1638 ms 78060 KB Output is correct
80 Correct 1767 ms 79620 KB Output is correct
81 Correct 480 ms 33916 KB Output is correct
82 Correct 471 ms 33984 KB Output is correct
83 Correct 489 ms 29312 KB Output is correct
84 Correct 433 ms 29444 KB Output is correct
85 Correct 444 ms 30608 KB Output is correct
86 Correct 454 ms 27856 KB Output is correct
87 Correct 462 ms 29380 KB Output is correct
88 Correct 459 ms 30520 KB Output is correct
89 Correct 450 ms 27908 KB Output is correct
90 Correct 170 ms 28780 KB Output is correct
91 Correct 437 ms 33876 KB Output is correct
92 Correct 461 ms 30372 KB Output is correct
93 Correct 486 ms 29164 KB Output is correct
94 Correct 503 ms 27872 KB Output is correct
95 Correct 457 ms 27300 KB Output is correct
96 Correct 314 ms 26832 KB Output is correct
97 Correct 3431 ms 159956 KB Output is correct
98 Correct 2012 ms 89504 KB Output is correct
99 Correct 3872 ms 106928 KB Output is correct
100 Correct 3379 ms 160020 KB Output is correct
101 Correct 3348 ms 114516 KB Output is correct
102 Correct 3908 ms 108804 KB Output is correct
103 Correct 2715 ms 106300 KB Output is correct
104 Correct 2873 ms 107700 KB Output is correct
105 Correct 2353 ms 103816 KB Output is correct
106 Correct 2437 ms 107208 KB Output is correct
107 Correct 3008 ms 115056 KB Output is correct
108 Correct 3048 ms 145552 KB Output is correct
109 Correct 2956 ms 110052 KB Output is correct
110 Correct 3193 ms 116324 KB Output is correct
111 Correct 3197 ms 129304 KB Output is correct
112 Correct 3137 ms 109544 KB Output is correct
113 Correct 835 ms 111860 KB Output is correct
114 Correct 3136 ms 160000 KB Output is correct
115 Correct 3356 ms 144752 KB Output is correct
116 Correct 3206 ms 114216 KB Output is correct
117 Correct 3214 ms 107716 KB Output is correct
118 Correct 3147 ms 104692 KB Output is correct
119 Correct 2104 ms 102656 KB Output is correct
120 Correct 1437 ms 92172 KB Output is correct
121 Correct 1636 ms 100456 KB Output is correct
122 Correct 1547 ms 92120 KB Output is correct
123 Correct 1840 ms 102964 KB Output is correct
124 Correct 2045 ms 105996 KB Output is correct
125 Correct 1913 ms 98424 KB Output is correct
126 Correct 2079 ms 106784 KB Output is correct