#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <algorithm>
using namespace std;
#define mp pair<pii, pii>
#define pii pair<int, int>
#define f first
#define s second
#define pow2 (1 << 20) // just over 1 million
#define siz 80000
set<pii> bt [pow2*2];
vector<int> graph [siz+1]; // add extra space for virtual root
set<int> colorsAtNode [siz];
int nbColours [siz]; // different colors at node rect
struct Event {
Event(bool lIsRectSide, bool lIsStartSide, int lx, int lidx) {
isRectSide = lIsRectSide;
isStartSide = lIsStartSide;
x = lx;
idx = lidx;
}
bool isRectSide, isStartSide; // iSStartSide is only for rectangles
int x, idx; // idx is rectangle or ball index
};
// used for sorting
bool sf(Event a, Event b) {
return (a.x < b.x or (a.x == b.x and (a.isRectSide and a.isStartSide) and !b.isRectSide) or (a.x == b.x and !a.isRectSide and (b.isRectSide and !b.isStartSide)));
// second conditions are to avoid tricky edge cases where point is located on segment. We must make sure the point is between the start side and the end side
}
// reinit segtree
void btClear() {
for (int i = 0; i < pow2*2; i++) bt[i].clear();
}
// insert pair in bt interval
void btAdd(int rBegin, int rEnd, pii rPair, int qNode, int qBegin, int qEnd) {
if (rBegin > qEnd or rEnd < qBegin) return;
else if (rBegin <= qBegin and qEnd <= rEnd) bt[qNode].insert(rPair);
else {
int qMid = (qBegin+qEnd)/2;
btAdd(rBegin, rEnd, rPair, qNode*2, qBegin, qMid);
btAdd(rBegin, rEnd, rPair, qNode*2+1, qMid+1, qEnd);
}
}
// remove pair from bt interval
void btRemove(int rBegin, int rEnd, pii rPair, int qNode, int qBegin, int qEnd) {
if (rBegin > qEnd or rEnd < qBegin) return;
else if (rBegin <= qBegin and qEnd <= rEnd) bt[qNode].erase(rPair);
else {
int qMid = (qBegin+qEnd)/2;
btRemove(rBegin, rEnd, rPair, qNode*2, qBegin, qMid);
btRemove(rBegin, rEnd, rPair, qNode*2+1, qMid+1, qEnd);
}
}
// point request for maximum pair
pii btGetMax(int idx) {
idx += pow2;
pii mP = pii(-1, -1); // mP = max pair, init with lowest possible value, NOTE: time starts at 0
while (idx != 0) {
if (!bt[idx].empty()) mP = max(mP, *(prev(bt[idx].end())));
idx /= 2; // loop for all parents
}
return mP;
}
// small-to-large merging technique to count number of different colors
set<int>& dfs(int cn) { // cn = current node
for (int nn : graph[cn]) { // nn = new node
set<int>& ls = dfs(nn); // pass by reference
if (colorsAtNode[cn].size() < ls.size()) swap(colorsAtNode[cn], ls);
for (int j : ls) colorsAtNode[cn].insert(j); // small-to-large merging
}
nbColours[cn] = colorsAtNode[cn].size();
return colorsAtNode[cn];
}
int main() {
// int n, nbBalls;
// cin >> n >> nbBalls;
// mp rect [n];
// vector<Event> sweep;
// for (int i = 0; i < n; i++) {
// cin >> rect[i].f.f >> rect[i].f.s >> rect[i].s.f >> rect[i].s.s;
// sweep.push_back(Event(true, true, rect[i].f.f, i));
// sweep.push_back(Event(true, false, rect[i].s.f, i));
// }
// int ballColor [nbBalls];
// int ballY [nbBalls];
// for (int i = 0; i < nbBalls; i++) {
// int lx;
// cin >> lx >> ballY[i] >> ballColor[i];
// sweep.push_back(Event(false, -1, lx, i)); // second parameter has no influence
// }
// sort(sweep.begin(), sweep.end(), sf); // sort by x-coordinate
// int par [n]; // the immediate rectangle a rectangle is contained inside
// int ballImpactRect [nbBalls]; // the smallest rectangle the ball hits
// int t = 0; // time variable
// int insertedT [n]; // remember time when deleting elements
btClear();
// for (Event i : sweep) {
// if (i.isRectSide and i.x == rect[i.idx].f.f) {
// pii j = btGetMax(rect[i.idx].f.s); // it doesn't matter on which point of interval [ rect[i.idx].f.s ; rect[i.idx].s.s ] we look at since there are no sides crossing
// if (j.second == -1) j.second = n; // n is the virtual root
// par[i.idx] = j.second;
// insertedT[i.idx] = t;
// btAdd(rect[i.idx].f.s, rect[i.idx].s.s, pii(insertedT[i.idx], i.idx), 1, 0, pow2-1); // add this side as latest rectangle in this interval
// }
// else if (i.isRectSide and i.x == rect[i.idx].s.f) {
// btRemove(rect[i.idx].f.s, rect[i.idx].s.s, pii(insertedT[i.idx], i.idx), 1, 0, pow2-1);
// }
// else {
// pii j = btGetMax(ballY[i.idx]);
// if (j.second == -1) j.second = n; // n is the virtual root
// ballImpactRect[i.idx] = j.second;
// }
// t++;
// }
// for (int i = 0; i < n; i++) {
// graph[par[i]].push_back(i);
// }
// for (int i = 0; i < nbBalls; i++) {
// colorsAtNode[ballImpactRect[i]].insert(ballColor[i]);
// }
// dfs(n); // start dfs from virtual root
// for (int i = 0; i < n; i++) {
// cout << nbColours[i] << endl;
// }
int d = 0;
d++;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
104388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
104388 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
104392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
67 ms |
104292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
75 ms |
104396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
