fork download
copy 
  1. #include <fstream>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7. ifstream F("arbint.in");
  8. ofstream G("arbint.out");
  9.  
  10. const int N = 100010;
  11.  
  12. int n,m;
  13.  
  14. struct node {
  15. 	vector<int> a;
  16. 	int mx;
  17.  
  18. 	node(int x)
  19. 	{
  20. 		a.push_back(x);
  21. 		mx = x;
  22. 	}
  23. 	void push(int x)
  24. 	{
  25. 		a.push_back(x);
  26. 		mx = max(x,mx);
  27. 	}
  28. 	void update(int p,int x)
  29. 	{
  30. 		a[p] = x;
  31. 		mx = 0;
  32. 		for (int i=0;i<int(a.size());++i)
  33. 			mx = max(mx,a[i]);
  34. 	}
  35. 	int query(int p1,int p2)
  36. 	{
  37. 		if ( p1 == p2 || p1 >= int(a.size()) || p2 <= 0 )
  38. 			return 0;
  39. 		if ( p1 == 0 && p2 == int(a.size()) ) 
  40. 			return mx;
  41.  
  42. 		int _mx = 0;
  43. 		for (int i=p1;i<p2;++i)
  44. 			_mx = max(_mx,a[i]);
  45. 		return _mx;
  46. 	}
  47. 	void print()
  48. 	{
  49. 		for (int i=0;i<int(a.size());++i)
  50. 			cerr<<a[i]<<' ';
  51. 	}
  52. };
  53.  
  54. struct ksegment {
  55. 	int k;
  56. 	vector<node> v;
  57.  
  58. 	ksegment()
  59. 	{
  60. 	}
  61. 	ksegment(int _k)
  62. 	{
  63. 		k = _k;
  64. 	}
  65. 	void push(int x)
  66. 	{
  67. 		if ( v.empty() ) 
  68. 			v.push_back( node(x) );
  69. 		else
  70. 			if ( int(v.back().a.size()) == k )
  71. 				v.push_back( node(x) );
  72. 			else
  73. 				v.back().push(x);
  74. 	}
  75. 	void update(int p,int x)
  76. 	{
  77. 		int wh = (p-1)/k;   
  78. 		p -= wh*k+1; 
  79. 		v[wh].update(p,x);
  80. 	}
  81. 	int query(int l,int r)
  82. 	{
  83. 		int mx = 0;
  84. 		for (int i=0;i<int(v.size());++i)
  85. 		{
  86. 			int ll = max(l-i*k-1,0);
  87. 			int rr = min(k,r-i*k);
  88. 			mx = max(mx,v[i].query( ll,rr ));
  89. 		}
  90. 		return mx;
  91. 	}
  92. 	void print()
  93. 	{
  94. 		for (int i=0;i<int(v.size());++i)
  95. 		{
  96. 			cerr<<"[";
  97. 			v[i].print();
  98. 			cerr<<"] ";
  99. 		}
  100. 		cerr<<'\n';
  101. 	}
  102. };
  103.  
  104. int main()
  105. {
  106.     F>>n>>m;
  107. 	ksegment ks = ksegment(sqrt(n));
  108. 	for (int i=1,x;i<=n;++i)
  109. 	{
  110. 		F>>x;
  111. 		ks.push(x);
  112. 	}
  113. 	for (int i=1,t,x,y;i<=m;++i)
  114. 	{
  115. 		//ks.print();
  116. 		F>>t;
  117. 		++t;
  118.  
  119. 		if ( t == 1 ) 
  120. 		{
  121. 			F>>x>>y;
  122. 			G<<ks.query(x,y)<<'\n';
  123. 		}
  124. 		else 
  125. 		{
  126. 			F>>x>>y;
  127. 			ks.update(x,y);
  128. 		}
  129. 	}
  130. }
  131.  
Success #stdin #stdout 0s 3460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mxYRzM
language:
C++ (gcc 8.3)
created:
8 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!