fork download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5. template<class T> inline void chkmax(T &x, const T &y) { if(x < y) x = y; }
  6. template<class T> inline void chkmin(T &x, const T &y) { if(x > y) x = y; }
  7. const int MAXN = (1 << 20);
  8. const int inf = (int)1e9 + 42;
  9. const int bound = (int)1e9;
  10.  
  11. struct segment_tree
  12. {
  13. 	vector<int> li[4 * MAXN];
  14. 	int mx[4 * MAXN];
  15.  
  16. 	void init(int l, int r, int idx)
  17. 	{
  18. 		if(l == r)
  19. 		{
  20. 			li[idx].clear();
  21. 			mx[idx] = -inf;
  22. 			return;
  23. 		}
  24.  
  25. 		int mid = (l + r) >> 1;
  26. 		init(l, mid, 2 * idx + 1);
  27. 		init(mid + 1, r, 2 * idx + 2);
  28.  
  29. 		mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
  30. 	}
  31.  
  32. 	void add(int pos, int id, int l, int r, int idx)
  33. 	{
  34. 		if(l > pos || r < pos) return;
  35.  
  36. 		if(l == r && pos == l)
  37. 		{
  38. 			li[idx].push_back(id);
  39. 			mx[idx] = id;
  40. 			return;
  41. 		}
  42.  
  43. 		int mid = (l + r) >> 1;
  44. 		add(pos, id, l, mid, 2 * idx + 1);
  45. 		add(pos, id, mid + 1, r, 2 * idx + 2);
  46.  
  47. 		mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
  48. 	}
  49.  
  50. 	void rem(int pos, int l, int r, int idx)
  51. 	{
  52. 		if(pos > r || pos < l)
  53. 			return;
  54.  
  55. 		if(pos == l && l == r)
  56. 		{
  57. 			li[idx].pop_back();
  58. 			if(li[idx].empty()) mx[idx] = -inf;
  59. 			else mx[idx] = li[idx].back();
  60. 			return;
  61. 		}
  62.  
  63. 		int mid = (l + r) >> 1;
  64. 		rem(pos, l, mid, 2 * idx + 1);
  65. 		rem(pos, mid + 1, r, 2 * idx + 2);
  66.  
  67. 		mx[idx] = max(mx[2 * idx + 1], mx[2 * idx + 2]);
  68. 	}
  69.  
  70. 	int query(int qL, int qR, int l, int r, int idx)
  71. 	{
  72. 		if(qL > r || qR < l)
  73. 			return -inf;
  74.  
  75. 		if(qL <= l && r <= qR)
  76. 			return mx[idx];
  77.  
  78. 		int mid = (l + r) >> 1;
  79. 		return max(query(qL, qR, l, mid, 2 * idx + 1), query(qL, qR, mid + 1, r, 2 * idx + 2));
  80. 	}
  81. };
  82.  
  83. struct rect
  84. {
  85. 	int x1, y1, x2, y2;
  86. };
  87.  
  88. int n;
  89. rect a[MAXN];
  90.  
  91. void print_inp()
  92. {
  93. 	cout << n << endl;
  94. 	for(int i = 0; i < n; i++)
  95. 		cout << a[i].x1 << " " << a[i].y1 << " " << a[i].x2 - a[i].x1 << " " << a[i].y2 - a[i].y1 << endl;
  96. 	cout << flush;
  97. }
  98.  
  99. int m;
  100. vector<int> available;
  101. pair<int, pair<int, int> > li_p[MAXN];
  102.  
  103. void read()
  104. {
  105. 	cin >> n >> m;
  106. 	for(int i = 0; i < n; i++)
  107. 		cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >> a[i].y2;
  108.  
  109. 	for(int i = 0; i < m; i++)
  110. 	{
  111. 		int x, y, k;
  112. 		cin >> x >> y >> k;
  113. 		available.push_back(k);
  114. 		li_p[i] = {x, {y, k}};
  115. 	}
  116.  
  117. 	sort(available.begin(), available.end());
  118. 	available.erase(unique(available.begin(), available.end()), available.end());
  119. 	for(int i = 0; i < m; i++)
  120. 		li_p[i].second.second = lower_bound(available.begin(), available.end(), li_p[i].second.second) - available.begin() + 1;	
  121. }
  122.  
  123. vector<pair<int, int> > ev;
  124. vector<int> cli;
  125.  
  126. int get_cord(int x)
  127. {
  128. 	return lower_bound(cli.begin(), cli.end(), x) - cli.begin();
  129. }
  130.  
  131. segment_tree t;
  132. vector<int> G[MAXN];
  133. int answer[MAXN];
  134. set<int> st;
  135. int tr_sz[MAXN];
  136.  
  137. vector<int> values[MAXN];
  138.  
  139. void pre_dfs(int u, int pr)
  140. {
  141. 	tr_sz[u] = 1;
  142. 	for(int v: G[u])
  143. 		if(v != pr)
  144. 		{
  145. 			pre_dfs(v, u);
  146. 			tr_sz[u] += tr_sz[v];
  147. 		}
  148. }
  149.  
  150. int cnt[MAXN];
  151. int curr_ans;
  152.  
  153. void add_vertex(int u)
  154. {
  155. 	for(int val: values[u]) 
  156. 	{
  157. 		cnt[val]++;
  158. 		if(cnt[val] == 1)
  159. 			curr_ans++;
  160. 	}
  161. }
  162.  
  163. void clear(int u, int pr)
  164. {
  165. 	for(int val: values[u]) cnt[val] = 0;
  166. 	for(int v: G[u])
  167. 		if(v != pr)
  168. 			clear(v, u);
  169. }
  170.  
  171. void add(int u, int pr)
  172. {
  173. 	add_vertex(u);
  174. 	for(int v: G[u])
  175. 		if(v != pr)
  176. 			add(v, u);
  177. }
  178.  
  179. void dfs(int u, int pr, int keep)
  180. {
  181. 	pair<int, int> mx = {-1, -1};
  182. 	for(int v: G[u])
  183. 		if(v != pr)
  184. 			mx = max(mx, {tr_sz[v], v});
  185.  
  186. 	for(int v: G[u])
  187. 		if(v != pr && v != mx.second)
  188. 			dfs(v, u, 0);
  189.  
  190. 	if(mx.second != -1)
  191. 		dfs(mx.second, u, 1);
  192.  
  193. 	for(int v: G[u])
  194. 		if(v != pr && v != mx.second)
  195. 			add(v, u);
  196.  
  197. 	add_vertex(u);
  198. 	answer[u] = curr_ans;
  199.  
  200. 	if(keep) return;
  201. 	clear(u, pr);
  202. 	curr_ans = 0;
  203. }
  204.  
  205. const int OFFSET = (200000);
  206.  
  207. bool cmp(pair<int, int> a, pair<int, int> b)
  208. {
  209. 	if(a.first != b.first) return a.first < b.first;
  210. 	return a.second > b.second;
  211. }
  212.  
  213. void solve()
  214. {
  215. 	for(int i = 0; i < n; i++)
  216. 	{
  217. 		ev.push_back(make_pair(a[i].x2, i));
  218. 		cli.push_back(a[i].y1);
  219. 		cli.push_back(a[i].y2);
  220. 	}
  221.  
  222. 	for(int i = 0; i < m; i++)
  223. 	{
  224. 		ev.push_back(make_pair(li_p[i].first, OFFSET + i));
  225. 		cli.push_back(li_p[i].second.first);
  226. 	}
  227.  
  228. 	sort(ev.begin(), ev.end(), cmp);
  229. 	sort(cli.begin(), cli.end());
  230. 	cli.erase(unique(cli.begin(), cli.end()), cli.end());
  231. 	t.init(0, cli.size(), 0);
  232.  
  233. 	int e_idx = 0;
  234. 	for(auto e: ev)
  235. 	{
  236. 		if(e.second >= OFFSET)
  237. 		{
  238. 			int i = e.second - OFFSET;
  239. 			t.add(get_cord(li_p[i].second.first), e_idx++, 0, cli.size(), 0);
  240. 			continue;
  241. 		}
  242.  
  243. 		int i = e.second, L = get_cord(a[i].y1) + 1, R = get_cord(a[i].y2) - 1;
  244.  
  245. 		int pos;
  246. 		while(((pos = t.query(L - 1, R + 1, 0, cli.size(), 0)) >= 0))
  247. 		{
  248. 			if(ev[pos].second >= OFFSET) 
  249. 			{
  250. 				if(li_p[ev[pos].second - OFFSET].first < a[i].x1) break;
  251. 				values[i].push_back(li_p[ev[pos].second - OFFSET].second.second);
  252. 				t.rem(get_cord(li_p[ev[pos].second - OFFSET].second.first), 0, cli.size(), 0);
  253. 				continue;
  254. 			}
  255.  
  256. 			if(a[ev[pos].second].x2 < a[i].x1) break;
  257. 			G[i].push_back(ev[pos].second);
  258. 			t.rem(get_cord(a[ev[pos].second].y1), 0, cli.size(), 0);
  259. 		}
  260.  
  261. 		t.add(L - 1, e_idx++, 0, cli.size(), 0);
  262. 	}
  263.  
  264. 	int pos;
  265. 	while((pos = t.query(0, cli.size(), 0, cli.size(), 0)) >= 0)
  266. 	{
  267. 		if(ev[pos].second >= OFFSET) 
  268. 		{
  269. 			t.rem(get_cord(li_p[ev[pos].second - OFFSET].second.first), 0, cli.size(), 0);
  270. 			continue;
  271. 		}
  272.  
  273. 		G[MAXN - 1].push_back(ev[pos].second);
  274. 		t.rem(get_cord(a[ev[pos].second].y1), 0, cli.size(), 0);
  275. 	}
  276.  
  277. 	pre_dfs(MAXN - 1, MAXN - 1);
  278. 	dfs(MAXN - 1, MAXN - 1, 1);
  279.  
  280. 	for(int i = 0; i < n; i++)
  281. 		cout << answer[i] << endl;
  282. }
  283.  
  284. int main()
  285. {
  286. 	ios_base::sync_with_stdio(false);
  287. 	cin.tie(NULL);
  288.  
  289. 	read();
  290. 	solve();
  291. 	return 0;
  292. }
  293.  
  294.  
Success #stdin #stdout 0.03s 220928KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/YWJFaQ
language:
C++ (gcc 8.3)
created:
7 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!