Submission #431127

#	Time	Username	Problem	Language	Result	Execution time	Memory
431127		fvogel499	Plahte (COCI17_plahte)	C++14	0 / 160	1543 ms	202224 KiB

plahte

#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++;
}

• Subtask 1: 0 / 32
• Subtask 2: 0 / 32
• Subtask 3: 0 / 32
• Subtask 4: 0 / 32
• Subtask 5: 0 / 32