fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. template <typename T> bool maximize(T &res, const T &val){if(res < val) return res = val, true; return false;}
  6. template <typename T> bool minimize(T &res, const T &val){if(res > val) return res = val, true; return false;}
  7.  
  8. #define ll long long
  9. #define fi first
  10. #define se second
  11. #define pb push_back
  12. #define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)
  13. #define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; i--)
  14. #define REP(i, n) for(int i = 0, _n = (n); i < _n; i++)
  15. #define C make_pair
  16. #define MASK(i) (1LL << (i))
  17. #define TURN_ON(i, x) ((x) | MASK(i))
  18. #define TURN_OFF(i, x) ((x) & ~MASK(i))
  19. #define RE(i, x) ((x) ^ MASK(i))
  20.  
  21. const ll mod = 918052004;
  22. const ll INF = 1e15;
  23. typedef pair<int, int> pi;
  24. typedef pair<int, pair<int,int>> pii;
  25. typedef pair<ll, ll> pl;
  26. typedef pair<ll, pair<ll,ll>>pll;
  27.  
  28. struct edge{
  29.     int u,v,w;
  30.     edge(int u = 0, int v = 0, int w = 0)
  31.     {
  32.         this->u = u;
  33.         this->v = v;
  34.         this->w = w;
  35.     }
  36. };
  37. struct matrix{
  38.     ll val[3][3];
  39.     matrix(){
  40.         memset(val, 0, sizeof(val));
  41.     }
  42. };
  43.  
  44. const int maxn = 181000;
  45.  
  46. ll t, n, m, L, R, a[maxn];
  47.  
  48. void add(ll &a, ll b){
  49. 	a += b;
  50. 	if(a >= mod) a -= mod;
  51. }
  52. namespace sub1{
  53. 	bool check(){
  54. 		return n <= 185;
  55. 	}
  56. 	const int limit = (int)185;
  57. 	ll dp[limit + 10][limit + 10], ans;
  58. 	bool mark[limit + 10];
  59.  
  60. 	void solve(){
  61. 		dp[0][L] = 1;
  62. 		FOR(i, 1, n){
  63. 			memset(mark, 0, sizeof(mark));
  64. 			int cnt = 0;
  65. 			FORD(j, i, 1){
  66. 				if(!mark[a[j]]){
  67. 					mark[a[j]] = 1;
  68. 					cnt++;
  69. 				}
  70. 				if(cnt > R) break;
  71. 				if(cnt < L) continue;
  72. 				FOR(g, L, R) add(dp[i][cnt], dp[j - 1][g]);
  73. 			}
  74. 		}
  75. 		FOR(i, L, R) add(ans, dp[n][i]);
  76. 		cout << ans << '\n';
  77. 		memset(dp, 0, sizeof(dp));
  78. 		ans = 0;
  79. 	}
  80. }
  81. namespace sub2{
  82. 	bool check(){
  83. 		return n <= (int)1805;
  84. 	}
  85. 	const int limit = (int)1805;
  86. 	ll dp[limit + 10][limit + 10], sum[limit + 10], ans;
  87. 	bool mark[limit + 10];
  88. 	void solve(){
  89. 		sum[0] = 1;
  90. 		FOR(i, 1, n){
  91. 			memset(mark, 0, sizeof(mark));
  92. 			int cnt = 0;
  93. 			FORD(j, i, 1){
  94. 				if(!mark[a[j]]){
  95. 					cnt++;
  96. 					mark[a[j]] = 1;
  97. 				}
  98. 				if(cnt > R) break;
  99. 				if(cnt < L) continue;
  100. 				add(dp[i][cnt], sum[j - 1]);
  101. 			}
  102. 			FOR(j, L, R) add(sum[i], dp[i][j]);
  103. 		}
  104. 		FOR(i, L, R) add(ans, dp[n][i]);
  105. 		cout << ans << '\n';
  106. 		memset(dp, 0, sizeof(dp));
  107. 		memset(sum, 0, sizeof(sum));
  108. 		ans = 0;
  109. 	}
  110. }
  111. namespace sub3{
  112. 	const int limit = (int)180504;
  113. 	ll dp[limit + 10], sum[limit + 10], BIT[limit + 10], last_pos[limit + 10];
  114.  
  115. 	void update(int x, int val){
  116. 		for(; x <= limit; x += x & -x) BIT[x] += val;
  117. 	}
  118. 	ll get(int x){
  119. 		ll s = 0;
  120. 		for(; x > 0; x -= x & -x) s += BIT[x];
  121. 		return s;
  122. 	}
  123. 	int get_R(int i){
  124. 		int l = 1, r = i, ans = -1;
  125. 		while(l <= r){
  126. 			int mid = (l + r) >> 1;
  127. 			int val = get(i) - get(mid - 1);
  128. 			if(val >= L) l = mid + 1;
  129. 			else{
  130. 				ans = mid;
  131. 				r = mid - 1;
  132. 			}
  133. 		}
  134. 		return ans;
  135. 	}
  136. 	int get_L(int i){
  137. 		int l = 1, r = i, ans = -1;
  138. 		while(l <= r){
  139. 			int mid = (l + r) >> 1;
  140. 			int val = get(i) - get(mid - 1);
  141. 			if(val > R){
  142. 				ans = mid;
  143. 				l = mid + 1;
  144. 			}
  145. 			else r = mid - 1;
  146. 		}
  147. 		return ans;
  148. 	}
  149. 	void solve(){
  150. 		FOR(i, 0, n + 3){
  151. 			dp[i] = 0;
  152. 			sum[i] = 0;
  153. 			last_pos[i] = 0;
  154. 			BIT[i] = 0;
  155. 		}
  156. 		sum[1] = 1;
  157. 		int tmp1 = 1, tmp2 = 1;
  158. 		FOR(i, 1, n){
  159. 			update(i, 1);
  160. 			if(last_pos[a[i]]){
  161. 				update(last_pos[a[i]], -1);
  162. 			}
  163. 			last_pos[a[i]] = i;
  164. 			sum[i + 1] += sum[i];
  165. 			int val = get(i) - get(tmp1 - 1);
  166. 			if(val < L) continue;
  167. 			while(val > R){
  168. 				tmp1++;
  169. 				val = get(i) - get(tmp1 - 1);
  170. 			}
  171. 			val = get(i) - get(tmp2 - 1);
  172. 			while(val >= L){
  173. 				tmp2++;
  174. 				val = get(i) - get(tmp2 - 1);
  175. 			}
  176. 			tmp2--;
  177. 			add(dp[i], (sum[tmp2] - sum[tmp1 - 1] + mod) % mod);
  178. 			add(sum[i + 1], dp[i]);
  179. 		}
  180. 		cout << dp[n] << '\n';
  181. 	}
  182. }
  183. int main(){
  184. 	//freopen("team.inp", "r", stdin);
  185. 	//freopen("team.out", "w", stdout);
  186. 	ios_base::sync_with_stdio(0);
  187. 	cin.tie(0); cout.tie(0);
  188. 	cin >> t;
  189. 	while(t--){
  190. 		cin >> n >> m >> L >> R;
  191. 		FOR(i, 1, n) cin >> a[i];
  192. 		//if(sub1::check()) sub1::solve();
  193. 		//else if(sub2::check()) sub2::solve();
  194. 		//else sub3::solve();
  195. 		sub1::solve();
  196. 		sub3::solve();
  197. 	}
  198. }
Success #stdin #stdout 0.01s 9772KB
comments (?)
stdin
copy 
9
1 1 1 1
1
2 1 1 1
1 1
2 2 1 2
1 2
2 2 1 2
2 1
2 2 1 2
2 2
2 2 2 2
1 1
2 2 2 2
1 2
2 2 2 2
2 1
2 2 2 2
2 2
stdout
copy 
1
1
2
2
2
2
2
2
2
2
0
0
1
1
1
1
0
0
https://ideone.com/0LaMqZ
language:
C++14 (gcc 8.3)
created:
8 days ago
visibility:
public

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!