Submission #431121

#TimeUsernameProblemLanguageResultExecution timeMemory
431121fvogel499Plahte (COCI17_plahte)C++14
0 / 160
1471 ms195804 KiB
#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]; mp rect [siz]; int ballX [siz]; int ballY [siz]; int ballColor [siz]; 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 vector<int> graph [siz+1]; // add extra space for virtual root set<int> colorsAtNode [siz+1]; 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, int level) { // cn = current node if (level%10 == 0) cout << level << endl; for (int nn : graph[cn]) { // nn = new node set<int>& ls = dfs(nn, level+1); // 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() { // i/o optimisation cin.tie(0); // ios_base::sync_with_stdio(0); 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 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); } 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 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, 0); // start dfs from virtual root // for (int i = 0; i < n; i++) { // cout << nbColours[i] << endl; // } int d = 0; d++; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...