| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 402421 |
2021-05-11T16:26:30 Z |
fvogel499 |
Plahte (COCI17_plahte) |
C++14 |
|
606 ms |
421140 KB |
#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 << 21) // 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
int par [siz]; // the immediate rectangle a rectangle is contained inside
int ballImpactRect [siz]; // the smallest rectangle the ball hits
int insertedT [siz]; // remember time when deleting elements
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()) {
auto it = bt[idx].end();
it = prev(it);
pii itpi = *it;
if (itpi.first > mP.first) {
mP.first = itpi.first;
mP.second = itpi.second;
}
}
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 getInt(int val) {
long long loc = val;
loc /= 1000000000;
loc++;
loc--;
// loc = 0;
return int(loc);
}
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
btClear();
int t = 0; // time variable
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
int val = j.s;
par[i.idx] = getInt(val);
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
int val = j.s;
// ballImpactRect[i.idx] = val;
}
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++;
}
Compilation message
plahte.cpp: In function 'int main()':
plahte.cpp:150:17: warning: unused variable 'val' [-Wunused-variable]
150 | int val = j.s;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
464 ms |
414372 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
448 ms |
415332 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
518 ms |
417700 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
606 ms |
421140 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
593 ms |
421120 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
