| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 402433 |
2021-05-11T16:44:51 Z |
fvogel499 |
Plahte (COCI17_plahte) |
C++14 |
|
2000 ms |
409284 KB |
#include <iostream>
#include <fstream>
#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()) {
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];
}
// #define LOCAL
#ifdef LOCAL
ifstream fin("plahte.in");
#define cin fin
#endif
int main() {
int n, nbBalls;
cin >> n >> nbBalls;
set<int> coordSet; // used for index compression
// to further optimize we could have two separate sets: one for the x dimension, on for the y dimension
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;
coordSet.insert(rect[i].f.f);
coordSet.insert(rect[i].f.s);
coordSet.insert(rect[i].s.f);
coordSet.insert(rect[i].s.s);
}
int ballX [nbBalls];
int ballY [nbBalls];
int ballColor [nbBalls];
for (int i = 0; i < nbBalls; i++) {
cin >> ballX[i] >> ballY[i] >> ballColor[i];
coordSet.insert(ballX[i]);
coordSet.insert(ballY[i]);
}
unordered_map<int, int> coordMap; // compressed index map
// since it's unordered, be careful with collisions
// we could also use the faster hash map here : https://usaco.guide/gold/faster-hashmap?lang=cpp
int c = 0;
for (int i : coordSet) {
coordMap[i] = c;
c++;
}
// apply index compression
for (int i = 0; i < n; i++) {
rect[i].f.f = coordMap[rect[i].f.f];
rect[i].f.s = coordMap[rect[i].f.s];
rect[i].s.f = coordMap[rect[i].s.f];
rect[i].s.s = coordMap[rect[i].s.s];
}
for (int i = 0; i < nbBalls; i++) {
ballX[i] = coordMap[ballX[i]];
ballY[i] = coordMap[ballY[i]];
}
// create Events for sweep line algorithm
for (int i = 0; i < n; i++) {
sweep.push_back(Event(true, true, rect[i].f.f, i));
sweep.push_back(Event(true, false, rect[i].s.f, i));
}
for (int i = 0; i < nbBalls; i++) sweep.push_back(Event(false, -1, ballX[i], i)); // second parameter has no influence
sort(sweep.begin(), sweep.end(), sf); // sort by x-coordinate
btClear();
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
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
par[i.idx] = j.s;
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.s;
}
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 |
Correct |
372 ms |
122752 KB |
Output is correct |
| 2 |
Correct |
344 ms |
124132 KB |
Output is correct |
| 3 |
Correct |
69 ms |
105332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
463 ms |
135888 KB |
Output is correct |
| 2 |
Correct |
460 ms |
129340 KB |
Output is correct |
| 3 |
Correct |
70 ms |
105284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
898 ms |
164176 KB |
Output is correct |
| 2 |
Correct |
744 ms |
140956 KB |
Output is correct |
| 3 |
Correct |
72 ms |
105284 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1467 ms |
409284 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2047 ms |
189944 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
