fork download
copy 
  1.  
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5.  
  6. using namespace std;
  7.  
  8. int a[1000], b[1000], c[1000], axis[1000], l[1000000], r[1000000], s[1000000], loc[1000];
  9. pair<int, int> item[1000], query[1000000];
  10. unsigned f[1000][3200];
  11. bool ans[1000000];
  12.  
  13. int main() {
  14. 	int n;
  15. 	scanf("%d", &n);
  16. 	for (int i = 0; i < n; i ++) {
  17. 		scanf("%d%d%d", &c[i], &a[i], &b[i]);
  18. 		axis[i] = b[i];
  19. 		item[i] = make_pair(a[i], i);
  20. 	}
  21. 	sort(axis, axis + n);
  22. 	int tot = unique(axis, axis + n) - axis;
  23. 	sort(item, item + n);
  24.  
  25. 	int m;
  26. 	scanf("%d", &m);
  27. 	for (int i = 0; i < m; i ++) {
  28. 		scanf("%d%d%d", &l[i], &s[i], &r[i]);
  29. 		r[i] += l[i];
  30. 		query[i] = make_pair(l[i], i);
  31. 	}
  32. 	sort(query, query + m);
  33.  
  34. 	memset(f, 0, sizeof(f));
  35. 	for (int i = 0; i < tot; i ++) {
  36. 		f[i][0] = 1;
  37. 		loc[i] = 0;
  38. 	}
  39.  
  40. 	int p = 0;
  41. 	for (int i = 0; i < n; i ++) {
  42. 		while (p < m && query[p].first < item[i].first) {
  43. 			int now = query[p].second;
  44. 			int pos = lower_bound(axis, axis + tot, r[now] + 1) - axis;
  45. 			if (pos < tot && (f[pos][s[now] / 32] & 1U << (s[now] % 32)))
  46. 				ans[now] = true;
  47. 			else
  48. 				ans[now] = false;
  49. 			p ++;
  50. 		}
  51. 		int t1 = lower_bound(axis, axis + tot, a[item[i].second]) - axis;
  52. 		int t2 = lower_bound(axis, axis + tot, b[item[i].second]) - axis;
  53. 		int d = c[item[i].second] / 32;
  54. 		int x = c[item[i].second] % 32;
  55. 		int y = 32 - c[item[i].second] % 32;
  56. 		for (int j = t1; j <= t2; j ++) {
  57. 			unsigned *g = f[j];
  58. 			for (int k = min(loc[j] + d + 1, 100000 / 32); k >= d + 1; k --) {
  59. 				if (g[k] == ~0U || g[k - d] == 0 && g[k - d - 1] == 0) continue;
  60. 				g[k] |= g[k - d] << x;
  61. 				if (y < 32) g[k] |= g[k - d - 1] >> y;
  62. 				if (g[k] > 0 && k > loc[j]) loc[j] = k;
  63. 			}
  64. 			g[d] |= g[0] << x;
  65. 			if (g[d] > 0 && d > loc[j]) loc[j] = d;
  66. 		}
  67. 	}
  68. 	while (p < m) {
  69. 		int now = query[p].second;
  70. 		int pos = lower_bound(axis, axis + tot, r[now] + 1) - axis;
  71. 		if (pos < tot && (f[pos][s[now] / 32] & 1U << (s[now] % 32)))
  72. 			ans[now] = true;
  73. 		else
  74. 			ans[now] = false;
  75. 		p ++;
  76. 	}
  77.  
  78. 	for (int i = 0; i < m; i ++)
  79. 		if (ans[i]) printf("TAK\n"); else printf("NIE\n");
  80.  
  81. 	return 0;
  82. }
  83.  
Success #stdin #stdout 0.03s 35768KB
comments (?)
stdin
copy 
5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5
stdout
copy 
TAK
NIE
TAK
TAK
NIE
https://ideone.com/ecSKY
language:
C++ (gcc 8.3)
created:
14 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!