#include<bits/stdc++.h> #define ll long long #define DSIZE 1048576 using namespace std; ll n,m,a,b,k; ll wyn; bool D[2*DSIZE][3]; void add(ll a,ll b,ll u,ll lo, ll hi,ll v){ if(a==lo&&b==hi){ D[u][v]=true; return; } if(a>=b) return; if(a<lo||b>hi) return; ll mid = (lo+hi)/2; add(a,min(mid,b),2*u,lo,mid,v); add(max(mid,a),b,2*u+1,mid,hi,v); } bool warunki(ll u){ u+=DSIZE; bool var[3] = {false,false,false}; while(u>0){ if(D[u][0]||var[0]) var[0]=true; if(D[u][1]||var[1]) var[1]=true; if(D[u][2]||var[2]) var[2]=true; u/=2; } if(var[0] && var[1] && !var[2]) return true; else return false; } void policz(){ for(int i=1;i<=n;i++){ if(warunki(i)){ wyn++; } } } void debug(){ int op = 1; for(int i=0;i<=log2(DSIZE);i++){ for(int j=op;j<2*op;j++){ cout<<j<<"/"<<D[j][0]<<"/"<<D[j][1]<<"/"<<D[j][2]<<" "; } cout<<endl; op*=2; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; wyn = 0; for(int i=0;i<m;i++){ cin>>a>>b>>k; add(a-1,b,1,0,DSIZE-1,k-1); } policz(); cout<<wyn; 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 | #include<bits/stdc++.h> #define ll long long #define DSIZE 1048576 using namespace std; ll n,m,a,b,k; ll wyn; bool D[2*DSIZE][3]; void add(ll a,ll b,ll u,ll lo, ll hi,ll v){ if(a==lo&&b==hi){ D[u][v]=true; return; } if(a>=b) return; if(a<lo||b>hi) return; ll mid = (lo+hi)/2; add(a,min(mid,b),2*u,lo,mid,v); add(max(mid,a),b,2*u+1,mid,hi,v); } bool warunki(ll u){ u+=DSIZE; bool var[3] = {false,false,false}; while(u>0){ if(D[u][0]||var[0]) var[0]=true; if(D[u][1]||var[1]) var[1]=true; if(D[u][2]||var[2]) var[2]=true; u/=2; } if(var[0] && var[1] && !var[2]) return true; else return false; } void policz(){ for(int i=1;i<=n;i++){ if(warunki(i)){ wyn++; } } } void debug(){ int op = 1; for(int i=0;i<=log2(DSIZE);i++){ for(int j=op;j<2*op;j++){ cout<<j<<"/"<<D[j][0]<<"/"<<D[j][1]<<"/"<<D[j][2]<<" "; } cout<<endl; op*=2; } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m; wyn = 0; for(int i=0;i<m;i++){ cin>>a>>b>>k; add(a-1,b,1,0,DSIZE-1,k-1); } policz(); cout<<wyn; return 0; } |