fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. const int maxn = 50005;
  8.  
  9. int n, m;
  10. int MaxL[maxn << 2], MaxR[maxn << 2], Max[maxn << 2], col[maxn << 2];
  11.  
  12. #define lc o << 1
  13. #define Lc lc, L, M
  14. #define rc o << 1 | 1
  15. #define Rc rc, M + 1, R
  16.  
  17. inline void maintain(int o, int L, int R)
  18. {
  19. 	int M = (L + R) >> 1;
  20. 	MaxL[o] = (MaxL[lc] == M - L + 1 ? MaxL[lc] + MaxL[rc] : MaxL[lc]);
  21. 	MaxR[o] = (MaxR[rc] == R - M ? MaxR[lc] + MaxR[rc] : MaxR[rc]);
  22. 	Max[o] = max(max(Max[lc], Max[rc]), MaxR[lc] + MaxL[rc]);
  23. }
  24.  
  25. inline void pushdown(int o, int L, int R)
  26. {
  27. 	if(col[o] != -1) {
  28. 		int M = (L + R) >> 1;
  29. 		col[lc] = col[o]; MaxL[lc] = MaxR[lc] = Max[lc] = col[o] * (M - L + 1);
  30. 		col[rc] = col[o]; MaxL[rc] = MaxR[rc] = Max[rc] = col[o] * (R - M);
  31. 		col[o] = -1;
  32. 	}
  33. }
  34.  
  35. int query(int o, int L, int R, int sz)
  36. {
  37. 	if(L == R) return L;
  38. 	pushdown(o, L, R);
  39. 	int M = (L + R) >> 1;
  40. 	if(Max[lc] >= sz) { //madan ba Max da cheng MaxL le, ri le gou!!!
  41. 		return query(Lc, sz);
  42. 	} else if(MaxR[lc] + MaxL[rc] >= sz) {
  43. 		return M - MaxR[lc] + 1;
  44. 	} else {
  45. 		return query(Rc, sz);
  46. 	}
  47. }
  48.  
  49. void update(int o, int L, int R, int ql, int qr, int v)
  50. {
  51. 	if(L == ql && qr == R) {
  52. 		col[o] = v; MaxL[o] = MaxR[o] = Max[o] = v * (R - L + 1);
  53. 	} else {
  54. 		pushdown(o, L, R);
  55. 		int M = (L + R) >> 1;
  56. 		if(qr <= M) {
  57. 			update(Lc, ql, qr, v);
  58. 		} else if(ql > M) {
  59. 			update(Rc, ql, qr, v);
  60. 		} else {
  61. 			update(Lc, ql, M, v);
  62. 			update(Rc, M + 1, qr, v);
  63. 		}
  64. 		maintain(o, L, R);
  65. 	}
  66. }
  67.  
  68. int main()
  69. {
  70. #ifndef ONLINE_JUDGE
  71. 	freopen("input.txt", "r", stdin);
  72. 	freopen("output.txt", "w", stdout);
  73. #endif
  74.  
  75. 	scanf("%d%d", &n, &m);
  76. 	memset(col, -1, sizeof(col));
  77. 	col[1] = 1; MaxL[1] = MaxR[1] = Max[1] = n;
  78. 	for(int i = 1; i <= m; ++i) {
  79. 		int ty, x, d;
  80. 		scanf("%d", &ty);
  81. 		if(ty == 1) {
  82. 			scanf("%d", &d);
  83. 			if(Max[1] < d) {
  84. 				puts("0");
  85. 			} else {
  86. 				x = query(1, 1, n, d);
  87. 				update(1, 1, n, x, x + d - 1, 0);
  88. 				printf("%d\n", x);
  89. 			}
  90. 		} else {
  91. 			scanf("%d%d", &x, &d);
  92. 			update(1, 1, n, x, x + d - 1, 1);
  93. 		}
  94. 	}
  95.  
  96. #ifndef ONLINE_JUDGE
  97. 	fclose(stdin), fclose(stdout);
  98. #endif
  99. }
  100.  
Success #stdin #stdout 0s 6536KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/zBCMag
poj3667
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!