fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<long long , int>
  10. #define lll pair<long long , pair<long long , long long>>
  11. #define lii pair<long long , pair<long long , int>>
  12. #define iii pair<int , pair<int , int>>
  13. #define iiii pair<pair<int , int> , pair<int , int>>
  14. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  15. #define li pair<long long , int>
  16. #define db long double
  17. #define onBit(mask , i) (mask | (1 << i))
  18. #define offBit(mask , i) (mask & (~(1 << i)))
  19.  
  20. const long long INF = 1e16;
  21. const int N = 5e5 + 7;
  22. const int M = 2e3 + 5e3 + 7;
  23. const int S = 107;
  24. vector<int> cand , query;
  25. int n , m;
  26. long long f[S * S] , ans[N];
  27. long long Pre_res = 0;
  28.  
  29. struct gv{
  30.     long long p , s , c;
  31. };
  32.  
  33. gv b[M];
  34.  
  35. bool cmp(gv x , gv y){
  36.     return x.p < y.p;
  37. }
  38.  
  39. struct gv1{
  40.     long long p;
  41.     int id;
  42. };
  43.  
  44. gv1 a[N];
  45.  
  46. bool cmp1(gv1 x , gv1 y){
  47.     return x.p < y.p;
  48. }
  49.  
  50. void inp(){
  51.     cin >> n;
  52.     for (int i = 1 ; i <= n ; ++i){
  53.         cin >> a[i].p;
  54.         a[i].id = i;
  55.     }
  56.  
  57.     cin >> m;
  58.     sort(a + 1 , a + n + 1 , cmp1);
  59.     for (int i = 1 ; i <= m ; ++i){
  60.         cin >> b[i].p >> b[i].s >> b[i].c;
  61.     }
  62.     sort(b + 1 , b + m + 1 , cmp);
  63. }
  64.  
  65. void ktao(){
  66.     for (int j = 1 ; j <= 100 * 101 ; ++j)
  67.         f[j] = INF;
  68.  
  69.     f[0] = 0;
  70. }
  71.  
  72. void sol(long long P , long long P1 , long long Wbest , long long Cbest){
  73.     cout << P << " " << P1 << '\n';
  74.     for (int i = 0 ; i < cand.size() ; ++i){
  75.         cout << cand[i] << " ";
  76.     }
  77.     cout << '\n';
  78.     for (int j = 1 ; j <= 100 * 101 ; ++j){
  79.         for (int i = 0 ; i < cand.size() ; ++i){
  80.             int id = cand[i];
  81.             int W = min(b[id].s , P + j - b[id].p);
  82.             if (f[j - W] == INF) continue;
  83.             f[j] = min(f[j] , f[j - W] + b[id].c);
  84.         }
  85.     }
  86.  
  87.     for (int i = 0 ; i < query.size() ; ++i){
  88.         int id = query[i];
  89.         long long Pi = a[id].p;
  90.         if (Pi - P + 1 > 100 * 100){
  91.             long long tmp = Pi - P + 1 , k = (tmp - 100 * 100) / Wbest;
  92.             long long res = Pre_res + k * Cbest + f[tmp - k * Wbest];
  93.  
  94.             ans[a[id].id] = Pre_res + res;
  95.         }
  96.         else ans[a[id].id] = Pre_res + f[Pi - P + 1];
  97.     }
  98.     long long Pi = P1 - 1;
  99.     if (Pi - P + 1 > 100 * 100){
  100.         long long tmp = Pi - P + 1 , k = (tmp - 100 * 100) / Wbest;
  101.         long long res = Pre_res + k * Cbest + f[tmp - k * Wbest];
  102.  
  103.         Pre_res += res;
  104.     }
  105.     else Pre_res += f[Pi - P + 1];
  106.  
  107.     while (query.size()) query.pop_back();
  108.  
  109.     int i = 0;
  110.     while (i < cand.size()){
  111.         int id = cand[i];
  112.         int W = min(b[id].s , P - b[id].p + 1);
  113.         if (W == b[id].s) cand.erase(cand.begin() + i);
  114.         else ++i;
  115.     }
  116. }
  117.  
  118. void solve(){
  119.     ktao();
  120.     int i = 1 , j = 1;
  121.     b[m + 1].p = 1e9 + 1;
  122.     long long Wbest = b[1].s , Cbest = b[1].c;
  123.     while (j <= n){
  124.         int u = i;
  125.  
  126.         cand.push_back(i);
  127.         while (u < m && b[u + 1].p == b[i].p){
  128.             ++u;
  129.             cand.push_back(u);
  130.             if (Cbest * b[u].s < b[u].c * Wbest){
  131.                 Wbest = b[u].s;
  132.                 Cbest = b[u].c;
  133.             }
  134.         }
  135.  
  136.         if (j < b[u + 1].p){
  137.             int v = j;
  138.             query.push_back(j);
  139.             while (v < n && a[v + 1].p < b[u + 1].p){
  140.                 ++v;
  141.                 query.push_back(v);
  142.             }
  143.             j = v + 1;
  144.         }
  145.  
  146.         sol(b[i].p , b[u + 1].p , Wbest , Cbest);
  147.         i = u + 1;
  148.     }
  149.  
  150.     for (int i = 1 ; i <= n ; ++i){
  151.         cout << ans[i] << " ";
  152.     }
  153.     cout << '\n';
  154. }
  155.  
  156. int main(){
  157.     faster;
  158.     inp();
  159.     solve();
  160.     return 0;
  161. }
  162.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/NmeGSi
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
2 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!