fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. int main() {
  7. 	ios::sync_with_stdio(0), cin.tie(0);
  8. 	int N; cin >> N;
  9. 	ll P; cin >> P;
  10. 	vector<ll> T(N);
  11. 	for (int i = 0; i < N; i++) {
  12. 		cin >> T[i];
  13. 	}
  14.  
  15. 	vector<pair<ll, int>> evts; evts.reserve(N);
  16. 	for (int i = 0; i < N; i++) {
  17. 		evts.emplace_back(T[i], i);
  18. 	}
  19. 	sort(evts.begin(), evts.end());
  20. 	auto eit = evts.begin();
  21.  
  22. 	vector<ll> ans(N);
  23.  
  24. 	vector<int> queueOrder; queueOrder.reserve(N);
  25. 	auto qit = queueOrder.begin();
  26. 	set<int> queueInds;
  27. 	set<int> waiting;
  28. 	ll lastWater = 0;
  29. 	while (eit != evts.end() || !queueInds.empty()) {
  30. 		assert(int(queueInds.size()) == int(queueOrder.end() - qit));
  31. 		// 0: somebody in the queue gets water
  32. 		// 1: somebody starts waiting
  33. 		int t = -1;
  34. 		if (eit == evts.end()) {
  35. 			t = 0;
  36. 		} else if (queueInds.empty()) {
  37. 			t = 1;
  38. 		} else if (lastWater + P < eit->first) {
  39. 			t = 0;
  40. 		} else {
  41. 			t = 1;
  42. 		}
  43. 		assert(t != -1);
  44.  
  45. 		//cerr << "t = " << t << '\n';
  46.  
  47. 		if (t == 0) {
  48. 			lastWater += P;
  49. 			int i = *qit;
  50. 			//cerr << i << " gets water" << '\n';
  51. 			ans[i] = lastWater;
  52. 			assert(queueInds.count(i));
  53. 			queueInds.erase(i);
  54. 			qit++;
  55. 		} else {
  56. 			if (queueInds.empty()) {
  57. 				lastWater = eit->first;
  58. 			}
  59. 			int i = eit->second;
  60. 			//cerr << i << " starts waiting" << '\n';
  61. 			waiting.insert(i);
  62. 			eit++;
  63. 		}
  64.  
  65. 		if (!waiting.empty()) {
  66. 			int i = *waiting.begin();
  67. 			if (queueInds.empty() || i < *queueInds.begin()) {
  68. 				//cerr << i << " enters queue" << '\n';
  69. 				queueOrder.push_back(i);
  70. 				queueInds.insert(i);
  71. 				waiting.erase(waiting.begin());
  72. 			}
  73. 		}
  74. 	}
  75.  
  76. 	for (int i = 0; i < N; i++) {
  77. 		cout << ans[i] << " \n"[i+1==N];
  78. 	}
  79.  
  80. 	return 0;
  81. }
  82.  
Success #stdin #stdout 0s 4460KB
comments (?)
stdin
copy 
5 314
0 310 942 628 0
stdout
copy 
314 628 1256 942 1570
https://ideone.com/kjtz5M
language:
C++14 (gcc 8.3)
created:
5 years 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!