#include <bits/stdc++.h>
using namespace std;
//Paint info: 845 966305103 70503
//Bad box info: 825 966200021 979406993 966308497
struct Container {
int index;
unordered_set<int> colors;
Container* parent;
vector<Container*> children;
Container(Container* p, int i): parent(p), index(i) {}
};
struct Event {
int index;
int color;
int x_pos;
int y_low, y_high;
bool close;
Event(int col, int x, int yl, int yh, bool c, int i):
color(col), x_pos(x), y_low(yl), y_high(yh), close(c), index(i) {}
};
struct Node {
Node *l = 0, *r = 0;
int lo, hi;
Container* mset = NULL;
Container* val = NULL;
Node(int lo,int hi): lo(lo), hi(hi) {}
Container* query(int L, int R) {
if (R <= lo || hi <= L) return NULL;
if (L <= lo && hi <= R) return val;
push();
Container* result;
if((result = l->query(L, R)) != NULL)
return result;
else if((result = r->query(L, R)) != NULL)
return result;
else
return NULL;
}
void set(int L, int R, Container* x) {
if (R <= lo || hi <= L) return;
if (L <= lo && hi <= R) mset = val = x;
else {
push(), l->set(L, R, x), r->set(L, R, x);
}
}
void push() {
if (!l) {
int mid = lo + (hi - lo)/2;
l = new Node(lo, mid); r = new Node(mid, hi);
}
if (mset != NULL)
l->set(lo,hi,mset), r->set(lo,hi,mset), mset = NULL;
}
};
int main(){
cin.tie(NULL)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<Event> actions;
for(int i = 0; i < n; i++){
int lx, ly, ux, uy;
cin >> lx >> ly >> ux >> uy;
actions.emplace_back(-1, lx, ly, uy, false, i);
actions.emplace_back(-1, ux, ly, uy, true, i);
}
for(int i = 0; i < m; i++){
int x, y, c;
cin >> x >> y >> c;
actions.emplace_back(c, x, y, y, true, i);
}
auto actionComp = [](const auto &a, const auto &b){
if(a.x_pos == b.x_pos){
if(a.color == -1 && b.color == -1)
return b.close;
else if(a.color == -1 && b.color != -1)
return !a.close;
else if(a.color != -1 && b.color == -1)
return b.close;
else
return a.y_low < b.y_low;
}else
return a.x_pos < b.x_pos;
};
sort(actions.begin(), actions.end(), actionComp);
Container root(NULL, -1);
Node* containerQuery = new Node(-10, 1e9+10);
vector<int> colorCounts(n, 0);
containerQuery->set(0, (1e9 + 1) + 1, &root);
for(const Event event : actions){
if(event.color == -1){
if(event.close){
Container* child = containerQuery->query(event.y_low, event.y_high + 1);
assert(child != NULL);
// if(child->index == 130)
// fout << "Closing: " << child->index << "\n";
colorCounts[child->index] = child->colors.size();
if(child->parent->colors.size() < child->colors.size())
swap(child->parent->colors, child->colors);
child->parent->colors.insert(child->colors.begin(), child->colors.end());
containerQuery->set(event.y_low, event.y_high + 1, child->parent);
}else{
Container* parent = containerQuery->query(event.y_low, event.y_high + 1);
assert(parent != NULL);
parent->children.push_back(new Container(parent, event.index));
containerQuery->set(event.y_low, event.y_high + 1, parent->children.back());
// if(event.index == 130){
// fout << "Opening: " << event.index << " " << event.y_low << " " << event.y_high << " " << parent->index << "\n";
// fout << "Testing: " << containerQuery->query(966305103, 966305104)->index << "\n";
// }
}
}else{
Container* sheet = containerQuery->query(event.y_low, event.y_high + 1);
assert(sheet != NULL);
// if(sheet->index == 130)
// fout << "Inserting into: " << sheet->index << "\n";
// if(event.index == 33905)
// fout << "Wrong insert: " << sheet->index << " " << event.y_low << " " << event.y_high << "\n";
sheet->colors.insert(event.color);
}
}
for(const int &count : colorCounts)
cout << count << "\n";
}
/*
3 9
1 1 8 8
4 2 5 3
2 5 6 7
7 4 10
4 2 1
5 2 2
5 3 3
4 3 4
2 5 1
6 5 2
6 7 3
2 7 4
*/
/*
5 5
1 1 10 10
2 2 9 9
3 3 8 8
4 4 7 7
5 5 6 6
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
*/
Compilation message
plahte.cpp: In constructor 'Container::Container(Container*, int)':
plahte.cpp:11:16: warning: 'Container::parent' will be initialized after [-Wreorder]
11 | Container* parent;
| ^~~~~~
plahte.cpp:9:9: warning: 'int Container::index' [-Wreorder]
9 | int index;
| ^~~~~
plahte.cpp:14:5: warning: when initialized here [-Wreorder]
14 | Container(Container* p, int i): parent(p), index(i) {}
| ^~~~~~~~~
plahte.cpp: In constructor 'Event::Event(int, int, int, int, bool, int)':
plahte.cpp:22:10: warning: 'Event::close' will be initialized after [-Wreorder]
22 | bool close;
| ^~~~~
plahte.cpp:18:9: warning: 'int Event::index' [-Wreorder]
18 | int index;
| ^~~~~
plahte.cpp:24:5: warning: when initialized here [-Wreorder]
24 | Event(int col, int x, int yl, int yh, bool c, int i):
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
136 ms |
67948 KB |
Output is correct |
| 2 |
Correct |
133 ms |
70712 KB |
Output is correct |
| 3 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
147 ms |
71040 KB |
Output is correct |
| 2 |
Correct |
151 ms |
74576 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
117572 KB |
Output is correct |
| 2 |
Correct |
246 ms |
117652 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
390 ms |
180940 KB |
Output is correct |
| 2 |
Correct |
383 ms |
175028 KB |
Output is correct |
| 3 |
Correct |
0 ms |
320 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
371 ms |
179144 KB |
Output is correct |
| 2 |
Correct |
409 ms |
179388 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
