#include <bits/stdc++.h> using namespace std; const int pot = 1048576; int d[pot * 2][3]; void Mod(int n, int l, int r, int lo, int hi, int x) { if(l >= r) return; else if(l == lo && r == hi) d[n][x] = 1; else { int mid = (lo + hi) / 2; Mod(n * 2, l, min(r, mid), lo, mid, x); Mod(n * 2 + 1, max(l, mid), r, mid, hi, x); } return; } bool Get(int n, int x) { if(n == 0) return false; if(d[n][x] == true) return true; else { return Get(n / 2, x); } } int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for(int i = 0; i < m; i ++) { int l, r, x; cin >> l >> r >> x; l --; r --; x --; Mod(1, l, r + 1, 0, pot, x); } int wynik = 0; for(int i = 0; i < n; i ++) { if(Get(i + pot, 0) == true && Get(i + pot, 1) == true && Get(i + pot, 2) == false) wynik ++; } cout << wynik; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 | #include <bits/stdc++.h> using namespace std; const int pot = 1048576; int d[pot * 2][3]; void Mod(int n, int l, int r, int lo, int hi, int x) { if(l >= r) return; else if(l == lo && r == hi) d[n][x] = 1; else { int mid = (lo + hi) / 2; Mod(n * 2, l, min(r, mid), lo, mid, x); Mod(n * 2 + 1, max(l, mid), r, mid, hi, x); } return; } bool Get(int n, int x) { if(n == 0) return false; if(d[n][x] == true) return true; else { return Get(n / 2, x); } } int main() { std::ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; for(int i = 0; i < m; i ++) { int l, r, x; cin >> l >> r >> x; l --; r --; x --; Mod(1, l, r + 1, 0, pot, x); } int wynik = 0; for(int i = 0; i < n; i ++) { if(Get(i + pot, 0) == true && Get(i + pot, 1) == true && Get(i + pot, 2) == false) wynik ++; } cout << wynik; return 0; } |