fork download
copy 
  1. #include <stdio.h>
  2. #include <stack>
  3. #include <map>
  4. #include <string.h>
  5. #include <string>
  6. #include <iostream>
  7. #include <algorithm>
  8. #include <iomanip>
  9. #include <math.h>
  10. #include <vector>
  11. #include <set>
  12. #include <queue>
  13. #include <functional>
  14. using namespace std;
  15. #define ll long long
  16. #define mp make_pair
  17. #define pb push_back
  18. //#define ld long double
  19. const double sn = 1e-6;
  20. const int siz = 100005;
  21. bool cmp(int a, int b) {
  22. 	return a > b;
  23. }
  24. int n, m;
  25. int perm[siz], root[siz], lazy[siz*4];
  26. vector<int> adj[siz];
  27. int tree[siz*4];
  28. set<int, bool(*)(int, int)> se(cmp);
  29. void build(int id, int s, int e) {
  30. 	if (s == e) {
  31. 		tree[id] = root[s];
  32. 		if(root[s] == 0) {
  33. 			tree[id] = INT_MAX;
  34. 			se.insert(s);
  35. 		}
  36. 		return;
  37. 	}
  38. 	int mid = (s + e) / 2;
  39. 	int le = id * 2, ri = id * 2 + 1;
  40. 	build(le, s, mid);
  41. 	build(ri, mid+1, e);
  42. 	tree[id]= min(tree[le], tree[ri]);
  43. }
  44. void fin(int id, int s, int e) {
  45. 	tree[id] -= lazy[id];
  46. 	if (s != e) {
  47. 		lazy[2 * id] += lazy[id];
  48. 		lazy[2 * id + 1] += lazy[id];
  49. 	}
  50. 	lazy[id] = 0;
  51. }
  52. void update(int id, int s, int e, int l, int r) {
  53. 	if (lazy[id] != 0) {
  54. 		fin(id, s, e);
  55. 	}
  56. 	if (s > r || e < l)
  57. 		return;
  58. 	int le = id * 2, ri = id * 2 + 1;
  59. 	if (s >= l && e <= r) {
  60. 		tree[id]--;
  61. 		if (s != e) {
  62. 			lazy[le]++;
  63. 			lazy[ri]++;
  64. 		}
  65. 		if(tree[id]!=0)
  66. 			return;
  67. 		if (tree[id] == 0 && s == e) {
  68. 			se.insert(s);
  69. 			tree[id] = INT_MAX;
  70. 			return;
  71. 		}
  72. 		lazy[le]--;
  73. 		lazy[ri]--;
  74. 	}
  75. 	int mid = (s + e) / 2;
  76. 	update(le, s, mid, l, r);
  77. 	update(ri, mid+1, e, l, r);
  78. 	int bef = tree[id];
  79. 	tree[id] = min(tree[le], tree[ri]);
  80. }
  81. int ans[siz];
  82. int main() {
  83. 	int t;
  84. 	scanf("%d", &t);
  85. 	for (int ii = 0; ii < t; ii++) {
  86. 		scanf("%d%d", &n, &m);
  87. 		for (int i = 1; i <= n; i++) {
  88. 			root[i] = i - 1;
  89. 			adj[i].clear();
  90. 		}
  91. 		for (int i = 0; i < m; i++) {
  92. 			int a, b;
  93. 			scanf("%d%d", &a, &b);
  94. 			adj[a].push_back(b);
  95. 			root[b]--;
  96. 		}
  97. 		build(1, 1, n);
  98. 		int c = 0;
  99. 		while (!se.empty()) {
  100. 			int v = *se.begin();
  101. 			ans[c++] = v;
  102. 			se.erase(se.begin());
  103. 			sort(adj[v].begin(), adj[v].end());
  104. 			int in = v + 1, sz=adj[v].size();
  105. 			for (int i = 0; i < sz; i++) {
  106. 				int en = adj[v][i] - 1;
  107. 				if (en >= in) {
  108. 					update(1,1,n,in,en);
  109. 				}
  110. 				in = adj[v][i] + 1;
  111. 			}
  112. 			if (in <= n) {
  113. 				update(1, 1, n, in, n);
  114. 			}
  115. 		}
  116. 		for (int i = 0; i < n; i++) {
  117. 			printf("%d", ans[i]);
  118. 			if (i != n - 1)
  119. 				printf(" ");
  120. 			else
  121. 				printf("\n");
  122. 		}
  123. 	}
  124. 	return 0;
  125. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp: In function ‘void build(int, int, int)’:
prog.cpp:33:15: error: ‘INT_MAX’ was not declared in this scope
    tree[id] = INT_MAX;
               ^~~~~~~
prog.cpp: In function ‘void update(int, int, int, int, int)’:
prog.cpp:69:15: error: ‘INT_MAX’ was not declared in this scope
    tree[id] = INT_MAX;
               ^~~~~~~
stdout
copy 
Standard output is empty
https://ideone.com/JSqbeu
language:
C++14 (gcc 8.3)
created:
7 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!