Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- int MAXOP = 110000;
- struct Operation {
- Operation () {
- left = 0;
- right = 0;
- value = 0;
- }
- Operation(bool sgn, int lft, int rgt) {
- value = sgn;
- left = lft;
- right = rgt;
- }
- bool value;
- int left;
- int right;
- };
- struct PointsPair {
- int left, right;
- };
- struct Point {
- int coord;
- bool is_right;
- size_t op_idx;
- bool operator < (const Point& other) const {
- return coord < other.coord;
- }
- };
- std::vector<PointsPair> pointsPairs(MAXOP);
- std::vector<int> uniqPoints(2 * MAXOP);
- std::vector<Operation> input(MAXOP);
- size_t uniqueOrdered(size_t operNum,
- std::vector<PointsPair>& pointsPairs) {
- std::vector<Point> points(2 * operNum);
- for (size_t i = 0; i < operNum; ++i) {
- points[2 * i].is_right = 0;
- points[2 * i].coord = input[i].left;
- points[2 * i].op_idx = i;
- points[2 * i + 1].is_right = 1;
- points[2 * i + 1].coord = input[i].right;
- points[2 * i + 1].op_idx = i;
- }
- std::sort(points.begin(), points.end());
- size_t cnt = 0;
- for (size_t i = 0; i < 2 * operNum; ++i) {
- if (i == 0 || uniqPoints[cnt - 1] != points[i].coord)
- uniqPoints[cnt++] = points[i].coord;
- if (!points[i].is_right)
- pointsPairs[points[i].op_idx].left = cnt - 1;
- else
- pointsPairs[points[i].op_idx].right = cnt - 1;
- }
- return cnt;
- }
- size_t getDists(const std::vector<int>& uniqPoints, std::vector<int>& segs, size_t size) {
- for (size_t i = 0; i < size - 1; ++i) {
- segs[i] = uniqPoints[i + 1] - uniqPoints[i];
- }
- return size - 1;
- }
- struct Segment {
- int cur_len;
- int max_len;
- size_t lazy;
- };
- struct SegmentTree {
- size_t size;
- std::vector<Segment> values;
- explicit SegmentTree(size_t size): size(size), values(4 * size) {}
- };
- void buildSubtree(SegmentTree& stree, std::vector<int>& segments, size_t current, size_t left, size_t right)
- {
- stree.values[current].cur_len = 0;
- stree.values[current].lazy = 0;
- if (left == right) {
- stree.values[current].max_len = segments[left];
- } else {
- size_t middle = (left + right) / 2;
- buildSubtree(stree, segments, 2 * current, left, middle);
- buildSubtree(stree, segments, 2 * current + 1, middle + 1, right);
- stree.values[current].max_len = stree.values[2 * current].max_len
- + stree.values[2 * current + 1].max_len;
- }
- }
- void buildTree(SegmentTree& tree, std::vector<int>& segments, size_t size) {
- buildSubtree(tree, segments, 1, 0, size - 1);
- }
- int64_t getLen(const Segment& segment)
- {
- return (segment.lazy != 0) ? segment.max_len : segment.cur_len;
- }
- int64_t subtreeOper(SegmentTree& stree, size_t current, size_t left, size_t right, size_t from, size_t to, char operation)
- {
- if (to < left || right < from) {
- return getLen(stree.values[current]);
- }
- if ((from <= left && right <= to) || (left == right)) {
- operation == 1 ? stree.values[current].lazy++ : stree.values[current].lazy--;
- return getLen(stree.values[current]);
- }
- size_t middle = (left + right) / 2;
- stree.values[current].cur_len = subtreeOper(stree, 2 * current,
- left,
- middle,
- from,
- to,
- operation)
- + subtreeOper(stree, 2 * current + 1, middle + 1,
- right, from, to, operation);
- return getLen(stree.values[current]);
- }
- int64_t treeSum(SegmentTree& stree) {
- return getLen(stree.values[1]);
- }
- int main() {
- size_t numOper;
- std::cin >> numOper;
- for (size_t i = 0; i < numOper; ++i) {
- char sign;
- std::cin >> sign;
- std::cin >> input[i].left;
- std::cin >> input[i].right;
- sign == '+' ? input[i].value = 1 : input[i].value = 0;
- }
- size_t pSize = uniqueOrdered(numOper, pointsPairs);
- std::vector<int> segments(2 * numOper - 1);
- size_t segCount = getDists(uniqPoints, segments, pSize);
- SegmentTree tree(segCount);
- buildTree(tree, segments, segCount);
- for (size_t i = 0; i < numOper; ++i) {
- size_t from = pointsPairs[i].left;
- size_t to = pointsPairs[i].right;
- if (from != to) {
- subtreeOper(tree, 1, 0, tree.size - 1,
- from, to - 1, input[i].value);
- }
- std::cout << treeSum(tree) << std::endl;
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement