fork(1) download 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <map>
  4. #include <vector>
  5. #include <time.h>
  6. #include <utility>
  7. #include <cmath>
  8. #include <set>
  9. #include <cstring>
  10. #include <queue>
  11. #include <algorithm>
  12. using namespace std;
  13.  
  14. #define ll long long int
  15. #define ipair pair<ll, ll>
  16. #define mod 1000000007
  17. #define pb push_back
  18. #define mp make_pair
  19. #define ff first
  20. #define ss second
  21. #define rep(i,n) for(i=0;i<n;i++)
  22. #define fu(i,a,n) for(i=a;i<=n;i++)
  23. #define fd(i,n,a) for(i=n;i>=a;i--)
  24. #define gi(n) scanf("%d",&n)
  25. #define gl(n) scanf("%lld",&n)
  26. #define pl(n) printf("%lld",n)
  27. #define pi(n) printf("%d",n)
  28. #define pp printf(" ")
  29. #define pn printf("\n")
  30. #define MAX 500000
  31. #define LN 60
  32.  
  33. ll ctr;
  34. struct node2 {
  35. 	ll cont;
  36. 	ll val;	// count
  37. 	ll lc;
  38. 	ll rc;
  39. 	node2(ll con, ll c, ll l, ll r) {
  40. 		cont = con;
  41. 		val = c;
  42. 		lc = l;
  43. 		rc = r;
  44. 	}
  45. 	node2() {
  46. 		cont = val = lc = rc = 0;
  47. 	}
  48. } seg[MAX * LN * 2];
  49.  
  50.  
  51. void update(ll &node, ll start, ll end, ll id) {
  52. 	if(!node) {
  53. 		node = ++ctr;
  54. 	}
  55. 	if(start^end) {
  56. 		ll mid = (start + end) >> 1;
  57. 		if(id <= mid) {
  58. 			update(seg[node].lc, start, mid, id);
  59. 		}
  60. 		else {
  61. 			update(seg[node].rc, mid + 1, end, id);
  62. 		}
  63. 		ll p = seg[node].lc;
  64. 		ll q = seg[node].rc;
  65. 		seg[node].val = seg[p].val + seg[q].val;
  66. 		if(seg[p].cont == mid + 1 - start) {
  67. 			seg[node].cont = seg[p].cont + seg[q].cont;
  68. 		}
  69. 		else {
  70. 			seg[node].cont = seg[p].cont;
  71. 		}
  72. 	}
  73. 	else {
  74. 		seg[node].val = 1;
  75. 		seg[node].cont = 1;
  76. 	}
  77. }
  78.  
  79. ll query(ll node, ll start, ll end, ll r) {
  80. 	if(!node) {
  81. 		// return min(end, r);
  82. 		return r;
  83. 	}
  84. 	if(start == end) {
  85. 		return 0;
  86. 	}
  87. 	ll mid = (start + end) >> 1;
  88. 	ll rig = seg[node].rc;
  89. 	ll en = min(end, r);
  90. 	// if(r <= mid || (en - mid <= seg[rig].cont)) {
  91. 	// 	return query(seg[node].lc, start, mid, r);
  92. 	// }
  93. 	// return query(seg[node].rc, mid + 1, end, r);
  94. 	if(r <= mid || (r - mid <= seg[rig].cont)) {
  95. 		return query(seg[node].lc, start, mid, mid);
  96. 	}
  97. 	return query(seg[node].rc, mid + 1, end, r);
  98. }
  99.  
  100. int main() {
  101. 	int t;
  102. 	gi(t);
  103. 	while(t--) {
  104. 		ll n, q;
  105. 		gl(n);
  106. 		gl(q);
  107. 		ll root = 0;
  108. 		ll s = 0;
  109. 		while(q--) {
  110. 			int ch;
  111. 			gi(ch);
  112. 			if(ch == 1) {
  113. 				ll x;
  114. 				gl(x);
  115. 				x+=s;
  116. 				update(root, 1, n, x);
  117. 			}
  118. 			else {
  119. 				ll l, r;
  120. 				gl(l);
  121. 				gl(r);
  122. 				l+=s;
  123. 				r+=s;
  124. 				// ll ans = query(root, 1, n, r);
  125. 				ll ans = query(root, 1, n, min(r,n));
  126. 				if(ans < l) {
  127. 					ans = 0;
  128. 				}
  129. 				s = (s + ans)%n;
  130. 				pl(ans);
  131. 				pn;
  132. 			}
  133. 		}
  134. 		ll i;
  135. 		fu(i, 1, ctr) {
  136. 			seg[i].lc = seg[i].rc = seg[i].val = seg[i].cont = 0;
  137. 		}
  138. 		ctr = 0;
  139. 	}
  140.  
  141. 	return 0;
  142. }
Success #stdin #stdout 0.36s 1890304KB
comments (?)
stdin 
1
6 3
1 4
1 5
2 1 5
stdout 
3
https://ideone.com/X17kon
language:
C++14 (gcc 8.3)
created:
6 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!