fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4. using namespace __gnu_pbds;
  5. using namespace std;
  6.  
  7. template<typename T>
  8. using ordered_multiset = tree<
  9.     pair<T,int>, null_type,
  10.     less<pair<T,int>>,
  11.     rb_tree_tag,
  12.     tree_order_statistics_node_update>;
  13.  
  14. const int k = (1 << 19);
  15. int uid = 1;
  16.  
  17. ordered_multiset<int> drzewo[k*2+10];
  18.  
  19. void upd(int x,int a)
  20. {
  21. 	int c = (*drzewo[x].find_by_order(0)).first;
  22. 	drzewo[x].erase(drzewo[x].lower_bound({c,-1}));
  23. 	drzewo[x].insert({a,uid});
  24. 	uid++;
  25. 	x /= 2;
  26. 	while(x >= 1)
  27. 	{
  28. 		drzewo[x].erase(drzewo[x].lower_bound({c,-1}));
  29. 		drzewo[x].insert({a,uid});
  30. 		uid++;
  31. 		x /= 2;
  32. 	}
  33. }
  34.  
  35. int odp(int l,int p,int L,int P,int x,int a)
  36. {
  37. 	if(l > P || p < L)
  38. 	{
  39. 		return 0;
  40. 	}
  41. 	if(L <= l && p <= P)
  42. 	{
  43. 		return drzewo[x].order_of_key({a,-1});
  44. 	}
  45. 	return odp(l,(l+p)/2,L,P,x*2,a)+odp((l+p+1)/2,p,L,P,x*2+1,a);
  46. }
  47.  
  48. int main()
  49. {
  50. 	/*int n,a,b;
  51. 	cin >> n;
  52. 	for(int i = 0;i < n;++i)
  53. 	{
  54. 		cin >> a;
  55. 		if(a == 0)
  56. 		{
  57. 			cin >> a;
  58. 			os.insert({a,uid});
  59. 			uid++;
  60. 		}
  61. 		else if(a == 1)
  62. 		{
  63. 			cin >> a;
  64. 			os.erase(os.lower_bound({a,-1}));
  65. 			uid++;
  66. 		}
  67. 		else
  68. 		{
  69. 			cin >> a;
  70. 			cout << os.order_of_key({a,-1}) << endl;
  71. 		}
  72. 	}*/
  73. 	int n,m,u,a,b,c,d,f;
  74. 	cin >> n >> m >> u;
  75. 	for(int i = 0;i < n;++i)
  76. 	{
  77. 		cin >> a;
  78. 		drzewo[i+k].insert({a,uid});
  79. 		uid++;
  80. 	}
  81. 	for(int i = n;i < k;++i)
  82. 	{
  83. 		drzewo[i+k].insert({1e9,uid});
  84. 		uid++;
  85. 	}
  86. 	for(int i = k-1;i >= 1;--i)
  87. 	{
  88. 		//cout << drzewo[i].size() << endl;
  89. 		for (auto j : drzewo[i*2])
  90. 			drzewo[i].insert(j);
  91. 		for (auto j : drzewo[i*2+1])
  92. 			drzewo[i].insert(j);
  93. 		//cout << drzewo[i].size() << ' ' << i << endl;
  94. 	}
  95. 	for(int i = 0;i < m;++i)
  96. 	{
  97. 		cin >> a >> b >> c >> d;
  98. 		f = odp(0,k-1,a-1,b-1,1,c);
  99. 		upd(k+d-1,(f*u)/(b-a+1));
  100. 		//cout << f << endl;
  101. 	}
  102. 	for(int i = 0;i < n;++i)
  103. 	{
  104. 		cout << (*drzewo[k+i].find_by_order(0)).first << endl;
  105. 	}
  106. }
  107.  
  108.  
  109.  
  110.  
Success #stdin #stdout 3.71s 757260KB
comments (?)
stdin
copy 
10 1 11
1
2
3
4
5
6
7
8
9
10
2 8 6 10
stdout
copy 
1
2
3
4
5
6
7
8
9
6
https://ideone.com/FCNC1p
language:
C++ (gcc 8.3)
created:
1 day 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!