Submission #945135

#TimeUsernameProblemLanguageResultExecution timeMemory
945135infrapolarMonkey and Apple-trees (IZhO12_apple)C++17
0 / 100
399 ms262144 KiB
#include <bits/stdc++.h> using namespace std; struct Node{ Node *left = nullptr, *right = nullptr; int64_t count = 0; bool red = false; int64_t node_l, node_r; Node(int64_t l, int64_t r){ node_l = l; node_r = r; } void check_children(){ int64_t mid = (node_l + node_r); if (mid < 0LL){ mid -= 1; } mid /= 2LL; if (left == nullptr) left = new Node(node_l, mid); if (right == nullptr) right = new Node(mid+1, node_r); } void push(){ check_children(); if (!red) return; Node* child = left; for (int i = 0; i < 2; i++) { child->red = true; child->count = child->node_r - child->node_l + 1; child = right; } } void paint(int64_t l, int64_t r){ if (l > node_r || r < node_l) return; if (l <= node_l && node_r <= r){ red = true; count = node_r - node_l+1; return; } push(); left->paint(l, r); right->paint(l, r); count = left->count + right->count; } int64_t get(int64_t l, int64_t r){ if (l > node_r || r < node_l) return 0; if (l <= node_l && node_r <= r){ return count; } push(); return left->get(l, r) + right->get(l, r); } }; struct Edge{ int64_t y1, y2; int64_t x; bool open; bool operator<(const Edge& other) const{ if (x == other.x) return open > other.open; return x < other.x; } }; void solve(){ Node root(1, 1e9); int m; cin >> m; int c = 0; for (int i = 0; i < m; i++) { int t, l, r; cin >> t >> l >> r; l += c; r += c; if (t == 1){ c = root.get(l, r); cout << c << '\n'; } else{ root.paint(l, r); } } } int main(){ cin.tie(0); ios_base::sync_with_stdio(0); solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...