fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define ll long long
  6. #define ull unsigned ll
  7. #define ld long double
  8. typedef vector<int> vi;
  9. typedef multiset<int> mi;
  10. typedef multiset<ll> mll;
  11. typedef vector<ll> vll;
  12. typedef vector<bool> vb;
  13. typedef vector<string> vs;
  14. typedef set<ll> sll;
  15. typedef vector<vector<int>> _2vi;
  16. typedef vector<vector<ll>> _2vll;
  17. #define all(v) ((v).begin()), ((v).end())
  18. #define sz(v) ((ll)((v).size()))
  19.  
  20. #define vinp(v, n)                \
  21.     for (ull i = 0; i < (n); i++) \
  22.     cin >> (v)[i]
  23. #define printv(v)      \
  24.     for (auto i : (v)) \
  25.     cout << i << " "
  26. #define fr0(i, n) for (ull(i) = 0; (i) < (n); (i)++)
  27. #define fr1(i, n) for (ull(i) = 1; (i) < (n); (i)++)
  28. #define fr(i, x, n) for (ull(i) = (x); (i) < (n); (i)++)
  29. #define _CRT_SECURE_NO_WARNING
  30. const ll MOD = 1000000007;
  31.  
  32. void Bustany() {
  33.     ios_base::sync_with_stdio(false);
  34.     cin.tie(NULL);
  35.     cout.tie(NULL);
  36. #ifndef ONLINE_JUDGE
  37.     freopen("./in.txt", "r", stdin), freopen("./out.txt", "w", stdout);
  38. #endif
  39. }
  40.  
  41. const ll N = 1e5 + 5;
  42. vector<sll> adj(N);
  43. //_2vll adj(N,vll(N));
  44. vb vis;
  45. #define int ll
  46.  
  47. struct FenwickTreeOneBasedIndexing {
  48.     vector<int> bit;  // binary indexed tree
  49.     int n;
  50.  
  51.     FenwickTreeOneBasedIndexing(int n) {
  52.         this->n = n + 1;
  53.         bit.assign(n + 1, 0);
  54.     }
  55.  
  56. //    FenwickTreeOneBasedIndexing(vector<int> a)
  57. //            : FenwickTreeOneBasedIndexing(a.size()) {
  58. ////        bit.resize(a.size());
  59. ////        for (size_t i = 0; i < a.size(); i++)
  60. ////            add(i, a[i]);
  61. //    }
  62.  
  63.     int sum(int idx) {
  64.         int ret = 0;
  65.         for (++idx; idx > 0; idx -= idx & -idx)
  66.             ret += bit[idx];
  67.         return ret;
  68.     }
  69.  
  70.     int sum(int l, int r) {
  71.         return sum(r) - sum(l - 1);
  72.     }
  73.  
  74.     void add(int idx, int val) {
  75.         for (++idx; idx < n; idx += idx & -idx)
  76.             bit[idx] += val;
  77.     }
  78.  
  79.     void range_add(int l, int r, int val) {
  80.         add(l, val);
  81.         add(r + 1, -val);
  82.     }
  83.  
  84.     int point_query(int idx) {
  85.         int ret = 0;
  86.         for (++idx; idx > 0; idx -= idx & -idx)
  87.             ret += bit[idx];
  88.         return ret;
  89.     }
  90. };
  91.  
  92. #undef int
  93. ll SKIP_VALUE = 0;
  94.  
  95. #define int long long
  96.  
  97. struct Node {
  98.     int val, lazy;
  99.     bool isLazy;
  100.  
  101.     Node(int val = SKIP_VALUE, int lazy = 0, bool isLazy = false) : val(val), lazy(lazy), isLazy(isLazy) {}
  102. };
  103.  
  104. class SegmentTree {
  105. private:
  106.     vector<Node> tree;
  107.     ll sz;
  108.  
  109. #define mid ((r + l) >> 1)
  110. #define L node * 2 + 1
  111. #define R node * 2 + 2
  112.  
  113.     Node merge(Node a, Node b) {
  114.         return Node(a.val + b.val);
  115.     }
  116.  
  117.     Node build(ll l, ll r, ll node, vector<ll> &a) {
  118.         if (l == r) {
  119.             if (l < (int) a.size()) return (tree[node] = Node(a[l]));
  120.             return Node();
  121.         }
  122.  
  123.         return tree[node] = merge(build(l, mid, L, a), build(mid + 1, r, R, a));
  124.     }
  125.  
  126.     // apply lazy on the node
  127.     void apply(int l, int r, int node) {
  128.         tree[node].val = (r - l + 1) * tree[node].lazy;
  129.         tree[node].lazy = 0;
  130.         tree[node].isLazy = 0;
  131.     }
  132.  
  133.     // add val on to lazy of the node
  134.     void push(int node, int val) {
  135.         tree[node].lazy = val;
  136.         tree[node].isLazy = 1;
  137.     }
  138.  
  139.     void propegate(ll l, ll r, ll node) {
  140.         if (!tree[node].isLazy) return;
  141.  
  142.         if (l != r) {
  143.             push(L, tree[node].lazy);
  144.             push(R, tree[node].lazy);
  145.         }
  146.  
  147.         apply(l, r, node);
  148.     }
  149.  
  150.     void update(ll l, ll r, ll node, ll tl, ll tr, ll val) {
  151.         propegate(l, r, node);
  152.  
  153.         if (l > tr || r < tl) return;
  154.  
  155.         if (l >= tl && r <= tr) {
  156.             push(node, val);
  157.             propegate(l, r, node);
  158.             return;
  159.         }
  160.  
  161.         update(l, mid, L, tl, tr, val);
  162.         update(mid + 1, r, R, tl, tr, val);
  163.  
  164.         tree[node] = merge(tree[L], tree[R]);
  165.     }
  166.  
  167.     Node query(ll l, ll r, ll node, ll tl, ll tr) {
  168.         propegate(l, r, node);
  169.  
  170.         if (tl > r || tr < l) return Node();
  171.         if (l >= tl && r <= tr)
  172.             return tree[node];
  173.  
  174.         return merge(
  175.                 query(l, mid, L, tl, tr),
  176.                 query(mid + 1, r, R, tl, tr)
  177.         );
  178.     }
  179.  
  180. public:
  181.     SegmentTree(vector<ll> &a) {
  182.         ll n = (int) a.size();
  183.         sz = 1;
  184.         while (sz <= n) sz *= 2;
  185.  
  186.         tree = vector<Node>(sz << 1);
  187.  
  188.         build(0, sz - 1, 0, a);
  189.     }
  190.  
  191.     SegmentTree(ll n) {
  192.         sz = 1;
  193.         while (sz < n) sz <<= 1;
  194.         tree = vector<Node>(sz << 1, Node(SKIP_VALUE));
  195.     }
  196.  
  197.     void update(ll l, ll r, ll val) { // add value to range [l, r]
  198.         update(0, sz - 1, 0, l, r, val);
  199.     }
  200.  
  201.     ll query(ll l, ll r) {
  202.         return query(0, sz - 1, 0, l, r).val;
  203.     }
  204.  
  205. #undef R
  206. #undef L
  207. #undef mid
  208. };
  209.  
  210. #undef int
  211.  
  212.  
  213. struct a {
  214.     ll x1, x2, y;
  215. };
  216.  
  217.  
  218. void solve() {
  219.     ll n, q;
  220.     cin >> n >> q;
  221.     vector<a> v(q);
  222.     for (ll i = 0; i < q; i++) {
  223.         cin >> v[i].x1 >> v[i].x2 >> v[i].y;
  224.     }
  225.     sort(all(v), [&](auto f, auto s) {
  226.         return f.y < s.y;
  227.     });
  228.     SegmentTree lazy(n);
  229.     lazy.update(0, n - 1, 1);
  230.     for (ll i = 0; i < q; i++) {
  231.         auto [x1, x2, y] = v[i];
  232.         x1--;
  233.         x2--;
  234.         if (x2 - x1 > 1) {
  235.             if (lazy.query(x1, x2) >= 1) {
  236.                 lazy.update(x1 + 1, x2 - 1, 0);
  237.                 lazy.update(x1, x1, 1);
  238.                 lazy.update(x2, x2, 1);
  239.             }
  240.         }
  241.     }
  242.     cout << lazy.query(0, n - 1) << endl;
  243. }
  244.  
  245. int main() {
  246.     Bustany();
  247.     ll t = 1;
  248.     cin >> t;
  249.     while (t--) {
  250.         solve();
  251.     }
  252. }
Success #stdin #stdout 0.01s 7652KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Cpk8XI
language:
C++ (gcc 8.3)
created:
21 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!