fork download 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12.  
  13. typedef long long ll;
  14. typedef pair<ll,ll> ii;
  15. typedef vector<int> vi;
  16. typedef long double ld; 
  17. typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  18.  
  19. int L[1111111];
  20. ll dp[1111111];
  21. int par[1111111];
  22. int leftmost[1111111];
  23.  
  24. int rt(int u)
  25. {
  26. 	vi vec;
  27. 	while(par[u]>=0)
  28. 	{
  29. 		vec.pb(u);
  30. 		u=par[u];
  31. 	}
  32. 	for(int v:vec) par[v]=u;
  33. 	return u;
  34. }
  35.  
  36. void merge(int u, int v)
  37. {
  38. 	u=rt(u); v=rt(v);
  39. 	if(u==v) return ;
  40. 	if(par[u]>par[v]) swap(u,v);
  41. 	par[u]+=par[v]; par[v]=u;
  42. 	leftmost[u]=min(leftmost[u],leftmost[v]);
  43. }
  44.  
  45. bool cmp(ii a, ii b)
  46. {
  47. 	if(a.se!=b.se) return a.se<b.se;
  48. 	return a.fi<b.fi;
  49. }
  50.  
  51. int lmin[1111111];
  52. int t[4141414];
  53.  
  54. void build(vector<ii> &stones) 
  55. {  // build the tree
  56. 	int n=stones.size();
  57. 	for(int i=n;i<2*n;i++) t[i] = stones[i-n].se;
  58. 	for (int i = n - 1; i > 0; --i) t[i] = max(t[i<<1], t[i<<1|1]);
  59. }
  60.  
  61. void modify(int n, int p, int v) {  
  62.   for (t[p += n] = v; p > 1; p >>= 1) t[p>>1] = max(t[p], t[p^1]);
  63. }
  64.  
  65. int query(int n, int l, int r) {  
  66.   int res = 0;
  67.   for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
  68.     if (l&1) res = max(res, t[l++]);
  69.     if (r&1) res = max(res, t[--r]);
  70.   }
  71.   return res;
  72. }
  73.  
  74. map<ll,int> ma;
  75.  
  76. void add(ll x){ma[x]++;}
  77. void del(ll x){ma[x]--; if(ma[x]==0){ma.erase(x);}}
  78.  
  79. int main()
  80. {
  81. 	ios_base::sync_with_stdio(0); cin.tie(0);
  82. 	freopen("fossil_fuels.txt","r",stdin); freopen("fossil_fuels.out","w",stdout);
  83. 	int tc; cin>>tc;
  84. 	for(int zz=0;zz<tc;zz++)
  85. 	{
  86. 		cout<<"Case #"<<zz+1<<": ";
  87. 		int n; ll s,m; int k; cin>>n>>s>>m>>k;
  88. 		memset(par,-1,sizeof(par)); 
  89. 		for(int i=0;i<=1011111;i++) leftmost[i] = i;
  90. 		vector<ii> stones(n); int ptr1=0; int ptr2=0;
  91. 		for(int i=0;i<2*k;i++)
  92. 		{
  93. 			ll len; cin>>len;
  94. 			vector<ll> vec; ll zzz; cin>>zzz; vec.pb(zzz);
  95. 			ll x,y,z; cin>>x>>y>>z;
  96. 			for(int j=1;j<len;j++)
  97. 			{
  98. 				vec.pb(((vec.back()*x)+y)%z + 1);
  99. 				while(vec.back()<=0) vec.back()+=z;
  100. 			}
  101. 			if(i<k)
  102. 			{
  103. 				for(int j=0;j<len;j++)
  104. 				{
  105. 					stones[ptr1++].fi = vec[j];
  106. 				}
  107. 			}
  108. 			else
  109. 			{
  110. 				for(int j=0;j<len;j++)
  111. 				{
  112. 					stones[ptr2++].se = vec[j];
  113. 				}
  114. 			}
  115. 		}
  116. 		sort(stones.begin(),stones.end());
  117. 		memset(L,0,sizeof(L));
  118. 		int ptrl = 0;
  119. 		for(int i=0;i<n;i++)
  120. 		{
  121. 			while(stones[i].fi-stones[ptrl].fi>m*2) ptrl++;
  122. 			L[i] = ptrl;
  123. 		}
  124. 		vector<ii> stonesbydepth;
  125. 		for(int i=0;i<n;i++)
  126. 		{
  127. 			stonesbydepth.pb(mp(stones[i].se, i));
  128. 		}
  129. 		sort(stonesbydepth.begin(),stonesbydepth.end());
  130. 		vector<bool> used(n+2,0);
  131. 		for(ii stone:stonesbydepth)
  132. 		{
  133. 			int v=stone.se;
  134. 			used[v]=1;
  135. 			if(used[v+1]) merge(v,v+1);
  136. 			if(v>0&&used[v-1]) merge(v,v-1);
  137. 			//cerr<<"RT : "<<v<<' '<<rt(v)<<'\n';
  138. 			lmin[v] = leftmost[rt(v)];
  139. 			//cerr<<v<<' '<<lmin[v]<<'\n';
  140. 		}
  141. 		//build(1,0,n+1);
  142. 		build(stones);
  143. 		dp[0] = 0;
  144. 		ma.clear();
  145. 		deque<ii> S; S.pb(mp(0, 0)); add(0);
  146. 		//update(1,0,n+1,0,0);
  147. 		int ptr = 0;
  148. 		for(int i=1;i<=n;i++)
  149. 		{
  150. 			ll depth = stones[i-1].se; dp[i]=ll(1e18);
  151. 			/*
  152. 			ll mx=0;
  153. 			for(int j=i-1;j>=L[i-1];j--)
  154. 			{
  155. 				mx=max(mx,stones[j].se);
  156. 				dp[i] = min(dp[i], dp[j] + mx + s);
  157. 			}
  158. 			*/
  159. 			assert(query(n,lmin[i-1],i)==depth);
  160. 			while(S.size()>=2&&S[int(S.size())-2].fi>=lmin[i-1])
  161. 			{
  162. 				del(S.back().se); S.pop_back();
  163. 			}
  164. 			assert(!S.empty());
  165. 			if(S.back().fi>=lmin[i-1])
  166. 			{
  167. 				del(S.back().se);
  168. 				ll as=0;
  169. 				if(S.back().fi<i-1) 
  170. 				{
  171. 					as=query(n,S.back().fi,i-1);
  172. 					S.back().se-=as;
  173. 				}
  174. 				assert(depth>=as);
  175. 				S.back().se+=depth;
  176. 				add(S.back().se);
  177. 			}
  178. 			if(i-1>0) 
  179. 			{
  180. 				S.push_back(mp(i-1,dp[i-1]+depth)); add(dp[i-1]+depth);
  181. 			}
  182. 			while(!S.empty()&&S.front().fi<L[i-1])
  183. 			{
  184. 				int ptr=S.front().fi;
  185. 				ll tmp = S.front().se;
  186. 				S.pop_front(); del(tmp);
  187. 				ptr++;
  188. 				if(!S.empty()&&S.front().fi<=ptr) continue;
  189. 				tmp = dp[ptr] + query(n,ptr,i);
  190. 				S.push_front(mp(ptr,tmp)); add(tmp);
  191. 			}
  192. 			dp[i] = s + (*ma.begin()).fi;
  193. 			//dp[i] = query(1,0,n+1,L[i-1],i) + s;
  194. 			//update(1,0,n+1,i,dp[i]);
  195. 		}
  196. 		cout<<dp[n]<<'\n';
  197. 		cerr<<"Case #"<<zz+1<<" completed\n";
  198. 	}
  199. }
  200.  
Runtime error #stdin #stdout #stderr 0s 4456KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
stderr 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/ZltEJx
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!