fork download
copy 
  1. #include <ctime>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <iostream>
  5. #include <algorithm>
  6. using namespace std;
  7.  
  8. typedef long long LL;
  9.  
  10. inline int read()
  11. {
  12. 	int x = 0; int v = 1, c;
  13. 	while(c = getchar(), c < '0' || c > '9') if(c == '-') v = -1;
  14. 	for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  15. 	return x * v;
  16. }
  17.  
  18. template<typename T> inline void write(T x, int ch = 10)
  19. {
  20. 	static int s[20]; int t = 0;
  21. 	if(x < 0) x = -x, putchar('-');
  22. 	if(x == 0) putchar('0');
  23. 	for(s[t++] = ch; x; x /= 10)
  24. 		s[t++] = x % 10 + '0';
  25. 	while(t--) putchar(s[t]);
  26. }
  27.  
  28. const int maxn = 200005;
  29.  
  30. int n, pos[maxn], val[maxn], ans[maxn], sz[maxn << 2];
  31.  
  32. #define lc o << 1
  33. #define rc lc | 1
  34. #define Lc lc, L, M
  35. #define Rc rc, M + 1, R
  36. #define DM int M = (L + R) >> 1
  37.  
  38. void build(int o, int L, int R)
  39. {
  40. 	sz[o] = R - L + 1;
  41. 	if(L == R) return;
  42. 	DM; build(Lc); build(Rc);
  43. }
  44.  
  45. void insert(int o, int L, int R, int pos, int val)
  46. {
  47. 	DM; sz[o]--;
  48. 	if(L == R) { ans[L] = val; return; }
  49. 	if(pos <= sz[lc]) insert(Lc, pos, val);
  50. 	else insert(Rc, pos - sz[lc], val);
  51. }
  52.  
  53. void input()
  54. {
  55. 	for(int i = 1; i <= n; ++i)
  56. 	{
  57. 		pos[i] = read() + 1;
  58. 		val[i] = read();
  59. 	}
  60. 	build(1, 1, n);
  61. }
  62.  
  63. void solve()
  64. {
  65. 	for(int i = n; i >= 1; --i)
  66. 		insert(1, 1, n, pos[i], val[i]);
  67. 	for(int i = 1; i <= n; ++i)
  68. 		write(ans[i], i == n ? '\n' : ' ');
  69. }
  70.  
  71. int main()
  72. {
  73. #ifndef ONLINE_JUDGE
  74. 	freopen("input.txt", "r", stdin);
  75. 	freopen("output.txt", "w", stdout);
  76. #endif
  77.  
  78. 	while(~scanf("%d", &n))
  79. 	{
  80. 		input();
  81. 		solve();
  82. 	}
  83.  
  84. #ifndef ONLINE_JUDGE
  85. 	fclose(stdin), fclose(stdout);
  86. 	printf("Run Time: %.3fs\n", (double)clock() / CLOCKS_PER_SEC);
  87. #endif
  88. 	return 0;
  89. }
Success #stdin #stdout 0s 8928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/e3uhee
poj2828线段树版
language:
C++14 (clang 8.0)
created:
9 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!