Submission #361552

#TimeUsernameProblemLanguageResultExecution timeMemory
361552SortingComparing Plants (IOI20_plants)C++17
27 / 100
1532 ms55556 KiB
#include "plants.h" #include <bits/stdc++.h> using namespace std; const int N = 2e5 + 3; int r_arr[N], p[N], k, n; struct Segment_Tree{ struct Node{ int mn; array<int, 2> prev_zero; Node(){} Node(int mn, int i): mn(mn), prev_zero({i, 0}){} friend Node merge(const Node &l, const Node &r){ Node ret; ret.mn = min(l.mn, r.mn); if(r.prev_zero[1] >= k) ret.prev_zero = r.prev_zero; else if(l.prev_zero[1]) ret.prev_zero = l.prev_zero; else ret.prev_zero = r.prev_zero; return ret; } }; Node nd[4 * N]; int lp[4 * N]; void init(int i = 0, int l = 0, int r = n - 1){ if(l == r){ nd[i] = Node(r_arr[l], l); return; } int mid = (l + r) >> 1; init(2 * i + 1, l, mid); init(2 * i + 2, mid + 1, r); nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]); } void push(int i, int l, int r){ nd[i].mn += lp[i]; if(l != r){ lp[2 * i + 1] += lp[i]; lp[2 * i + 2] += lp[i]; } lp[i] = 0; } int query(int i = 0, int l = 0, int r = n - 1){ push(i, l, r); return nd[i].prev_zero[0]; } int get_next_zero(int s, int i = 0, int l = 0, int r = n - 1){ if(l > r) return n; push(i, l, r); if(r < s || nd[i].mn) return n; if(l == r) return l; int mid = (l + r) >> 1; int l_val = get_next_zero(s, 2 * i + 1, l, mid); if(l_val != n) return l_val; return get_next_zero(s, 2 * i + 2, mid + 1, r); } int get_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){ if(l > r) return -1; push(i, l, r); if(l > s || nd[i].mn) return -1; if(l == r) return l; int mid = (l + r) >> 1; int r_val = get_prev_zero(s, 2 * i + 2, mid + 1, r); if(r_val != -1) return r_val; return get_prev_zero(s, 2 * i + 1, l, mid); } void update_prev_zero(int s, int i = 0, int l = 0, int r = n - 1){ if(l > r) return; push(i, l, r); if(l > s || r < s) return; if(l == r){ nd[i].prev_zero = {s, s - get_prev_zero(s - 1, 0, 0, n - 1)}; return; } int mid = (l + r) >> 1; update_prev_zero(s, 2 * i + 1, l, mid); update_prev_zero(s, 2 * i + 2, mid + 1, r); nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]); } void update_zeroes(int l2, int r2, int i = 0, int l = 0, int r = n - 1){ if(l > r) return; push(i, l, r); if(nd[i].mn) return; if(r < l2 || r2 < l) return; if(l == r){ update_prev_zero(l, i, l, r); return; } int mid = (l + r) >> 1; update_zeroes(l2, r2, 2 * i + 1, l, mid); update_zeroes(l2, r2, 2 * i + 2, mid + 1, r); nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]); } void change_value(int s, int val, int i = 0, int l = 0, int r = n - 1){ if(l > r) return; push(i, l, r); if(r < s || s < l) return; if(l == r){ nd[i] = Node(val, s); return; } int mid = (l + r) >> 1; change_value(s, val, 2 * i + 1, l, mid); change_value(s, val, 2 * i + 2, mid + 1, r); nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]); } void update(int l2, int r2, int val, int i = 0, int l = 0, int r = n - 1){ if(l > r) return; push(i, l, r); if(r < l2 || r2 < l) return; if(l2 <= l && r <= r2){ lp[i]+=val; push(i, l, r); return; } int mid = (l + r) >> 1; update(l2, r2, val, 2 * i + 1, l, mid); update(l2, r2, val, 2 * i + 2, mid + 1, r); nd[i] = merge(nd[2 * i + 1], nd[2 * i + 2]); } } st; struct Fenwick{ int a[N]; Fenwick(){} void clear(){ fill(a, a + N, 0); } void update(int i, int v){ for(++i; i < N; i+=i&-i) a[i] += v; } int query(int i){ int ans = 0; for(++i; i >= 1; i-=i&-i) ans += a[i]; return ans; } int query(int l, int r){ return query(r) - query(l - 1); } } f; const int LOGN = 18; int nxt[2][LOGN][N]; void init(int _k, vector<int> _r) { k = _k; n = _r.size(); for(int i = 0; i < _r.size(); ++i) r_arr[i] = _r[i]; st.init(); st.update_zeroes(0, n - 1); for(int i = n - 1; i >= 0; --i){ int idx = st.query(); p[idx] = i; //cout << idx << " idx" << endl; st.change_value(idx, n); if(idx){ st.update(max(idx - (k - 1), 0), idx - 1, -1); st.update_zeroes(max(idx - (k - 1), 0), idx - 1); } if(idx < k - 1){ st.update(n - ((k - 1) - idx), n - 1, -1); st.update_zeroes(n - ((k - 1) - idx), n - 1); } int nxt = st.get_next_zero(idx + 1); if(nxt != n) st.update_prev_zero(nxt); } set<array<int, 2>> s; for(int i = n - 1; i > n - k; --i) s.insert({p[i], i}); for(int i = 0; i < n; ++i){ auto it = s.lower_bound({p[i], 0}); if(it == s.end()) nxt[0][0][i] = -1; else nxt[0][0][i] = (*it)[1]; int prev_i = (i - (k - 1) + n) % n; s.erase({p[prev_i], prev_i}); s.insert({p[i], i}); } s.clear(); for(int i = 0; i < k - 1; ++i) s.insert({p[i], i}); for(int i = n - 1; i >= 0; --i){ auto it = s.lower_bound({p[i], 0}); if(it == s.end()) nxt[1][0][i] = -1; else nxt[1][0][i] = (*it)[1]; int prev_i = (i + (k - 1)) % n; s.erase({p[prev_i], prev_i}); s.insert({p[i], i}); } for(int i = 1; i < LOGN; ++i) for(int j = 0; j < n; ++j){ int &ans = nxt[0][i][j]; int node_2 = nxt[0][i - 1][j]; if(node_2 == -1){ ans = -1; continue; } int node_3 = nxt[0][i - 1][node_2]; if(node_3 == -1){ ans = node_3; continue; } if(i < node_2){ if(node_3 > node_2 || node_3 <= j) ans = -1; else ans = node_3; } else{ if(node_3 > node_2 && node_3 <= j) ans = -1; else ans = node_3; } } for(int i = 1; i < LOGN; ++i) for(int j = 0; j < n; ++j){ int &ans = nxt[1][i][j]; int node_2 = nxt[1][i - 1][j]; if(node_2 == -1){ ans = -1; continue; } int node_3 = nxt[1][i - 1][node_2]; if(node_3 == -1){ ans = node_3; continue; } if(i < node_2){ if(node_3 >= j && node_3 < node_2) ans = -1; else ans = node_3; } else{ if(node_3 >= j || node_3 < node_2) ans = -1; else ans = node_3; } } //cout << "done preprocessing" << endl; } int get_dist(int x, int y){ return min(abs(x - y), min(abs(x + n - y), abs(y + n - x))); } bool connected(int x, int y){ if(get_dist(x, y) <= k - 1) return true; if(p[x] > p[y]) swap(x, y); int target = (y + (k - 1)) % n; int curr_x = x; for(int i = LOGN - 1; i >= 0; --i){ int cand = nxt[0][i][curr_x]; if(cand != -1){ if(curr_x < target){ if(cand < curr_x || target < cand) curr_x = cand; } else{ if(target < cand && cand < curr_x) curr_x = cand; } } } curr_x = nxt[0][0][curr_x]; if(curr_x != -1 && get_dist(y, curr_x) <= k - 1) if(p[curr_x] <= p[y]) return true; target = (y - (k - 1) + n) % n; curr_x = x; for(int i = LOGN - 1; i >= 0; --i){ int cand = nxt[1][i][curr_x]; if(cand != -1){ if(curr_x < target){ if(curr_x < cand && cand < target) curr_x = cand; } else{ if(curr_x < cand || cand < target) curr_x = cand; } } } curr_x = nxt[1][0][curr_x]; if(curr_x != -1 && get_dist(y, curr_x) <= k - 1) if(p[curr_x] <= p[y]) return true; return false; } int compare_plants(int x, int y) { if(!connected(x, y)) return 0; return (p[x] > p[y]) ? 1 : -1; } /* 4 3 2 0 1 1 2 0 2 1 2 */ /* 4 2 2 0 1 0 1 0 3 1 3 */ /* 4 3 2 1 1 0 2 0 1 0 2 */

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:185:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 |     for(int i = 0; i < _r.size(); ++i)
      |                    ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...