fork(4) download 
  1. #include <bits/stdc++.h>
  2. // #include "testlib.h"  
  3. using namespace std ;
  4.  
  5. #define ft first
  6. #define sd second
  7. #define pb push_back
  8. #define all(x) x.begin(),x.end()
  9.  
  10. #define ll long long int
  11. #define vi vector<int>
  12. #define vii vector<pair<int,int> >
  13. #define pii pair<int,int>
  14. #define plii pair<pair<ll, int>, int>
  15. #define piii pair<pii, int>
  16. #define viii vector<pair<pii, int> >
  17. #define vl vector<ll>
  18. #define vll vector<pair<ll,ll> >
  19. #define pll pair<ll,ll>
  20. #define pli pair<ll,int>
  21. #define mp make_pair
  22. #define ms(x, v) memset(x, v, sizeof x)
  23.  
  24. #define sc1(x) scanf("%d",&x)
  25. #define sc2(x,y) scanf("%d%d",&x,&y)
  26. #define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
  27.  
  28. #define scll1(x) scanf("%lld",&x)
  29. #define scll2(x,y) scanf("%lld%lld",&x,&y)
  30. #define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
  31.  
  32. #define pr1(x) printf("%d\n",x)
  33. #define pr2(x,y) printf("%d %d\n",x,y)
  34. #define pr3(x,y,z) printf("%d %d %d\n",x,y,z)
  35.  
  36. #define prll1(x) printf("%lld\n",x)
  37. #define prll2(x,y) printf("%lld %lld\n",x,y)
  38. #define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
  39.  
  40. #define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;
  41.  
  42. #define f_in(st) freopen(st,"r",stdin)
  43. #define f_out(st) freopen(st,"w",stdout)
  44.  
  45. #define fr(i, a, b) for(i=a; i<=b; i++)
  46. #define fb(i, a, b) for(i=a; i>=b; i--)
  47. #define ASST(x, l, r) assert( x <= r && x >= l )
  48.  
  49. #include <ext/pb_ds/assoc_container.hpp>
  50. #include <ext/pb_ds/tree_policy.hpp>
  51.  
  52. const int mod = 1e9 + 7;
  53.  
  54. int ADD(int a, int b, int m = mod) {
  55.     int s = a;
  56.     s += b;
  57.     if( s >= m )
  58.       s -= m;
  59.     return s;
  60. }
  61.  
  62. int MUL(int a, int b, int m = mod) {
  63.     return (1LL * a * b % m);
  64. }
  65.  
  66. int power(int a, int b, int m = mod) {
  67.     int res = 1;
  68.     while( b ) {
  69.         if( b & 1 ) {
  70.             res = 1LL * res * a % m;
  71.         }
  72.         a = 1LL * a * a % m;
  73.         b /= 2;
  74.     }
  75.     return res;
  76. }
  77.  
  78. ll nC2(ll x) {
  79.     return ( x * ( x - 1 ) / 2 );
  80. }
  81.  
  82. const int maxn = 1e5 + 5;
  83.  
  84. int n, q;
  85. vi adj[ maxn ];
  86. ll color[ maxn ];
  87.  
  88. int get( ll x ) {
  89. 	int c = 0;
  90. 	while( x ) {
  91. 		c ++;
  92. 		x -= (x & -x);
  93. 	}
  94. 	return c;
  95. }
  96.  
  97. void dfs( int u, int p, int k, int lev ) {
  98. 	if( lev > k ) return;
  99. 	color[ u ] = (1LL << lev);
  100. 	for( auto it: adj[u] ) {
  101. 		if( it != p ) {
  102. 			dfs(it, u, k, lev + 1);
  103. 		}
  104. 	}
  105. }
  106.  
  107. ll range(int l, int r) {
  108. 	ll ans = 0;
  109. 	while( l <= r ) {
  110. 		ans |= color[ l ];
  111. 		l ++;
  112. 	}
  113. 	return ans;
  114. }
  115.  
  116. int main() {
  117. 	cin >> n >> q;
  118. 	int i;
  119. 	fr(i, 1, n) {
  120. 		int x, y;
  121. 		x = i; y = 2 * x;
  122. 		if( y <= n ) adj[x].pb( y ), adj[y].pb( x );
  123. 		x = i; y = 2 * x + 1;
  124. 		if( y <= n ) adj[x].pb( y ), adj[y].pb( x );
  125. 	}
  126.  
  127. 	while( q-- ) {
  128. 		int t, x, y, k; sc1( t );
  129. 		if( t == 1 ) {
  130. 			sc2( x, k ); 
  131. 			dfs( x, 0, k, 0);
  132. 		} else if( t == 2 ) {
  133. 			sc2(x, y);
  134. 			ll ans = 0; 
  135. 			while( x != y ) {
  136. 				if( x < y ) {
  137. 					ans |= color[ y ];
  138. 					y /= 2;
  139. 				} else {
  140. 					ans |= color[ x ];
  141. 					x /= 2;
  142. 				}
  143. 			}
  144. 			ans |= color[ x ];
  145. 			ans -= ans % 2;
  146. 			pr1( get( ans ) );
  147. 		} else {
  148. 			sc1( x );
  149. 			int l, r; ll ans = 0;
  150. 			l = r = x;
  151. 			while( l <= r ) {
  152. 				ans |= range(l, r);
  153. 				l *= 2; r = r * 2 + 1;
  154. 				r = min(n, r);
  155. 			}
  156. 			ans -= ans % 2;
  157. 			pr1( get( ans ) );
  158. 		}
  159. 	}
  160. 	return 0;
  161. }
Success #stdin #stdout 0s 5412KB
comments ()
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/a1wAJF
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!