oj.uz

Submission #301923

# Submission time Handle Problem Language Result Execution time Memory
301923 2020-09-18T09:51:06 Z rama_pang Comparing Plants (IOI20_plants) C++14
44 / 100
 1909 ms 18604 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;

// 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);

  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);
    }
  }
}

int compare_plants(int x, int y) {
  return h[x] > h[y] ? 1 : -1;
}

Subtask #1
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 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 288 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 90 ms 3380 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 91 ms 3480 KB Output is correct
11 Correct 80 ms 3252 KB Output is correct
12 Correct 82 ms 3508 KB Output is correct
13 Correct 91 ms 3380 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 288 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Correct 90 ms 3380 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 7 ms 512 KB Output is correct
10 Correct 91 ms 3480 KB Output is correct
11 Correct 80 ms 3252 KB Output is correct
12 Correct 82 ms 3508 KB Output is correct
13 Correct 91 ms 3380 KB Output is correct
14 Correct 186 ms 4348 KB Output is correct
15 Correct 1909 ms 18476 KB Output is correct
16 Correct 190 ms 4216 KB Output is correct
17 Correct 1828 ms 18396 KB Output is correct
18 Correct 997 ms 18412 KB Output is correct
19 Correct 1124 ms 18392 KB Output is correct
20 Correct 1531 ms 18604 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 256 KB Output is correct
3 Correct 71 ms 3316 KB Output is correct
4 Correct 773 ms 18280 KB Output is correct
5 Correct 985 ms 18536 KB Output is correct
6 Correct 1333 ms 18464 KB Output is correct
7 Correct 1651 ms 18280 KB Output is correct
8 Correct 1800 ms 18408 KB Output is correct
9 Correct 857 ms 18284 KB Output is correct
10 Correct 887 ms 18408 KB Output is correct
11 Correct 581 ms 18536 KB Output is correct
12 Correct 874 ms 18408 KB Output is correct
13 Correct 962 ms 18388 KB Output is correct

Subtask #5
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 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 1 ms 256 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
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 Incorrect 1 ms 384 KB Output isn't correct
5 Halted 0 ms 0 KB -