fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class FastIntReader extends BufferedReader
  5. {
  6. 	int cur, res;
  7.  
  8. 	FastIntReader(InputStream s){super(new InputStreamReader(s));}
  9.  
  10. 	int getNextInt() throws IOException
  11. 	{
  12. 		cur = read();
  13. 		res = 0;
  14. 		while(cur!=32 && cur!=-1 && cur != '\n'){
  15. 			res*=10;
  16. 			res += (int)(cur-'0');
  17. 			cur = read();
  18. 		}
  19. 		return res;
  20. 	}
  21. }
  22. //Дерево отрезков.
  23. class SegmentTree
  24. {
  25. 	static long []tree;
  26. 	//Конструктор.
  27. 	SegmentTree(int length){tree = new long[4*length+1];}
  28.  
  29. 	void build(int v, int treeL, int treeR, FastIntReader in) throws IOException
  30. 	{
  31.  
  32. 		if(treeL == treeR) tree[v] = in.getNextInt();
  33. 		else{
  34. 			int treeM = (treeL + treeR)/2;
  35. 			build(v*2, treeL, treeM, in);
  36. 			build(v*2+1, treeM+1, treeR, in);
  37. 			tree[v] = tree[v*2] + tree[v*2+1];
  38. 		}
  39. 	}
  40.  
  41. 	//Присваивание человечку на позиции pos веса newVal.
  42. 	void update(int v, int treeL, int treeR, int pos, int newVal)
  43. 	{
  44. 		if(treeL == treeR) tree[v] = newVal;
  45. 		else{
  46. 			int treeM = (treeL + treeR)/2;
  47. 			if(pos <= treeM){
  48. 				update(v*2, treeL, treeM, pos, newVal);
  49. 			}
  50. 			else{
  51. 				update(v*2+1, treeM+1, treeR, pos, newVal);
  52. 			}
  53. 			tree[v] = tree[v*2] + tree[v*2+1];
  54. 		}
  55. 	}
  56.  
  57. 	//Нахождение количества поместившихся человечков.
  58. 	int findNumberOfPeople(int v, int treeL, int treeR, long max_w)
  59. 	{
  60. 		if(treeL == treeR){
  61. 			if(tree[v] <= max_w) return 1;
  62. 			else return 0;
  63. 		}
  64. 		int treeM = (treeL + treeR)/2;
  65. 		if(tree[v*2] > max_w)
  66. 			return findNumberOfPeople(v*2, treeL, treeM, max_w);
  67. 		else
  68. 			return treeM - treeL + 1 + findNumberOfPeople(v*2+1, treeM+1, treeR, max_w-tree[v*2]);
  69. 	}
  70. }
  71.  
  72. class Main
  73. {
  74. 	public static void main (String[] args) throws java.lang.Exception
  75. 	{
  76. 		FastIntReader in = new FastIntReader(System.in);
  77. 		PrintWriter out = new PrintWriter(System.out);
  78. 		//Построение дерева отрезков.
  79. 		int n, m;
  80. 		n = in.getNextInt();
  81. 		SegmentTree tr = new SegmentTree(n);
  82. 		tr.build(1, 1, n, in);
  83. 		//Обработка запросов.
  84. 		m = in.getNextInt();
  85. 		int type, x, y, v;
  86. 		for(int i = 0; i < m; ++i){
  87. 			type = in.getNextInt();
  88. 			if(type == 2){
  89. 				x = in.getNextInt();
  90. 				y = in.getNextInt();
  91. 				tr.update(1, 1, n, x, y);
  92. 			}
  93. 			else{
  94. 				v = in.getNextInt();
  95. 				out.print(tr.findNumberOfPeople(1, 1, n, v));
  96. 				out.print('\n');
  97. 			}
  98. 		}
  99. 		out.flush();
  100. 	}
  101. }
Success #stdin #stdout 0.06s 2841600KB
comments (?)
stdin
copy 
5
1 2 3 4 5
5
1 7
1 3
2 1 5
1 7
1 3
stdout
copy 
3
2
2
0
https://ideone.com/LVypc2
e-olymp 4496
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!