Advertisement
Guest User

Untitled

a guest
Oct 24th, 2014
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4.  
  5. const int N = (int)(1e5 + 100);
  6.  
  7. int shr;
  8.  
  9. int t[4 * N], n, m, L[N], R[N], Q[N], used[4 * N];
  10.  
  11. void into(int v)
  12. {
  13.     if(!used[v]) return;
  14.     else if(used[v])
  15.     {
  16.         used[v] = 0;
  17.         used[v + v] = used[v + v + 1] = 1;
  18.         t[v + v] |= t[v], t[v + v + 1] |= t[v];
  19.     }
  20. }
  21.  
  22. void update(int v, int tl, int tr, int l, int r, int x)
  23. {
  24.     if(l > r)
  25.         return;
  26.     if(tl == l && tr == r)
  27.     {
  28.     //  cerr << l << ' ' << r << ' ' << t[v] << ' ' << (t[v] | x) << endl;
  29.         t[v] |= x;
  30.         used[v] = 1;
  31.         return;
  32.     }  
  33.     into(v);
  34.     int mid = (tl + tr) / 2;  
  35.     update(v + v, tl, mid, l, min(r, mid), x);
  36.     update(v + v + 1, mid + 1, tr, max(l, mid + 1), r, x);
  37.     t[v] = t[v + v] & t[v + v + 1];
  38. }
  39.  
  40. int getand(int v, int tl, int tr, int l, int r)
  41. {                          
  42.     if(l <= r)
  43.     {
  44.         if(tl == l && tr == r)
  45.             return t[v];
  46.         int mid = (tl + tr) / 2;
  47.         into(v);
  48. //      cerr << l << ' ' << r << ' ' << tl << ' ' << tr << ' ' << getand(v + v, tl, mid, l, min(r, mid)) << ' ' << getand(v + v + 1, mid + 1, tr, max(l, mid + 1), r) << endl;
  49.         return getand(v + v, tl, mid, l, min(r, mid)) & getand(v + v + 1, mid + 1, tr, max(l, mid + 1), r);
  50.     }
  51.     return shr;
  52. }
  53. int main()
  54. {
  55.     ios::sync_with_stdio(0);
  56.     cin.tie(0);
  57.     cin >> n >> m;
  58.     shr = (1 << 31) - 1;
  59.    
  60.     for(int i = 0; i < m; ++i)
  61.     {
  62.         cin >> L[i] >> R[i] >> Q[i];
  63.         update(1, 1, n, L[i], R[i], Q[i]);
  64.     }
  65.    
  66.    
  67.     for(int i = 0; i < m; ++i)
  68.         if(getand(1, 1, n, L[i], R[i]) != Q[i])
  69.         {
  70.             cout << "NO";
  71.             return 0;
  72.         }
  73.    
  74.     cout << "YES\n";
  75.    
  76.     for(int i = 1; i <= n; ++i)
  77.     {
  78.         cout << getand(1, 1, n, i, i) << ' ';
  79.     }
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement