CPP_Classrooms
unknown
c_cpp
2 months ago
4.5 kB
37
Indexable
#include <algorithm> #include <cstdio> #include <utility> #define RANK(x) ((1 << (31 - __builtin_clz(x))) - 1) using interval = std::pair<int, int>; struct node { int value; int numvalid; int min; int count; }; int update(node* tree, int start, int end, int s, int f) { int root = start + RANK(end - start); if (tree[root].min >= s) return 0; int lvl = 0; int parents[20]; int p_end[20]; int best = -1; int bestlvl = -1; for (;;) { auto [val, num, min, count] = tree[root]; int oldend = end; if (val < s) { if (count) { best = root; bestlvl = lvl - 1; start = root + 1; } else { int right_start = root + 1; int left_end = root; if (right_start >= end) { end = left_end; } else { int right_root = right_start + RANK(end - right_start); if (tree[right_root].numvalid < 1) { end = left_end; } else { if (tree[right_root].min >= s) { end = left_end; } else { start = right_start; } } } } } else { end = root; } if (start >= end) break; int oldroot = root; root = start + RANK(end - start); if (tree[root].numvalid < 1 || tree[root].min >= s) break; parents[lvl] = oldroot; p_end[lvl] = oldend; lvl++; } auto &[val, numvalid, min, count] = tree[best]; count--; numvalid--; for(int i = bestlvl; i >= 0; i--) tree[parents[i]].numvalid--; if (count == 0) { int newmin = min; if (min == val) { if (numvalid) { newmin = tree[root].min; } else { if (bestlvl == -1) newmin = f; else { for(int l = bestlvl;;l--) { int n = parents[l]; node *p = &tree[n]; if (p->numvalid) { if (p->count > 0) newmin = p->value; else { int p_r_start = n+1; int p_r_end = p_end[l]; int r = p_r_start + RANK(p_r_end-p_r_start); newmin = tree[r].min; } break; } } } } } for(int i = bestlvl; i >= 0; i--) { node *p = &tree[parents[i]]; if (p->min == min) p->min = newmin; } min = newmin; } return 1; } int main() { int n, k; scanf("%d %d\n", &n, &k); interval* intervals = new interval[n]; for(int i = 0; i < n; i++) { scanf("%d %d\n", &intervals[i].first, &intervals[i].second); } std::sort(intervals, intervals+n, [](interval a, interval b) { return a.second < b.second; }); int start = 0, end = 1; node* tree = new node[1 + n]; tree[0] = {0,k,0,k}; int count = 0; for(int i = 0; i < n; i++) { auto [s, f] = intervals[i]; int success = update(tree, start, end, s, f); if (success) { bool eq = false; if (tree[end-1].value == f) { tree[end-1].count++; eq = true; } else tree[end++] = {f, 0, f, 1}; int numvalid = tree[end-1].numvalid+1; int min = f; int _start = 0, _end = end; int _root = _start + RANK(_end-_start); for(; tree[_root].value != f;) { tree[_root].numvalid++; _start = _root + 1; _root = _start + RANK(_end-_start); } if (((end-1) & 1) == 1 && !eq) { _end = _root; if (_start < _end) { _root = _start + RANK(_end-_start); min = tree[_root].numvalid > 0 ? tree[_root].min : f; numvalid = tree[_root].numvalid + 1; } tree[end-1].min = min; } tree[end-1].numvalid = numvalid; count += 1; } } printf("%d\n", count); return 0; }
Editor is loading...
Leave a Comment