#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int32_t MAX_N = 80005;
const int32_t MAX_M = 80005;
class Rectangle {
public:
int32_t lowerLeftX, lowerLeftY, upperRightX, upperRightY, ind;
};
class Shot {
public:
int32_t x, y, color;
};
Rectangle rects[MAX_N];
Shot shots[MAX_M];
void Compress(int32_t n, int32_t m, int32_t &maxY) {
vector< int32_t > xs, ys;
xs.push_back(0);
ys.push_back(0);
for(int32_t i = 1; i <= n; i++) {
xs.push_back(rects[i].lowerLeftX);
xs.push_back(rects[i].upperRightX);
ys.push_back(rects[i].lowerLeftY);
ys.push_back(rects[i].upperRightY);
}
for(int32_t i = 1; i <= m; i++) {
xs.push_back(shots[i].x);
ys.push_back(shots[i].y);
}
sort(xs.begin(), xs.end());
sort(ys.begin(), ys.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
for(int32_t i = 1; i <= n; i++) {
rects[i].lowerLeftX = lower_bound(xs.begin(), xs.end(), rects[i].lowerLeftX) - xs.begin();
rects[i].upperRightX = lower_bound(xs.begin(), xs.end(), rects[i].upperRightX) - xs.begin();
rects[i].lowerLeftY = lower_bound(ys.begin(), ys.end(), rects[i].lowerLeftY) - ys.begin();
rects[i].upperRightY = lower_bound(ys.begin(), ys.end(), rects[i].upperRightY) - ys.begin();
}
for(int32_t i = 1; i <= m; i++) {
shots[i].x = lower_bound(xs.begin(), xs.end(), shots[i].x) - xs.begin();
shots[i].y = lower_bound(ys.begin(), ys.end(), shots[i].y) - ys.begin();
}
maxY = ys.size();
}
class SegmentTree {
private:
int32_t treeSize;
stack< pair< int32_t, int32_t > > data[4 * (MAX_N + MAX_M)];
void Build(int32_t node, int32_t low, int32_t high) {
if(low == high) {
data[node].push({ 0, 0 });
return;
}
int32_t mid = (low + high) / 2;
Build(2 * node, low, mid);
Build(2 * node + 1, mid + 1, high);
}
void Update(int32_t node, int32_t low, int32_t high, int32_t qLow, int32_t qHigh, pair< int32_t, int32_t > qVal) {
if(low > qHigh || high < qLow) {
return;
}
else if(low >= qLow && high <= qHigh) {
if(qVal.first == -1) {
data[node].pop();
}
else {
data[node].push(qVal);
}
return;
}
int32_t mid = (low + high) / 2;
Update(2 * node, low, mid, qLow, qHigh, qVal);
Update(2 * node + 1, mid + 1, high, qLow, qHigh, qVal);
}
void Query(int32_t node, int32_t low, int32_t high, int32_t qInd, pair< int32_t, int32_t > &ans) {
if(low > qInd || high < qInd) {
return;
}
if(!data[node].empty()) {
ans = max(ans, data[node].top());
}
if(low == qInd && high == qInd) {
return;
}
int32_t mid = (low + high) / 2;
Query(2 * node, low, mid, qInd, ans);
Query(2 * node + 1, mid + 1, high, qInd, ans);
}
public:
void Init(int32_t n) {
treeSize = n;
Build(1, 1, treeSize);
}
void Update(int32_t low, int32_t high, pair< int32_t, int32_t > val) {
Update(1, 1, treeSize, low, high, val);
}
int32_t Query(int32_t ind) {
pair< int32_t, int32_t > ans = { 0, 0 };
Query(1, 1, treeSize, ind, ans);
return ans.second;
}
};
SegmentTree segTree;
class Event {
public:
bool isBegining;
int32_t x, low, high, rectInd;
Event(bool isBegining = false, int32_t x = 0, int32_t low = 0, int32_t high = 0, int32_t rectInd = 0)
: isBegining(isBegining), x(x), low(low), high(high), rectInd(rectInd) {
}
bool operator< (const Event &other) {
if(x != other.x) {
return x < other.x;
}
else {
return isBegining > other.isBegining;
}
}
};
class Tree {
private:
class Node {
public:
int32_t ans;
set< int32_t > colors;
vector< int32_t > v;
};
int32_t cntNodes;
public:
Node nodes[MAX_N];
void Init(int32_t n) {
cntNodes = n;
}
void AddEdge(int32_t x, int32_t y) {
nodes[x].v.push_back(y);
}
void Merge(int32_t x, int32_t y) {
if(nodes[x].colors.size() < nodes[y].colors.size()) {
for(int32_t p : nodes[x].colors) {
nodes[y].colors.insert(p);
}
swap(nodes[x].colors, nodes[y].colors);
}
else {
for(int32_t p : nodes[y].colors) {
nodes[x].colors.insert(p);
}
}
}
void Dfs(int32_t node) {
for(int32_t x : nodes[node].v) {
Dfs(x);
if(node != 0) {
Merge(node, x);
}
}
nodes[node].ans = nodes[node].colors.size();
}
};
Tree t;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int32_t n, m;
cin >> n >> m;
for(int32_t i = 1; i <= n; i++) {
cin >> rects[i].lowerLeftX >> rects[i].lowerLeftY;
cin >> rects[i].upperRightX >> rects[i].upperRightY;
rects[i].ind = i;
}
for(int32_t i = 1; i <= m; i++) {
cin >> shots[i].x >> shots[i].y >> shots[i].color;
}
int32_t maxY;
Compress(n, m, maxY);
segTree.Init(maxY);
vector< Event > evs(2 * n + 1);
for(int32_t i = 1; i <= n; i++) {
evs[2 * i - 1] = Event(true, rects[i].lowerLeftX, rects[i].lowerLeftY, rects[i].upperRightY, rects[i].ind);
evs[2 * i] = Event(false, rects[i].upperRightX, rects[i].lowerLeftY, rects[i].upperRightY, rects[i].ind);
}
sort(evs.begin() + 1, evs.begin() + 1 + 2 * n);
t.Init(n);
for(int32_t i = 1; i <= 2 * n; i++) {
if(evs[i].isBegining) {
t.AddEdge(segTree.Query(evs[i].low), evs[i].rectInd);
segTree.Update(evs[i].low, evs[i].high, { i, evs[i].rectInd });
}
else {
segTree.Update(evs[i].low, evs[i].high, { -1, -1 });
}
}
for(int32_t i = 1; i <= m; i++) {
evs.push_back(Event(false, shots[i].x, shots[i].y, i, -1));
}
sort(evs.begin() + 1, evs.end());
for(int32_t i = 1; i < (int32_t) evs.size(); i++) {
if(evs[i].rectInd == -1) {
t.nodes[segTree.Query(evs[i].low)].colors.insert(shots[evs[i].high].color);
}
else if(evs[i].isBegining) {
segTree.Update(evs[i].low, evs[i].high, { i, evs[i].rectInd });
}
else {
segTree.Update(evs[i].low, evs[i].high, { -1, -1 });
}
}
t.Dfs(0);
for(int32_t i = 1; i <= n; i++) {
cout << t.nodes[i].ans << endl;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
581 ms |
442620 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
633 ms |
443632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
825 ms |
449084 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1085 ms |
456660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1055 ms |
456660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
