fork download
copy 
  1. /*
  2. * @Author: hungeazy
  3. * @Date:   2026-03-08 10:23:48
  4. * @Last Modified by:   hungeazy
  5. * @Last Modified time: 2026-03-08 11:20:16
  6. */
  7. #include <bits/stdc++.h>
  8. #include <ext/pb_ds/assoc_container.hpp> 
  9. #include <ext/pb_ds/tree_policy.hpp> 
  10. // #pragma GCC optimize("O3")  
  11. // #pragma GCC optimize("unroll-loops")  
  12. // #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")  
  13. using namespace std;
  14. using namespace __gnu_pbds; 
  15. bool M1;
  16. #define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  17. #define int long long
  18. #define ll long long 
  19. #define ull unsigned long long
  20. #define sz(x) x.size()
  21. #define sqr(x) (1LL * (x) * (x))
  22. #define all(x) x.begin(), x.end()
  23. #define fill(f,x) memset(f,x,sizeof(f))
  24. #define FOR(i,l,r) for(int i=l;i<=r;i++)
  25. #define FOD(i,r,l) for(int i=r;i>=l;i--)
  26. #define debug(x) cout << #x << " = " << x << '\n'
  27. #define ii pair<int,int>
  28. #define iii pair<int,ii>
  29. #define di pair<ii,ii>
  30. #define vi vector<int>
  31. #define vii vector<ii>
  32. #define mii map<int,int>
  33. #define fi first
  34. #define se second
  35. #define pb push_back
  36. #define MOD 1000000007
  37. #define __lcm(a,b) (1ll * ((a) / __gcd((a), (b))) * (b))
  38. #define YES cout << "YES\n"
  39. #define NO cout << "NO\n"
  40. #define MASK(i) (1LL << (i))
  41. #define c_bit(i) __builtin_popcountll(i)
  42. #define BIT(x,i) ((x) & MASK(i))
  43. #define SET_ON(x,i) ((x) | MASK(i))
  44. #define SET_OFF(x,i) ((x) & ~MASK(i))
  45. #define oo 1e18
  46. #define name "BANTUQUAN"
  47. #define endl '\n'
  48. #define memory() cerr << abs(&M2-&M1)/1024.0/1024 << " MB" << endl
  49. #define time() cerr << endl << "-------------Time:" << 1000.0 * clock() / CLOCKS_PER_SEC << "ms." << endl
  50. template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
  51. template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
  52. template <class T> using ordered_set = tree <T, null_type, less_equal <T>, rb_tree_tag,tree_order_statistics_node_update>;
  53. const int N = (int)1e5+10;
  54. int n,l,r;
  55. ii a[N];
  56.  
  57. namespace sub1 {
  58.  
  59. 	int pre[N],dp[N];
  60. 	//dp[i] là hiệu số B-G lớn nhất có thể đạt được khi phân nhóm hợp lệ cho i lớp đầu tiên
  61.  
  62. 	bool approved() {
  63. 		return n <= 1e4;
  64. 	}
  65.  
  66. 	int sign(int x) {
  67. 		return (x > 0 ? 1 : x < 0 ? -1 : 0);
  68. 	}
  69.  
  70. 	void solve(void)
  71. 	{
  72. 		FOR(i,1,n) pre[i] = pre[i-1]+a[i].fi-a[i].se;
  73. 		fill(dp,-0x3f);
  74. 		int INF = dp[0];
  75. 		dp[0] = 0;
  76. 		FOR(i,1,n)
  77. 		{
  78. 			int startPos = max(0LL,i-r), endPos = i-l;
  79. 			FOR(j,startPos,endPos)
  80. 				if (dp[j] != INF)
  81. 					maximize(dp[i],dp[j]+sign(pre[i]-pre[j])); 
  82. 		}
  83. 		cout << dp[n];
  84. 	}
  85.  
  86. }
  87.  
  88. namespace sub2 {
  89.  
  90. 	int pre[N],dp[N],INF;
  91.  
  92. 	struct SegmentTree {
  93. 		vi st;
  94. 		vector<multiset<int>> values;
  95. 		int n;
  96.  
  97. 		SegmentTree() {};
  98. 		SegmentTree(int _n): n(_n), st((_n<<2)+1,INF), values(_n+1) {};
  99.  
  100. 		void update(int id, int l, int r, int pos, int val, bool check)
  101. 		{
  102. 			if (l == r)
  103. 			{
  104. 				if (check) values[l].insert(val);
  105. 				else 
  106. 				{
  107. 					auto it = values[l].find(val);
  108. 					if (it != values[l].end()) values[l].erase(it);
  109. 				}
  110. 				if (values[l].empty()) st[id] = INF;
  111. 				else st[id] = *values[l].rbegin();
  112. 				return;
  113. 			}
  114. 			int mid = (l+r)>>1;
  115. 			if (pos <= mid) update(id<<1,l,mid,pos,val,check);
  116. 			else update(id<<1|1,mid+1,r,pos,val,check);
  117. 			st[id] = max(st[id<<1],st[id<<1|1]);
  118. 		} 
  119.  
  120. 		int get(int id, int l, int r, int u, int v)
  121. 		{
  122. 			if (l > v or r < u) return INF;
  123. 			if (l >= u and r <= v) return st[id];
  124. 			int mid = (l+r)>>1;
  125. 			return max(get(id<<1,l,mid,u,v),get(id<<1|1,mid+1,r,u,v));
  126. 		}
  127. 	} IT;
  128.  
  129. 	void solve(void)
  130. 	{
  131. 		vi comp;
  132. 		comp.pb(0);
  133. 		FOR(i,1,n)
  134. 		{
  135. 			pre[i] = pre[i-1]+a[i].fi-a[i].se;
  136. 			comp.pb(pre[i]);
  137. 		} 
  138. 		sort(all(comp));
  139. 		comp.erase(unique(all(comp)),comp.end());
  140. 		auto getId = [&](int val) {
  141. 			return lower_bound(all(comp),val)-comp.begin()+1;
  142. 		};
  143. 		fill(dp,-0x3f);
  144. 		INF = dp[0];
  145. 		dp[0] = 0;
  146. 		int len = sz(comp);
  147. 		IT = SegmentTree(len);
  148. 		FOR(i,1,n)
  149. 		{
  150. 			int jAdd = i-l;
  151. 			if (jAdd >= 0) 
  152. 				IT.update(1,1,len,getId(pre[jAdd]),dp[jAdd],true);
  153. 			int jDel = i-r-1;
  154. 			if (jDel >= 0)
  155. 				IT.update(1,1,len,getId(pre[jDel]),dp[jDel],false);
  156. 			int cur = getId(pre[i]);
  157. 			//pre[j] < pre[i] => dp[j]+1
  158. 			int res1 = IT.get(1,1,len,1,cur-1);
  159. 			// debug(res1);
  160. 			if (res1 != INF) maximize(dp[i],res1+1);
  161. 			//pre[j] = pre[i] => dp[j]
  162. 			int res2 = IT.get(1,1,len,cur,cur);
  163. 			// debug(res2);
  164. 			if (res2 != INF) maximize(dp[i],res2);
  165. 			//pre[j] > pre[i] => dp[j]-1
  166. 			int res3 = IT.get(1,1,len,cur+1,len);
  167. 			// debug(res3);
  168. 			if (res3 != INF) maximize(dp[i],res3-1);
  169. 		}
  170. 		cout << dp[n];
  171. 	}
  172.  
  173. }
  174.  
  175. bool M2;
  176. signed main()
  177. {
  178.     fast;
  179.     if (fopen(name".inp","r"))
  180.     {
  181.     	freopen(name".inp","r",stdin);
  182.     	freopen(name".out","w",stdout);
  183.     }
  184.     cin >> n >> l >> r;
  185.     FOR(i,1,n) cin >> a[i].fi >> a[i].se;
  186.     if (sub1::approved()) return sub1::solve(), time(), memory(), 0;
  187.     sub2::solve();
  188.     time();
  189.     memory();
  190.     return 0;
  191. }
  192. // ██░ ██  █    ██  ███▄    █   ▄████
  193. //▓██░ ██▒ ██  ▓██▒ ██ ▀█   █  ██▒ ▀█▒
  194. //▒██▀▀██░▓██  ▒██░▓██  ▀█ ██▒▒██░▄▄▄░
  195. //░▓█ ░██ ▓▓█  ░██░▓██▒  ▐▌██▒░▓█  ██▓
  196. //░▓█▒░██▓▒▒█████▓ ▒██░   ▓██░░▒▓███▀▒
  197. // ▒ ░░▒░▒░▒▓▒ ▒ ▒ ░ ▒░   ▒ ▒  ░▒   ▒
  198. // ▒ ░▒░ ░░░▒░ ░ ░ ░ ░░   ░ ▒░  ░   ░
  199. // ░  ░░ ░ ░░░ ░ ░    ░   ░ ░ ░ ░   ░
  200. // ░  ░  ░   ░              ░       ░
Success #stdin #stdout #stderr 0.01s 5704KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
-------------Time:7.752ms.
4.57827 MB
https://ideone.com/1eASnr
language:
C++14 (gcc 8.3)
created:
3 hours 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!