#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define vsort(a) sort(a.begin(), a.end());
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
typedef long long ll;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
void io();
template <int SZ> struct SegmentTree {
stack <pii> data[SZ * 2]; // <id, time>
void update(int a, int b, pii x) { // add x to [a,b]
update(1, 0, SZ - 1, a, b, x);
}
void update(int node, int l, int r, int a, int b, pii x) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
data[node].push(x);
return;
}
int mid = (l + r) / 2;
update(node * 2, l, mid, a, b, x);
update(node * 2 + 1, mid + 1, r, a, b, x);
}
void ddelete(int a, int b, pii x) {
ddelete(1, 0, SZ - 1, a, b, x);
}
void ddelete(int node, int l, int r, int a, int b, pii x) {
if (l > b || r < a) return;
if (l >= a && r <= b) {
assert(data[node].top().first == x.first);
data[node].pop();
return;
}
int mid = (l + r) / 2;
ddelete(node * 2, l, mid, a, b, x);
ddelete(node * 2 + 1, mid + 1, r, a, b, x);
}
int query(int node) {
node += SZ;
pii ret = { -1,-1 }; // id, time
while (node) {
if (!data[node].empty()) {
if (data[node].top().second > ret.second) {
ret = data[node].top();
}
}
node /= 2;
}
return ret.first;
}
};
SegmentTree<100000> tree;
struct Event {
int x, f, y1, y2, id;
Event(int a, int b, int c, int d, int e) : x(a), f(b), y1(c), y2(d), id(e) {}
bool operator< (const Event& other) const {
return mp(x, f) < mp(other.x, other.f);
}
};
int N, M; // rect, balls
v<Event> allevents;
void compressCoord() {
map<int, int> conv;
FOR(i, 0, allevents.size()) {
conv[allevents[i].y1] = 0;
conv[allevents[i].y2] = 0;
}
int num = 0;
for (auto& en : conv)
en.second = num++;
FOR(i, 0, allevents.size()) {
allevents[i].y1 = conv[allevents[i].y1];
allevents[i].y2 = conv[allevents[i].y2];
}
}
void input() {
cin >> N >> M;
allevents.push_back(Event(-1, -1, -1, 1000000001, 0)); // start
allevents.push_back(Event(1000000001, 1, -1, 1000000001, 0)); // end
FOR(i, 0, N) {
int x1, y1, x2, y2, id = i + 1;
cin >> x1 >> y1 >> x2 >> y2;
allevents.push_back(Event(x1, -1, y1, y2, id)); // start
allevents.push_back(Event(x2, 1, y1, y2, id)); // end
}
FOR(i, 0, M) {
int x, y, c;
cin >> x >> y >> c;
allevents.push_back(Event(x, 0, y, -1, c));
}
}
///**************/
//stack<pii> fakeSeg[100000]; // <id, time>
//void update(int a, int b, pii x) { // add x to [a,b]
// FORE(i, a, b)
// fakeSeg[i].push(x);
//}
//
//void ddelete(int a, int b, pii x) {
// FORE(i, a, b) {
// assert(fakeSeg[i].top().first == x.first);
// fakeSeg[i].pop();
// }
//}
//int query(int node) {
// if (fakeSeg[node].size() == 0)
// return -1;
// return fakeSeg[node].top().first;
//}
///**************/
int par[100000];
v<int> adj[100000];
set<int> colors[100000];
int ans[100000];
void merge(set<int> &a, set<int> &b) {
if (a.size() > b.size()) { // merge b into a
a.insert(b.begin(), b.end());
}
else { // merge a into b then swap
b.insert(a.begin(), a.end());
swap(a, b);
}
}
void dfs(int cur, int par) {
for (int chi : adj[cur]) if (chi != par) {
dfs(chi, cur);
merge(colors[cur], colors[chi]);
}
ans[cur] = colors[cur].size();
}
int main() {
// io();
input();
compressCoord();
vsort(allevents);
FOR(i, 0, allevents.size()) {
Event e = allevents[i];
if (e.f == -1) { // start
par[e.id] = tree.query((e.y1 + e.y2) / 2); // parent of e.id
tree.update(e.y1, e.y2, { e.id, i }); // add id into seg tree
}
else if (e.f == 1) { // end
tree.ddelete(e.y1, e.y2, { e.id, i });
}
else { // ball
colors[tree.query(e.y1)].insert(e.id); // which id is this ball in?
}
}
/* FORE(i, 0, N)
cout << i << ": " << par[i] << " par\n";
FORE(i, 0, N) {
cout << i << "contains: ";
for (int c : colors[i])
cout << c << " ";
cout << "\n";
}*/
FORE(i, 0, N) {
if (par[i] != -1) {
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
}
}
dfs(0, -1);
FORE(i, 1, N)
cout << ans[i] << "\n";
return 0;
}
void io() {
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
freopen("output.out", "w", stdout);
#else
// online submission
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
}
Compilation message
plahte.cpp: In function 'void io()':
plahte.cpp:226:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("input.in", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
plahte.cpp:227:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("output.out", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
506 ms |
293628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
534 ms |
295680 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
731 ms |
303596 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1112 ms |
315060 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
978 ms |
315236 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
