fork(1) download
copy 
  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. int get( ll x ) {
  83. 	int c = 0;
  84. 	while( x ) {
  85. 		c ++;
  86. 		x -= (x & -x);
  87. 	}
  88. 	return c;
  89. }
  90.  
  91. const int maxn = 1e5 + 5;
  92.  
  93. int n,m;
  94. ll Tree[4*maxn];
  95. ll Lazy[4*maxn][4];
  96.  
  97. void adjust(int i,int lo,int hi) {
  98.     int mid = (lo+hi) >> 1;
  99.     if (Lazy[i][3]!=mod) {
  100.         ll x = Lazy[i][3]; Lazy[i][3]=mod;
  101.         Tree[2*i] = x; Lazy[2*i][3] = x;
  102.         Tree[2*i+1] = x; Lazy[2*i+1][3] = x;
  103.     }
  104. }
  105.  
  106. void update(int i,int lo,int hi,int u,int v,int type,ll x) {
  107.     if (v<lo || hi<u) return;
  108.     if (u<=lo && hi<=v) {
  109.         Tree[i] = x;
  110.         Lazy[i][3] = x;
  111.         return;
  112.     }
  113.     int mid = (lo+hi) >> 1;
  114.     if (Lazy[i][3]!=mod) adjust(i,lo,hi);
  115.     update(2*i,lo,mid,u,v,type,x);
  116.     update(2*i+1,mid+1,hi,u,v,type,x);
  117.     Tree[i] = (Tree[2*i]|Tree[2*i+1]);
  118. }
  119.  
  120. ll query(int i,int lo,int hi,int u,int v) {
  121.     if (v<lo || hi<u) return 0;
  122.     if (u<=lo && hi<=v) return Tree[i];
  123.     int mid = (lo+hi) >> 1;
  124.     if (Lazy[i][3]!=mod) adjust(i,lo,hi);
  125.     return (query(2*i,lo,mid,u,v) | query(2*i+1,mid+1,hi,u,v));
  126. }
  127.  
  128. void init(int i,int lo,int hi) {
  129.     Tree[i]=0;
  130.     Lazy[i][3]=mod;
  131.     if (lo==hi) return;
  132.     int mid = (lo+hi) >> 1;
  133.     init(2*i,lo,mid);
  134.     init(2*i+1,mid+1,hi);
  135. }
  136.  
  137. void solve() {
  138. 	sc2( n, m );
  139. 	init(1, 1, n);
  140. 	int t, x, l, r, z, c, y, k, K;
  141. 	ll ans = 0;
  142. 	while( m -- ) {
  143. 		sc1( t );
  144. 		if( t == 1 ) {
  145. 			sc2( x, K );
  146. 			z = x; c = 0;
  147. 			while( z ) {
  148. 				if( z != x && c <= K ) {
  149. 					update(1, 1, n, z, z, 3, (1LL << c));
  150. 					if( z * 2 == x )
  151. 						l = r = 2 * z + 1;
  152. 					else 
  153. 						l = r = 2 * z;
  154. 					k = c + 1;
  155. 				} else {
  156. 					l = r = x;
  157. 					k = c;
  158. 				}
  159. 				r = min(r, n);
  160. 				while( l <= r && k <= K ) {
  161. 					update(1, 1, n, l, r, 3, (1LL << k));
  162. 					k ++; l *= 2; r = r * 2 + 1;
  163. 					r = min(r, n); 
  164. 				}
  165. 				x = z;
  166. 				z = z / 2;
  167. 				c ++;
  168. 			}
  169. 		} else if( t == 2 ) {
  170. 			sc2(x, y); ans = 0;
  171. 			while( x != y ) {
  172. 				if( x < y ) {
  173. 					ans |= query(1, 1, n, y, y);
  174. 					y /= 2;
  175. 				} else {
  176. 					ans |= query(1, 1, n, x, x);
  177. 					x /= 2;
  178. 				}
  179. 			}
  180. 			ans |= query(1, 1, n, x, x);
  181. 			ans -= ans % 2;
  182. 			pr1( get( ans ) );
  183. 		} else {
  184. 			sc1(x);
  185. 			ans = 0;
  186. 			l = r = x;
  187. 			while( l <= r ) {
  188. 				ans |= query(1, 1, n, l, r);
  189. 				l *= 2;
  190. 				r = r * 2 + 1;r = min(r, n);
  191. 			}
  192. 			ans -= ans % 2;
  193. 			pr1( get( ans ) );
  194. 		}
  195. 	}
  196. }
  197.  
  198.  
  199. int main() {
  200. 	solve();
  201. 	return 0;
  202. }
Runtime error #stdin #stdout 0s 19088KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pLOTjy
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!