oj.uz

Submission #827802

# Submission time Handle Problem Language Result Execution time Memory
827802 2023-08-16T19:08:36 Z erray Comparing Plants (IOI20_plants) C++17
100 / 100
 1034 ms 108524 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
  #include "/home/eagle/ioi19/day2/debug.h"
#else 
  #define debug(...) void(37)
#endif

const int inf = int(1e9);
struct SegTree {
  struct node {
    array<int, 2> mn{}; 
    int tag = 0;
    node operator+(node x) {
      node res;
      res.mn = min(mn, x.mn);
      return res;
    }
    void modify(int x) {
      tag += x;
      mn[0] += x;
    }
  };
  vector<node> tree;
  int n;
  void push(int v, int rv) {
    tree[v + 1].modify(tree[v].tag);
    tree[rv].modify(tree[v].tag);
    tree[v].tag = 0;
  }
  #define def int mid = (l + r) >> 1, rv = v + ((mid - l + 1) << 1)
  void modify(int v, int l, int r, int ll, int rr, int x) {
    debug(v, l, r, ll, rr, x);
    if (l >= ll && rr >= r) {
      if (l == r) {
        tree[v].mn[1] = l;
      }
      tree[v].modify(x);
      debug(v, l, r, tree[v].mn);
      return;
    }
    def;
    push(v, rv);
    if (mid >= ll) {
      modify(v + 1, l, mid, ll, rr, x);
    }
    if (mid < rr) {
      modify(rv, mid + 1, r, ll, rr, x);
    }
    tree[v] = tree[v + 1] + tree[rv];
    debug(v, l, r, tree[v].mn);
  }
  array<int, 2> root() {
    return tree[0].mn;
  }
  void modify(int l, int r, int x) {
    modify(0, 0, n - 1, l, r, x);
  }
  SegTree(int _n) : n(_n) {
    tree.resize(n * 2);
  }
};

int N, K, LG;
vector<int> ord;
vector<vector<int>> liftL, liftR;
vector<vector<long long>> distL, distR;
int L_dist(int from, int to) {
  return (from >= to ? from - to : from + N - to);
}
int R_dist(int from, int to) {
  return (from <= to ? to - from : to + N - from);
}

void init(int _K, std::vector<int> R) {
  reverse(R.begin(), R.end());
  N = int(R.size());
  K = _K;
  LG = __lg(N) + 1;
  SegTree st(N);
  for (int i = 0; i < N; ++i) {
    st.modify(i, i, +R[i]);
  }
  debug(N, K, LG, R);
  set<int> act;
  set<pair<int, int>> dists;
  vector<int> cur_len(N, -1);
  vector<int> use;
  auto Upd_len = [&](int x) {
    debug("upd after", x);
    if (act.empty()) {
      return;
    }
    auto it = act.lower_bound(x);
    if (it == act.begin()) {
      it = act.end();
    }
    it = prev(it);
    x = *it;
    debug("upd", x);
    //debug(dists);
    if (cur_len[x] != -1) {
      dists.erase(dists.find(pair{cur_len[x], x}));
    }
    it = next(it);
    if (it == act.end()) {
      int from = *act.begin();
      cur_len[x] = from + N - x;
    } else {
      cur_len[x] = *it - x;
    }
    dists.emplace(cur_len[x], x);
  };
  auto Add_seg = [&](int x) {    
    debug("add", x);
    act.insert(x);
    Upd_len(x + 1);
    Upd_len(x);
  };
  vector<int> next(N, -1);
  auto Push_segs = [&](int last) {
    debug(st.root());
    while (st.root()[0] == 0) {
      debug("add", st.root());
      int id = st.root()[1];
      st.modify(id, id, +inf);
      next[id] = (last == -1 ? id : last);
      Add_seg(id);
    }
  };
  Push_segs(-1);
  ord.resize(N);
  for (int i = 0; i < N; ++i) {
    debug(dists);
    assert(!dists.empty());
    auto it = prev(dists.end());
    auto[len, id] = *it;
    debug("########################", i, len, id);
    ord[id] = i;
    assert(len >= K);
    dists.erase(it);
    act.erase(id);
    Upd_len(id);
    int r = id + K - 1;
    debug("upd seg tree");
    if (r < N) {
      debug(id, r);
      st.modify(id, r, -1);
    } else {
      debug(id, N - 1);
      debug(0, r);
      r %= N;
      st.modify(id, N - 1, -1);
      st.modify(0, r, -1);
    }
    Push_segs(id);
  }
  liftL.resize(LG, vector<int>(N));
  liftR.resize(LG, vector<int>(N));
  distL.resize(LG, vector<long long>(N));
  distR.resize(LG, vector<long long>(N));
  set<pair<int, int>> mx;
  for (int i = 1; i < K; ++i) {
    mx.emplace(ord[i], i);
  }
  for (int i = 0; i < N; ++i) {
    auto it = mx.lower_bound(pair{ord[i], -1});
    liftR[0][i] = (it == mx.begin() ? i : prev(it)->second);
    int add = (i + K) % N;
    mx.emplace(ord[add], add);
    int rem = (i + 1) % N;
    mx.erase(pair{ord[rem], rem});
  }
  mx.clear();
  for (int i = 1; i < K; ++i) {
    mx.emplace(ord[N - i], N - i);
  }
  for (int i = 0; i < N; ++i) {
    debug(i, mx);
    auto it = mx.lower_bound(pair{ord[i], -1});
    liftL[0][i] = (it == mx.begin() ? i : prev(it)->second);
    mx.emplace(ord[i], i);
    int rem = (N - K + i + 1) % N;
    mx.erase(pair{ord[rem], rem});
  }
  for (int i = 0; i < N; ++i) {
    distL[0][i] = L_dist(i, liftL[0][i]);
    distR[0][i] = R_dist(i, liftR[0][i]);
  }
  for (int l = 1; l < LG; ++l) {
    for (int i = 0; i < N; ++i) {
      {
        int to = liftL[l - 1][i];
        liftL[l][i] = liftL[l - 1][to];
        distL[l][i] = distL[l - 1][i] + distL[l - 1][to]; 
      }
      {
        int to = liftR[l - 1][i];
        liftR[l][i] = liftR[l - 1][to];
        distR[l][i] = distR[l - 1][i] + distR[l - 1][to]; 
      }
    }
  }
  debug(R, ord, liftL[0], liftR[0]);
}

//#define SUBTASK3 false

int elevate(int v, int to, vector<vector<int>>& lift, vector<vector<long long>>& dist) {
  for (int l = LG - 1; l >= 0; --l) {
    if (dist[l][v] <= to) {
      to -= dist[l][v];
      v = lift[l][v];
    }
  }
  return v;
}

bool depends(int x, int y) {
  if (ord[x] > ord[y]) {
    swap(x, y);
  }
  {
    int dist = L_dist(y, x);
    int go = elevate(y, dist, liftL, distL);
    if (L_dist(go, x) < K && ord[x] <= ord[go]) {
      return true;
    }
  }
  {
    int dist = R_dist(y, x);
    int go = elevate(y, dist, liftR, distR);
    if (R_dist(go, x) < K && ord[x] <= ord[go]) {
      return true;
    }
  }
  return false;
}

int compare_plants(int x, int y) {
  x = N - 1 - x;
  y = N - 1 - y;
  debug("compare", x, y);
	if (depends(x, y)) {
    return (ord[x] < ord[y] ? 1 : -1);
  }
  return 0;
  
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 42 ms 4036 KB Output is correct
7 Correct 121 ms 13092 KB Output is correct
8 Correct 793 ms 101472 KB Output is correct
9 Correct 818 ms 101816 KB Output is correct
10 Correct 745 ms 101672 KB Output is correct
11 Correct 809 ms 101200 KB Output is correct
12 Correct 783 ms 101572 KB Output is correct
13 Correct 987 ms 101788 KB Output is correct
14 Correct 550 ms 101144 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 55 ms 6892 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 58 ms 6932 KB Output is correct
11 Correct 85 ms 6700 KB Output is correct
12 Correct 71 ms 6904 KB Output is correct
13 Correct 55 ms 7016 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 724 KB Output is correct
7 Correct 55 ms 6892 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 3 ms 724 KB Output is correct
10 Correct 58 ms 6932 KB Output is correct
11 Correct 85 ms 6700 KB Output is correct
12 Correct 71 ms 6904 KB Output is correct
13 Correct 55 ms 7016 KB Output is correct
14 Correct 100 ms 13312 KB Output is correct
15 Correct 781 ms 104864 KB Output is correct
16 Correct 102 ms 13316 KB Output is correct
17 Correct 877 ms 104936 KB Output is correct
18 Correct 964 ms 103752 KB Output is correct
19 Correct 680 ms 103840 KB Output is correct
20 Correct 776 ms 108524 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 63 ms 5448 KB Output is correct
4 Correct 753 ms 101708 KB Output is correct
5 Correct 831 ms 102488 KB Output is correct
6 Correct 769 ms 101508 KB Output is correct
7 Correct 744 ms 101548 KB Output is correct
8 Correct 863 ms 103308 KB Output is correct
9 Correct 957 ms 101496 KB Output is correct
10 Correct 720 ms 100560 KB Output is correct
11 Correct 949 ms 101808 KB Output is correct
12 Correct 593 ms 101320 KB Output is correct
13 Correct 1034 ms 101920 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 276 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 11 ms 1236 KB Output is correct
8 Correct 10 ms 1332 KB Output is correct
9 Correct 12 ms 1236 KB Output is correct
10 Correct 15 ms 1332 KB Output is correct
11 Correct 11 ms 1236 KB Output is correct
12 Correct 12 ms 1272 KB Output is correct
13 Correct 10 ms 1236 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 539 ms 100596 KB Output is correct
7 Correct 563 ms 100580 KB Output is correct
8 Correct 671 ms 100804 KB Output is correct
9 Correct 695 ms 102932 KB Output is correct
10 Correct 532 ms 101204 KB Output is correct
11 Correct 639 ms 102420 KB Output is correct
12 Correct 501 ms 100488 KB Output is correct
13 Correct 514 ms 100820 KB Output is correct
14 Correct 619 ms 100692 KB Output is correct
15 Correct 599 ms 100856 KB Output is correct
16 Correct 513 ms 100868 KB Output is correct
17 Correct 499 ms 100884 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 296 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 42 ms 4036 KB Output is correct
7 Correct 121 ms 13092 KB Output is correct
8 Correct 793 ms 101472 KB Output is correct
9 Correct 818 ms 101816 KB Output is correct
10 Correct 745 ms 101672 KB Output is correct
11 Correct 809 ms 101200 KB Output is correct
12 Correct 783 ms 101572 KB Output is correct
13 Correct 987 ms 101788 KB Output is correct
14 Correct 550 ms 101144 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 3 ms 724 KB Output is correct
21 Correct 55 ms 6892 KB Output is correct
22 Correct 2 ms 340 KB Output is correct
23 Correct 3 ms 724 KB Output is correct
24 Correct 58 ms 6932 KB Output is correct
25 Correct 85 ms 6700 KB Output is correct
26 Correct 71 ms 6904 KB Output is correct
27 Correct 55 ms 7016 KB Output is correct
28 Correct 100 ms 13312 KB Output is correct
29 Correct 781 ms 104864 KB Output is correct
30 Correct 102 ms 13316 KB Output is correct
31 Correct 877 ms 104936 KB Output is correct
32 Correct 964 ms 103752 KB Output is correct
33 Correct 680 ms 103840 KB Output is correct
34 Correct 776 ms 108524 KB Output is correct
35 Correct 1 ms 212 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 63 ms 5448 KB Output is correct
38 Correct 753 ms 101708 KB Output is correct
39 Correct 831 ms 102488 KB Output is correct
40 Correct 769 ms 101508 KB Output is correct
41 Correct 744 ms 101548 KB Output is correct
42 Correct 863 ms 103308 KB Output is correct
43 Correct 957 ms 101496 KB Output is correct
44 Correct 720 ms 100560 KB Output is correct
45 Correct 949 ms 101808 KB Output is correct
46 Correct 593 ms 101320 KB Output is correct
47 Correct 1034 ms 101920 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 276 KB Output is correct
50 Correct 1 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 1 ms 296 KB Output is correct
53 Correct 2 ms 340 KB Output is correct
54 Correct 11 ms 1236 KB Output is correct
55 Correct 10 ms 1332 KB Output is correct
56 Correct 12 ms 1236 KB Output is correct
57 Correct 15 ms 1332 KB Output is correct
58 Correct 11 ms 1236 KB Output is correct
59 Correct 12 ms 1272 KB Output is correct
60 Correct 10 ms 1236 KB Output is correct
61 Correct 53 ms 5392 KB Output is correct
62 Correct 124 ms 13020 KB Output is correct
63 Correct 890 ms 101664 KB Output is correct
64 Correct 617 ms 101524 KB Output is correct
65 Correct 781 ms 101552 KB Output is correct
66 Correct 707 ms 101656 KB Output is correct
67 Correct 760 ms 103792 KB Output is correct
68 Correct 918 ms 101744 KB Output is correct
69 Correct 676 ms 103216 KB Output is correct
70 Correct 794 ms 101888 KB Output is correct
71 Correct 806 ms 102304 KB Output is correct
72 Correct 763 ms 101648 KB Output is correct
73 Correct 728 ms 101696 KB Output is correct
74 Correct 757 ms 101620 KB Output is correct
75 Correct 667 ms 101844 KB Output is correct