oj.uz

Submission #988050

# Submission time Handle Problem Language Result Execution time Memory
988050 2024-05-24T00:52:02 Z rxlfd314 Escape Route 2 (JOI24_escape2) C++17
100 / 100
 1022 ms 73292 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)

constexpr int mxN = 100000;
int N, T, Q, L[3*mxN], R[3*mxN], same[3*mxN], uf[mxN], lft[mxN], rht[mxN];
vt<ari2> ltr[mxN], rtl[mxN], all_flights;
set<ari2> adj[mxN*2];
vt<int> nodes[mxN];
ll lz[mxN], ans[3*mxN], tot[mxN];

int find(int i) {
  return uf[i] < 0 ? i : uf[i] = find(uf[i]);
}

void unite(int a, int b) {
  a = find(a), b = find(b);
  if (a == b)
    assert(false);
  if (uf[a] > uf[b])
    swap(a, b);
  uf[a] += uf[b];
  uf[b] = a;
  for (int j : nodes[b]) {
    nodes[a].push_back(j);
    tot[j] += lz[b] - lz[a];
  }
  nodes[b].clear();
};

signed main() {
#ifndef DEBUG
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
#endif
  cin >> N >> T;
  FOR(i, 0, N-2) {
    int m;
    cin >> m;
    vt<ari2> v(m);
    for (auto &[a, b] : v)
      cin >> a >> b;
    sort(all(v), [&](const ari2 &a, const ari2 &b) {
      return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });
    vt<ari2> nf;
    for (auto &[a, b] : v) {
      while (size(nf) && nf.back()[1] >= b)
        nf.pop_back();
      nf.push_back({a, b});
    }
    lft[i] = size(all_flights);
    for (auto &vv : nf)
      all_flights.push_back(vv);
    rht[i] = size(all_flights) - 1;
  }

  cin >> Q;
  iota(same, same+Q, 0);
  FOR(i, 0, Q-1) {
    int &a = L[i], &b = R[i];
    cin >> a >> b, a--, b--;
    auto it = adj[a].lower_bound({b+N, 0});
    if (it != end(adj[a]) && (*it)[0] == b+N) {
      same[i] = (*it)[1];
      continue;
    }
    adj[a].insert({b+N, i});
    adj[b+N].insert({a, i});
  }
  /* generate queries */ {
    multiset<ari2> ms;
    FOR(i, 0, 2*N-1)
      if (size(adj[i]))
        ms.insert({size(adj[i]), i});
    while (size(ms)) {
      auto [d, i] = *begin(ms);
      ms.erase(begin(ms));
      for (auto [j, qi] : adj[i]) {
        ms.erase(ms.find({size(adj[j]), j}));
        adj[j].erase(adj[j].find({i, qi}));
        if (size(adj[j]))
          ms.insert({size(adj[j]), j});
        if (i < j)
          ltr[j-N].push_back({i, qi});
        else
          rtl[N-1-j].push_back({N-1-i+N, qi});
      }
    }
  }
  
  fill(ans, ans+Q, LLONG_MAX);
  vt<bool> marked(Q);
  FOR(_, 1, 2) {
    memset(uf, -1, sizeof(uf));
    memset(lz, 0, sizeof(lz));
    memset(tot, 0, sizeof(tot));
    FOR(i, 0, size(all_flights)-1)
      nodes[i].push_back(i);
    FOR(ii, 0, N-2) {
      if (ii > 0) {
        int j = lft[ii];
        FOR(i, lft[ii-1], rht[ii-1]) {
          auto [a, b] = all_flights[i];
          for (; j <= rht[ii] && all_flights[j][0] < b; j++);
          int k = j > rht[ii] ? lft[ii] : j;
          auto [c, d] = all_flights[k];
          lz[find(i)] += ((c - b) % T + T) % T;
          unite(i, k);
        }
      }
      FOR(i, lft[ii], rht[ii])
        lz[find(i)] += all_flights[i][1] - all_flights[i][0];
      for (auto [l, qi] : ltr[ii+1]) {
        marked[qi] = true;
        FOR(j, lft[l], rht[l])
          ans[qi] = min(ans[qi], lz[find(j)] + tot[j]);
      }
    }
    if (_ == 2)
      break;
    for (auto &[a, b] : all_flights) {
      a *= -1, b *= -1;
      swap(a, b);
    }
    FOR(i, 0, size(all_flights)-1)
      nodes[i].clear();
    reverse(all(all_flights));
    for (int i = 0, j = N-2; i <= j; i++, j--) {
      lft[i] = size(all_flights) - 1 - lft[i];
      rht[i] = size(all_flights) - 1 - rht[i];
      if (i < j) {
        lft[j] = size(all_flights) - 1 - lft[j];
        rht[j] = size(all_flights) - 1 - rht[j];
        swap(lft[i], lft[j]);
        swap(rht[i], rht[j]);
        swap(lft[i], rht[i]);
      }
      swap(lft[j], rht[j]);
    }
    FOR(i, 0, N-1)
      swap(ltr[i], rtl[i]);
  }

  FOR(i, 0, Q-1) {
    cout << ans[same[i]] << '\n';
  }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18776 KB Output is correct
2 Correct 56 ms 28880 KB Output is correct
3 Correct 393 ms 51796 KB Output is correct
4 Correct 585 ms 61876 KB Output is correct
5 Correct 450 ms 52280 KB Output is correct
6 Correct 715 ms 61092 KB Output is correct
7 Correct 761 ms 61012 KB Output is correct
8 Correct 424 ms 50784 KB Output is correct
9 Correct 702 ms 61200 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18776 KB Output is correct
2 Correct 56 ms 28880 KB Output is correct
3 Correct 393 ms 51796 KB Output is correct
4 Correct 585 ms 61876 KB Output is correct
5 Correct 450 ms 52280 KB Output is correct
6 Correct 715 ms 61092 KB Output is correct
7 Correct 761 ms 61012 KB Output is correct
8 Correct 424 ms 50784 KB Output is correct
9 Correct 702 ms 61200 KB Output is correct
10 Correct 10 ms 18780 KB Output is correct
11 Correct 185 ms 39248 KB Output is correct
12 Correct 181 ms 38916 KB Output is correct
13 Correct 169 ms 38992 KB Output is correct
14 Correct 173 ms 38740 KB Output is correct
15 Correct 332 ms 50160 KB Output is correct
16 Correct 52 ms 28756 KB Output is correct
17 Correct 549 ms 59556 KB Output is correct
18 Correct 382 ms 51276 KB Output is correct
19 Correct 631 ms 58692 KB Output is correct
20 Correct 369 ms 48724 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18776 KB Output is correct
2 Correct 56 ms 28880 KB Output is correct
3 Correct 393 ms 51796 KB Output is correct
4 Correct 585 ms 61876 KB Output is correct
5 Correct 450 ms 52280 KB Output is correct
6 Correct 715 ms 61092 KB Output is correct
7 Correct 761 ms 61012 KB Output is correct
8 Correct 424 ms 50784 KB Output is correct
9 Correct 702 ms 61200 KB Output is correct
10 Correct 549 ms 54224 KB Output is correct
11 Correct 965 ms 69784 KB Output is correct
12 Correct 990 ms 69808 KB Output is correct
13 Correct 765 ms 62728 KB Output is correct
14 Correct 975 ms 73292 KB Output is correct
15 Correct 950 ms 73148 KB Output is correct
16 Correct 673 ms 57392 KB Output is correct
17 Correct 1022 ms 73152 KB Output is correct
18 Correct 212 ms 39376 KB Output is correct
19 Correct 208 ms 38064 KB Output is correct
20 Correct 215 ms 40396 KB Output is correct
21 Correct 226 ms 40560 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18776 KB Output is correct
2 Correct 56 ms 28880 KB Output is correct
3 Correct 393 ms 51796 KB Output is correct
4 Correct 585 ms 61876 KB Output is correct
5 Correct 450 ms 52280 KB Output is correct
6 Correct 715 ms 61092 KB Output is correct
7 Correct 761 ms 61012 KB Output is correct
8 Correct 424 ms 50784 KB Output is correct
9 Correct 702 ms 61200 KB Output is correct
10 Correct 10 ms 18780 KB Output is correct
11 Correct 185 ms 39248 KB Output is correct
12 Correct 181 ms 38916 KB Output is correct
13 Correct 169 ms 38992 KB Output is correct
14 Correct 173 ms 38740 KB Output is correct
15 Correct 332 ms 50160 KB Output is correct
16 Correct 52 ms 28756 KB Output is correct
17 Correct 549 ms 59556 KB Output is correct
18 Correct 382 ms 51276 KB Output is correct
19 Correct 631 ms 58692 KB Output is correct
20 Correct 369 ms 48724 KB Output is correct
21 Correct 549 ms 54224 KB Output is correct
22 Correct 965 ms 69784 KB Output is correct
23 Correct 990 ms 69808 KB Output is correct
24 Correct 765 ms 62728 KB Output is correct
25 Correct 975 ms 73292 KB Output is correct
26 Correct 950 ms 73148 KB Output is correct
27 Correct 673 ms 57392 KB Output is correct
28 Correct 1022 ms 73152 KB Output is correct
29 Correct 212 ms 39376 KB Output is correct
30 Correct 208 ms 38064 KB Output is correct
31 Correct 215 ms 40396 KB Output is correct
32 Correct 226 ms 40560 KB Output is correct
33 Correct 952 ms 67780 KB Output is correct
34 Correct 901 ms 67808 KB Output is correct
35 Correct 936 ms 67300 KB Output is correct
36 Correct 954 ms 67016 KB Output is correct
37 Correct 978 ms 67908 KB Output is correct
38 Correct 591 ms 55500 KB Output is correct
39 Correct 739 ms 62984 KB Output is correct
40 Correct 569 ms 59856 KB Output is correct
41 Correct 752 ms 61820 KB Output is correct
42 Correct 965 ms 70420 KB Output is correct
43 Correct 772 ms 59852 KB Output is correct
44 Correct 940 ms 67628 KB Output is correct
45 Correct 220 ms 38076 KB Output is correct
46 Correct 188 ms 36560 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 18776 KB Output is correct
2 Correct 11 ms 18780 KB Output is correct
3 Correct 113 ms 31112 KB Output is correct
4 Correct 132 ms 30916 KB Output is correct
5 Correct 119 ms 30944 KB Output is correct
6 Correct 115 ms 30912 KB Output is correct
7 Correct 114 ms 30912 KB Output is correct
8 Correct 108 ms 30408 KB Output is correct
9 Correct 117 ms 31432 KB Output is correct
10 Correct 45 ms 25032 KB Output is correct
11 Correct 228 ms 39360 KB Output is correct
12 Correct 197 ms 38096 KB Output is correct
13 Correct 261 ms 36228 KB Output is correct
14 Correct 126 ms 34112 KB Output is correct
15 Correct 109 ms 33032 KB Output is correct
16 Correct 174 ms 37084 KB Output is correct
17 Correct 181 ms 36204 KB Output is correct
18 Correct 120 ms 33408 KB Output is correct
19 Correct 113 ms 33276 KB Output is correct
20 Correct 70 ms 30716 KB Output is correct
21 Correct 113 ms 33240 KB Output is correct
22 Correct 79 ms 31436 KB Output is correct
23 Correct 116 ms 33992 KB Output is correct
24 Correct 116 ms 33496 KB Output is correct
25 Correct 69 ms 30324 KB Output is correct
26 Correct 203 ms 35972 KB Output is correct
27 Correct 203 ms 38084 KB Output is correct
28 Correct 234 ms 40396 KB Output is correct
29 Correct 214 ms 40508 KB Output is correct
30 Correct 156 ms 34224 KB Output is correct
31 Correct 48 ms 23844 KB Output is correct
32 Correct 142 ms 34268 KB Output is correct
33 Correct 64 ms 25304 KB Output is correct
34 Correct 108 ms 30288 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 18776 KB Output is correct
2 Correct 56 ms 28880 KB Output is correct
3 Correct 393 ms 51796 KB Output is correct
4 Correct 585 ms 61876 KB Output is correct
5 Correct 450 ms 52280 KB Output is correct
6 Correct 715 ms 61092 KB Output is correct
7 Correct 761 ms 61012 KB Output is correct
8 Correct 424 ms 50784 KB Output is correct
9 Correct 702 ms 61200 KB Output is correct
10 Correct 10 ms 18780 KB Output is correct
11 Correct 185 ms 39248 KB Output is correct
12 Correct 181 ms 38916 KB Output is correct
13 Correct 169 ms 38992 KB Output is correct
14 Correct 173 ms 38740 KB Output is correct
15 Correct 332 ms 50160 KB Output is correct
16 Correct 52 ms 28756 KB Output is correct
17 Correct 549 ms 59556 KB Output is correct
18 Correct 382 ms 51276 KB Output is correct
19 Correct 631 ms 58692 KB Output is correct
20 Correct 369 ms 48724 KB Output is correct
21 Correct 549 ms 54224 KB Output is correct
22 Correct 965 ms 69784 KB Output is correct
23 Correct 990 ms 69808 KB Output is correct
24 Correct 765 ms 62728 KB Output is correct
25 Correct 975 ms 73292 KB Output is correct
26 Correct 950 ms 73148 KB Output is correct
27 Correct 673 ms 57392 KB Output is correct
28 Correct 1022 ms 73152 KB Output is correct
29 Correct 212 ms 39376 KB Output is correct
30 Correct 208 ms 38064 KB Output is correct
31 Correct 215 ms 40396 KB Output is correct
32 Correct 226 ms 40560 KB Output is correct
33 Correct 952 ms 67780 KB Output is correct
34 Correct 901 ms 67808 KB Output is correct
35 Correct 936 ms 67300 KB Output is correct
36 Correct 954 ms 67016 KB Output is correct
37 Correct 978 ms 67908 KB Output is correct
38 Correct 591 ms 55500 KB Output is correct
39 Correct 739 ms 62984 KB Output is correct
40 Correct 569 ms 59856 KB Output is correct
41 Correct 752 ms 61820 KB Output is correct
42 Correct 965 ms 70420 KB Output is correct
43 Correct 772 ms 59852 KB Output is correct
44 Correct 940 ms 67628 KB Output is correct
45 Correct 220 ms 38076 KB Output is correct
46 Correct 188 ms 36560 KB Output is correct
47 Correct 9 ms 18776 KB Output is correct
48 Correct 11 ms 18780 KB Output is correct
49 Correct 113 ms 31112 KB Output is correct
50 Correct 132 ms 30916 KB Output is correct
51 Correct 119 ms 30944 KB Output is correct
52 Correct 115 ms 30912 KB Output is correct
53 Correct 114 ms 30912 KB Output is correct
54 Correct 108 ms 30408 KB Output is correct
55 Correct 117 ms 31432 KB Output is correct
56 Correct 45 ms 25032 KB Output is correct
57 Correct 228 ms 39360 KB Output is correct
58 Correct 197 ms 38096 KB Output is correct
59 Correct 261 ms 36228 KB Output is correct
60 Correct 126 ms 34112 KB Output is correct
61 Correct 109 ms 33032 KB Output is correct
62 Correct 174 ms 37084 KB Output is correct
63 Correct 181 ms 36204 KB Output is correct
64 Correct 120 ms 33408 KB Output is correct
65 Correct 113 ms 33276 KB Output is correct
66 Correct 70 ms 30716 KB Output is correct
67 Correct 113 ms 33240 KB Output is correct
68 Correct 79 ms 31436 KB Output is correct
69 Correct 116 ms 33992 KB Output is correct
70 Correct 116 ms 33496 KB Output is correct
71 Correct 69 ms 30324 KB Output is correct
72 Correct 203 ms 35972 KB Output is correct
73 Correct 203 ms 38084 KB Output is correct
74 Correct 234 ms 40396 KB Output is correct
75 Correct 214 ms 40508 KB Output is correct
76 Correct 156 ms 34224 KB Output is correct
77 Correct 48 ms 23844 KB Output is correct
78 Correct 142 ms 34268 KB Output is correct
79 Correct 64 ms 25304 KB Output is correct
80 Correct 108 ms 30288 KB Output is correct
81 Correct 391 ms 49320 KB Output is correct
82 Correct 372 ms 49204 KB Output is correct
83 Correct 367 ms 49044 KB Output is correct
84 Correct 445 ms 49044 KB Output is correct
85 Correct 356 ms 49148 KB Output is correct
86 Correct 320 ms 50064 KB Output is correct
87 Correct 430 ms 50188 KB Output is correct
88 Correct 735 ms 64732 KB Output is correct
89 Correct 600 ms 57632 KB Output is correct
90 Correct 522 ms 58532 KB Output is correct
91 Correct 76 ms 30908 KB Output is correct
92 Correct 350 ms 51556 KB Output is correct
93 Correct 335 ms 49732 KB Output is correct
94 Correct 656 ms 69080 KB Output is correct
95 Correct 724 ms 62788 KB Output is correct
96 Correct 336 ms 51696 KB Output is correct
97 Correct 251 ms 44996 KB Output is correct
98 Correct 128 ms 40828 KB Output is correct
99 Correct 344 ms 51664 KB Output is correct
100 Correct 146 ms 41412 KB Output is correct
101 Correct 401 ms 50632 KB Output is correct
102 Correct 304 ms 48184 KB Output is correct
103 Correct 143 ms 40868 KB Output is correct
104 Correct 587 ms 55168 KB Output is correct
105 Correct 728 ms 57592 KB Output is correct
106 Correct 119 ms 28008 KB Output is correct
107 Correct 765 ms 59824 KB Output is correct
108 Correct 171 ms 31908 KB Output is correct
109 Correct 295 ms 40768 KB Output is correct