oj.uz

Submission #301945

# Submission time Handle Problem Language Result Execution time Memory
301945 2020-09-18T10:25:02 Z rama_pang Comparing Plants (IOI20_plants) C++14
100 / 100
 3353 ms 79332 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

class PotentialMaximum {
 public:
  PotentialMaximum() {}
  PotentialMaximum(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
    Build(1, 0, n - 1, r);
  }

  void UpdateIndeg(int x, int z = 1) {
    int l = x + 1;
    int r = x + k - 1;
    while (l >= n) {
      l -= n;
      r -= n;
    }
    if (n <= r) {
      Update(1, 0, n - 1, l, n - 1, 0, z);
      Update(1, 0, n - 1, 0, r - n, 0, z);
    } else {
      Update(1, 0, n - 1, l, r, 0, z);
    }
  }

  void UpdateRank(int x, int z) {
    int l = x - k + 1;
    int r = x - 1;
    while (l < 0) {
      l += n, r += n;
    }
    if (n <= r) {
      Update(1, 0, n - 1, l, n - 1, z, 0);
      Update(1, 0, n - 1, 0, r - n, z, 0);
    } else {
      Update(1, 0, n - 1, l, r, z, 0);
    }
  }

  void Delete(int x) {
    UpdateRank(x, -1);
    UpdateIndeg(x, -1);
    Update(1, 0, n - 1, x, x, 1e9, 1e9);
  }

  int Query() {
    return tree[1].id;
  }

 private:
  struct Node {
    int id;
    int rank;
    int indeg;
    int lazyrank;
    int lazyindeg;
  };

  int n, k;
  vector<Node> tree;

  void Apply(int u, int r, int d) {
    tree[u].rank += r;
    tree[u].lazyrank += r;
    tree[u].indeg += d;
    tree[u].lazyindeg += d;
  }

  void Push(int u, int lc, int rc) {
    Apply(lc, tree[u].lazyrank, tree[u].lazyindeg);
    Apply(rc, tree[u].lazyrank, tree[u].lazyindeg);
    tree[u].lazyrank = 0;
    tree[u].lazyindeg = 0;
  }

  void Pull(int u, int lc, int rc) {
    if (tree[lc].rank != tree[rc].rank) {
      if (tree[lc].rank < tree[rc].rank) {
        tree[u] = tree[lc];
      } else {
        tree[u] = tree[rc];
      }
    } else {
      if (tree[lc].indeg < tree[rc].indeg) {
        tree[u] = tree[lc];
      } else {
        tree[u] = tree[rc];
      }
    }
    tree[u].lazyrank = 0;
    tree[u].lazyindeg = 0;
  }

  void Build(int u, int tl, int tr, const vector<int> &r) {
    if (tl == tr) {
      tree[u].id = tl;
      tree[u].rank = r[tl];
      tree[u].indeg = 0;
      tree[u].lazyrank = 0;
      tree[u].lazyindeg = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Build(lc, tl, md, r);
    Build(rc, md + 1, tr, r);
    Pull(u, lc, rc);
  }

  void Update(int u, int tl, int tr, int l, int r, int rank, int indeg) {
    if (l > tr || tl > r || tl > tr || l > r) {
      return;
    }
    if (l <= tl && tr <= r) {
      return Apply(u, rank, indeg);
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Push(u, lc, rc);
    Update(lc, tl, md, l, r, rank, indeg);
    Update(rc, md + 1, tr, l, r, rank, indeg);
    Pull(u, lc, rc);    
  }
};

class Relax {
 public:
  Relax() {}
  Relax(int n, int k, vector<int> r) : n(n), k(k), tree(2 * n) {
    Build(1, 0, n - 1, r);
  }

  void Update(int x) {
    int l = x - k + 1;
    int r = x - 1;
    while (l < 0) {
      l += n, r += n;
    }
    if (n <= r) {
      Update(1, 0, n - 1, l, n - 1, -1);
      Update(1, 0, n - 1, 0, r - n, -1);
    } else {
      Update(1, 0, n - 1, l, r, -1);
    }
  }

  void Delete(int x) {
    Update(1, 0, n - 1, x, x, 1e9);
  }

  pair<int, int> Query(int x) {
    int l = x - k + 1;
    int r = x - 1;
    while (l < 0) {
      l += n, r += n;
    }
    Node res;
    if (n <= r) {
      auto ll = Query(1, 0, n - 1, l, n - 1);
      auto rr = Query(1, 0, n - 1, 0, r - n);
      if (ll.rank < rr.rank) {
        res = ll;
      } else {
        res = rr;
      }
    } else {
      res = Query(1, 0, n - 1, l, r);
    }
    return {res.id, res.rank};
  }

 private:
  struct Node {
    int id;
    int rank;
    int lazyrank;
  };

  int n, k;
  vector<Node> tree;

  void Apply(int u, int r) {
    tree[u].rank += r;
    tree[u].lazyrank += r;
  }

  void Push(int u, int lc, int rc) {
    Apply(lc, tree[u].lazyrank);
    Apply(rc, tree[u].lazyrank);
    tree[u].lazyrank = 0;
  }

  void Pull(int u, int lc, int rc) {
    if (tree[lc].rank < tree[rc].rank) {
      tree[u] = tree[lc];
    } else {
      tree[u] = tree[rc];
    }
    tree[u].lazyrank = 0;
  }

  void Build(int u, int tl, int tr, const vector<int> &r) {
    if (tl == tr) {
      tree[u].id = tl;
      tree[u].rank = r[tl];
      tree[u].lazyrank = 0;
      return;
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Build(lc, tl, md, r);
    Build(rc, md + 1, tr, r);
    Pull(u, lc, rc);
  }

  void Update(int u, int tl, int tr, int l, int r, int rank) {
    if (l > tr || tl > r || tl > tr || l > r) {
      return;
    }
    if (l <= tl && tr <= r) {
      return Apply(u, rank);
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Push(u, lc, rc);
    Update(lc, tl, md, l, r, rank);
    Update(rc, md + 1, tr, l, r, rank);
    Pull(u, lc, rc);
  }

  Node Query(int u, int tl, int tr, int l, int r) {
    if (l > tr || tl > r || tl > tr || l > r) {
      return Node({-1, (int) 1e9, (int) 1e9});
    }
    if (l <= tl && tr <= r) {
      return tree[u];
    }
    int md = (tl + tr) / 2;
    int lc = u + 1;
    int rc = u + 2 * (md - tl + 1);
    Push(u, lc, rc);
    auto ll = Query(lc, tl, md, l, r);
    auto rr = Query(rc, md + 1, tr, l, r);
    if (ll.rank < rr.rank) {
      return ll;
    } else {
      return rr;
    }
  }
};

int n, k;
vector<int> h;
vector<vector<int>> next_inc;
vector<vector<int>> next_dec;

// Greedily find a valid arrangement h
// Indices i, j are comparable if |i - j| < k
// x and y are comparable if there exists a sequence
// h[x] < h[i1] < h[i2] < ... < h[y] and adjacent elements
// have distance < k.

void init(int k, vector<int> r) {
  n = (int) r.size();
  ::k = k;
  h.assign(n, -1);

  { // find a valid configuration h
    Relax relax(n, k, r);
    PotentialMaximum maxim(n, k, r);

    for (int i = 0; i < n; i++) {
      if (r[i] == 0) {
        relax.Delete(i);
        maxim.UpdateIndeg(i);
      }
    }

    for (int v = n - 1; v >= 0; v--) {
      int id = maxim.Query();
      h[id] = v;
      relax.Update(id);
      maxim.Delete(id);
      while (relax.Query(id).second == 0) {
        int p = relax.Query(id).first;
        maxim.UpdateIndeg(p);
        relax.Delete(p);
      }
    }
  }
  for (auto i : h) cerr << i << " "; cerr << "\n";
  { // initialize binary lifting
    for (int i = 0; i < n; i++) {
      h.emplace_back(h[i]);
    }

    set<pair<int, int>> st;
    next_inc.assign(20, vector<int>(2 * n, -1));
    next_dec.assign(20, vector<int>(2 * n, -1));

    for (int i = 2 * n - 1; i >= 0; i--) {
      if (i + k < 2 * n) {
        st.erase({h[i + k], i + k});
      }
      auto it = st.lower_bound({h[i], i});
      next_inc[0][i] = it == end(st) ? -1 : it->second;
      next_dec[0][i] = it == begin(st) ? -1 : prev(it)->second;
      st.insert({h[i], i});
    }

    for (int j = 1; j < 20; j++) {
      for (int i = 0; i < 2 * n; i++) {
        if (next_inc[j - 1][i] == -1) {
          next_inc[j][i] = -1;
        } else {
          next_inc[j][i] = next_inc[j - 1][next_inc[j - 1][i]];
        }
        if (next_dec[j - 1][i] == -1) {
          next_dec[j][i] = -1;
        } else {
          next_dec[j][i] = next_dec[j - 1][next_dec[j - 1][i]];
        }
      }
    }
  }
}

bool Sequence(int t, int x, int y) { // 0 = increasing, 1 = decreasing
  auto &nxt = (t == 0 ? next_inc : next_dec);
  for (int j = 19; j >= 0; j--) {
    if (nxt[j][x] != -1 && y - nxt[j][x] >= k) {
      x = nxt[j][x];
    }
  }
  x = nxt[0][x];
  return x != -1 && y - x < k && (t == 0 ? h[x] <= h[y] : h[x] >= h[y]);
}

int compare_plants(int x, int y) {
  bool comparable = (y - x < k);
  if (h[x] < h[y]) {
    comparable |= Sequence(0, x, y);
    comparable |= Sequence(1, y, x + n);
  } else {
    comparable |= Sequence(0, y, x + n);
    comparable |= Sequence(1, x, y);
  }
  return comparable ? (h[x] > h[y] ? 1 : -1) : 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:296:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  296 |   for (auto i : h) cerr << i << " "; cerr << "\n";
      |   ^~~
plants.cpp:296:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  296 |   for (auto i : h) cerr << i << " "; cerr << "\n";
      |                                      ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 83 ms 3192 KB Output is correct
7 Correct 272 ms 10252 KB Output is correct
8 Correct 1779 ms 71400 KB Output is correct
9 Correct 1804 ms 71320 KB Output is correct
10 Correct 1824 ms 71448 KB Output is correct
11 Correct 1834 ms 71408 KB Output is correct
12 Correct 1869 ms 71480 KB Output is correct
13 Correct 1876 ms 71476 KB Output is correct
14 Correct 2009 ms 71532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 12 ms 768 KB Output is correct
7 Correct 151 ms 5160 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 12 ms 768 KB Output is correct
10 Correct 155 ms 5044 KB Output is correct
11 Correct 148 ms 5100 KB Output is correct
12 Correct 144 ms 5044 KB Output is correct
13 Correct 152 ms 5212 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 12 ms 768 KB Output is correct
7 Correct 151 ms 5160 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 12 ms 768 KB Output is correct
10 Correct 155 ms 5044 KB Output is correct
11 Correct 148 ms 5100 KB Output is correct
12 Correct 144 ms 5044 KB Output is correct
13 Correct 152 ms 5212 KB Output is correct
14 Correct 354 ms 10380 KB Output is correct
15 Correct 3328 ms 75880 KB Output is correct
16 Correct 341 ms 10384 KB Output is correct
17 Correct 3353 ms 75800 KB Output is correct
18 Correct 2290 ms 74548 KB Output is correct
19 Correct 2415 ms 74740 KB Output is correct
20 Correct 3040 ms 79332 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 133 ms 3956 KB Output is correct
4 Correct 2159 ms 71560 KB Output is correct
5 Correct 2423 ms 71536 KB Output is correct
6 Correct 2866 ms 71656 KB Output is correct
7 Correct 3148 ms 71496 KB Output is correct
8 Correct 3333 ms 74220 KB Output is correct
9 Correct 2211 ms 71384 KB Output is correct
10 Correct 2303 ms 71544 KB Output is correct
11 Correct 1884 ms 71320 KB Output is correct
12 Correct 2217 ms 71396 KB Output is correct
13 Correct 2303 ms 72676 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 23 ms 1024 KB Output is correct
8 Correct 23 ms 1152 KB Output is correct
9 Correct 25 ms 1024 KB Output is correct
10 Correct 25 ms 1024 KB Output is correct
11 Correct 27 ms 1128 KB Output is correct
12 Correct 25 ms 1024 KB Output is correct
13 Correct 23 ms 1024 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 10 ms 640 KB Output is correct
6 Correct 2127 ms 71528 KB Output is correct
7 Correct 2548 ms 71536 KB Output is correct
8 Correct 2917 ms 71664 KB Output is correct
9 Correct 3191 ms 74344 KB Output is correct
10 Correct 1971 ms 71524 KB Output is correct
11 Correct 2545 ms 73712 KB Output is correct
12 Correct 1884 ms 71432 KB Output is correct
13 Correct 2146 ms 71648 KB Output is correct
14 Correct 2569 ms 71524 KB Output is correct
15 Correct 2941 ms 71808 KB Output is correct
16 Correct 2055 ms 71304 KB Output is correct
17 Correct 2135 ms 71476 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 83 ms 3192 KB Output is correct
7 Correct 272 ms 10252 KB Output is correct
8 Correct 1779 ms 71400 KB Output is correct
9 Correct 1804 ms 71320 KB Output is correct
10 Correct 1824 ms 71448 KB Output is correct
11 Correct 1834 ms 71408 KB Output is correct
12 Correct 1869 ms 71480 KB Output is correct
13 Correct 1876 ms 71476 KB Output is correct
14 Correct 2009 ms 71532 KB Output is correct
15 Correct 1 ms 256 KB Output is correct
16 Correct 1 ms 256 KB Output is correct
17 Correct 1 ms 256 KB Output is correct
18 Correct 1 ms 256 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 12 ms 768 KB Output is correct
21 Correct 151 ms 5160 KB Output is correct
22 Correct 4 ms 384 KB Output is correct
23 Correct 12 ms 768 KB Output is correct
24 Correct 155 ms 5044 KB Output is correct
25 Correct 148 ms 5100 KB Output is correct
26 Correct 144 ms 5044 KB Output is correct
27 Correct 152 ms 5212 KB Output is correct
28 Correct 354 ms 10380 KB Output is correct
29 Correct 3328 ms 75880 KB Output is correct
30 Correct 341 ms 10384 KB Output is correct
31 Correct 3353 ms 75800 KB Output is correct
32 Correct 2290 ms 74548 KB Output is correct
33 Correct 2415 ms 74740 KB Output is correct
34 Correct 3040 ms 79332 KB Output is correct
35 Correct 1 ms 256 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 133 ms 3956 KB Output is correct
38 Correct 2159 ms 71560 KB Output is correct
39 Correct 2423 ms 71536 KB Output is correct
40 Correct 2866 ms 71656 KB Output is correct
41 Correct 3148 ms 71496 KB Output is correct
42 Correct 3333 ms 74220 KB Output is correct
43 Correct 2211 ms 71384 KB Output is correct
44 Correct 2303 ms 71544 KB Output is correct
45 Correct 1884 ms 71320 KB Output is correct
46 Correct 2217 ms 71396 KB Output is correct
47 Correct 2303 ms 72676 KB Output is correct
48 Correct 1 ms 256 KB Output is correct
49 Correct 1 ms 256 KB Output is correct
50 Correct 1 ms 256 KB Output is correct
51 Correct 1 ms 384 KB Output is correct
52 Correct 1 ms 384 KB Output is correct
53 Correct 3 ms 384 KB Output is correct
54 Correct 23 ms 1024 KB Output is correct
55 Correct 23 ms 1152 KB Output is correct
56 Correct 25 ms 1024 KB Output is correct
57 Correct 25 ms 1024 KB Output is correct
58 Correct 27 ms 1128 KB Output is correct
59 Correct 25 ms 1024 KB Output is correct
60 Correct 23 ms 1024 KB Output is correct
61 Correct 117 ms 3828 KB Output is correct
62 Correct 286 ms 9996 KB Output is correct
63 Correct 1980 ms 71604 KB Output is correct
64 Correct 2273 ms 71628 KB Output is correct
65 Correct 2774 ms 71536 KB Output is correct
66 Correct 3122 ms 71668 KB Output is correct
67 Correct 3239 ms 73968 KB Output is correct
68 Correct 2121 ms 71524 KB Output is correct
69 Correct 2685 ms 73776 KB Output is correct
70 Correct 2095 ms 71444 KB Output is correct
71 Correct 2327 ms 71408 KB Output is correct
72 Correct 2853 ms 71400 KB Output is correct
73 Correct 3128 ms 71528 KB Output is correct
74 Correct 2025 ms 71424 KB Output is correct
75 Correct 2334 ms 71536 KB Output is correct