fork download
copy 
  1. #pragma GCC target ("avx2")
  2. #pragma GCC optimization ("O3")
  3. #pragma GCC optimization ("unroll-loops")
  4. #include<bits/stdc++.h>
  5. #define int ll
  6. using namespace std;
  7.  
  8. #define all(a) a.begin(),a.end()
  9. #define F first
  10. #define S second
  11. #define pb push_back
  12. #define ll long long
  13. #define vi vector<int>
  14. #define pi pair<int,int>
  15. #define mp make_pair
  16.  
  17. #ifdef LOCAL
  18. #include "debug.h"
  19. #else
  20. #define debug(...) 42
  21. #endif
  22.  
  23. const int mod=1e9+7;
  24.  
  25. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  26.  
  27. int mul(int a,int b)
  28. {
  29. 	return ((a)*1ll*(b))%mod;
  30. }
  31.  
  32. void add(int &a,int b)
  33. {
  34. 	a+=b;
  35. 	if(a>=mod)a-=mod;
  36. }
  37.  
  38. int sub(int a,int b){
  39. 	a-=b;
  40. 	if(a<0){
  41. 		a+=mod;
  42. 	}
  43. 	return a;
  44. }
  45.  
  46. int powz(int a,int b)
  47. {
  48. 	int res=1;
  49. 	while(b)
  50. 	{
  51. 		if(b&1)res=mul(res,a);
  52. 		b/=2;
  53. 		a=mul(a,a);
  54. 	}
  55. 	return res;
  56. }
  57.  
  58. template <typename A, typename B>
  59. istream& operator>>(istream& input,pair<A,B>& x) {
  60. 	input>>x.F>>x.S;
  61. 	return input;
  62. }
  63.  
  64. template <typename A>
  65. istream& operator>>(istream& input,vector<A>& x) {
  66. 	for(auto& i:x)
  67. 		input>>i;
  68. 	return input;
  69. }
  70.  
  71. template<typename A>
  72. ostream& operator<<(ostream& output,vector<A>& x) {
  73. 	for(auto& i:x)
  74. 		output<<i<<' ';
  75. 	return output;
  76. }
  77.  
  78. const int N=500002;
  79.  
  80. vector<pair<int,ll>>rev[N];
  81.  
  82. int lazy[10*N];
  83. pair<int,int> t[10*N];
  84.  
  85. void push(int v) {
  86.     t[v*2].F += lazy[v];
  87.     lazy[v*2] += lazy[v];
  88.     t[v*2+1].F += lazy[v];
  89.     lazy[v*2+1] += lazy[v];
  90.     lazy[v] = 0;
  91. }
  92.  
  93. pair<int,int>merge(pi a,pi b){
  94. 	if(a.F>b.F){
  95. 		return a;
  96. 	}
  97. 	if(b.F>a.F){
  98. 		return b;
  99. 	}
  100. 	return b;
  101. }
  102.  
  103. void update(int v, int tl, int tr, int l, int r, int addend) {
  104.     if (l > r) 
  105.         return;
  106.     if(l==r&&tl==l&&tr==r){
  107. 		t[v].F+=addend;
  108. 		lazy[v]+=addend;
  109. 		return;
  110. 	}
  111.     if (l == tl && tr == r) {
  112.         t[v].F += addend;
  113.         lazy[v] += addend;
  114.     } else {
  115.         push(v);
  116.         int tm = (tl + tr) / 2;
  117.         update(v*2, tl, tm, l, min(r, tm), addend);
  118.         update(v*2+1, tm+1, tr, max(l, tm+1), r, addend);
  119.         t[v] = merge(t[v*2], t[v*2+1]);
  120.     }
  121. }
  122.  
  123. pi query(int v, int tl, int tr, int l, int r) {
  124.     if (l > r)
  125.         return {-1e18,0};
  126.     if (l <= tl && tr <= r)
  127.         return t[v];
  128.     push(v);
  129.     int tm = (tl + tr) / 2;
  130.     return merge(query(v*2, tl, tm, l, min(r, tm)), 
  131.                query(v*2+1, tm+1, tr, max(l, tm+1), r));
  132. }
  133.  
  134. void build(int v,int tl,int tr){
  135. 	if(tl==tr){
  136. 		t[v].S=tl;
  137. 		return;
  138. 	}
  139. 	build(2*v,tl,(tl+tr)/2);
  140. 	build(2*v+1,((tl+tr)/2)+1,tr);
  141. }
  142.  
  143.  
  144. void solve(){
  145. 	int n;
  146. 	ll k;
  147. 	cin>>n>>k;
  148. 	vector<pair<int,int>>abc;
  149. 	for(int i=0;i<n;i++){
  150. 		int l,r;
  151. 		ll p;
  152. 		cin>>l>>r>>p;
  153. 		rev[r].pb({l,p});
  154. 		abc.pb({l,r});
  155. 	}
  156. 	ll ans=0;
  157. 	build(1,1,200000);
  158. 	pair<int,int>opt;
  159. 	for(int i=1;i<=200000;i++){
  160. 		update(1,1,200000,1,i,-k);
  161. 		if(rev[i].size()==0)continue;
  162. 		sort(all(rev[i]));
  163. 		for(int j=rev[i].size()-1;j>=0;j--){
  164. 			update(1,1,200000,1,rev[i][j].F,rev[i][j].S);
  165. 		}
  166. 		pi zz=query(1,1,200000,1,i);
  167. 			ll cost=zz.F,index=zz.S;
  168. 			if(ans<cost){
  169. 				ans=cost;
  170. 				opt={index,i};
  171. 			}
  172. 	}
  173. 	if(ans==0){
  174. 		cout<<0;
  175. 		return;
  176. 	}
  177. 	cout<<ans<<' '<<opt.F<<' '<<opt.S<<' ';
  178. 	vector<int>anss;
  179. 	for(int i=0;i<n;i++){
  180. 		if(abc[i].F>=opt.F&&abc[i].F<=opt.S&&abc[i].S<=opt.S){
  181. 			anss.pb(i+1);
  182. 		}
  183. 	}
  184. 	cout<<anss.size()<<"\n";
  185. 	cout<<anss;
  186. }
  187.  
  188. signed main(){
  189. 	ios_base::sync_with_stdio(false);
  190. 	cin.tie(0);
  191. 	int tc=1;
  192. 	//~ cin>>tc;
  193. 	for(int _=0;_<tc;_++){
  194. 		//~ cout<<"Case #"<<_+1<<": ";
  195. 		solve();
  196. 		if(_!=tc-1)
  197. 		cout<<"\n";
  198. 	}
  199. }
Success #stdin #stdout 0.05s 27620KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/g2j16q
language:
C++14 (gcc 8.3)
created:
5 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!