fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long 
  4. #define ull unsigned long long
  5. #define all(x) x.begin(), x.end()
  6. #define X first
  7. #define Y second
  8. #define MOD (ll) 1000000007
  9. #define rd(l, r) uniform_int_distribution<ll> (l, r) (rng)
  10. #define eb(x) emplace_back(x)
  11. #define rsz resize
  12. #define sz size
  13. #define pii pair<int,int>
  14.  
  15. using namespace std;
  16.  
  17. struct wall{
  18. 	int h;
  19. 	int p;
  20. 	int ind;
  21. 	bool operator < (const wall &sth) {
  22. 		if ( h == sth.h )
  23. 			return p > sth.p;
  24. 		return h < sth.h;
  25. 	}
  26. };
  27.  
  28. int n;
  29. vector<pii> a;
  30. vector<wall> b;
  31.  
  32. void read(){
  33. 	#ifdef LOCAL
  34. 		freopen( "test.inp", "r", stdin );
  35. //		freopen( "test.out", "w", stdout );
  36. 	#endif	
  37. 	cin >> n;
  38. 	a.rsz(n);
  39. 	for ( int i = 0; i < n; ++i ){
  40. 		cin >> a[i].X;
  41. 		a[i].Y = i;
  42. 	}
  43. 	b.rsz(n);
  44. 	for ( int i = 0; i < n; ++i ){
  45. 		cin >> b[i].h >> b[i].p;
  46. 		b[i].ind = i;
  47. 	}
  48. }
  49.  
  50. void solve(){
  51. 	sort(all(a));
  52. 	sort(all(b));
  53. 	vector<int> ans(n, -1);
  54. 	priority_queue<pii> pq;
  55. 	int j = n;
  56. 	ll s = 0;
  57. 	for ( int i = n-1; i >= 0; --i ){
  58. 		while ( j > 0 && b[j-1].h >= a[i].X ){
  59. 			--j;
  60. 			pq.push({b[j].p, b[j].ind});
  61. 		}
  62. 		if ( pq.sz() ){
  63. 			s += pq.top().X;
  64. 		 	ans[a[i].Y] = pq.top().Y + 1;
  65. 			pq.pop();
  66. 		}
  67. 	}
  68. 	cout << s << '\n';
  69. 	for ( int i = 0; i < n; ++i )
  70. 		if ( ans[i] == -1 ){
  71. 			ans[i] = pq.top().Y + 1;
  72. 			pq.pop();
  73. 		}
  74. 	for ( int i : ans )
  75. 		cout << i << ' ';
  76. }
  77.  
  78. int main(){
  79. 	ios_base::sync_with_stdio(0);	
  80. 	cin.tie(0); cout.tie(0);
  81. 	read();
  82. 	solve();
  83. 	return 0;
  84. }
  85.  
Success #stdin #stdout 0.01s 5360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Bd16QP
language:
C++ (gcc 8.3)
created:
1 year 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!