Submission #402418

#	Time	Username	Problem	Language	Result	Execution time	Memory
402418		fvogel499	Plahte (COCI17_plahte)	C++14	0 / 160	647 ms	421076 KiB

plahte

#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--;
    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 (stderr)

plahte.cpp: In function 'int main()':
plahte.cpp:149:17: warning: unused variable 'val' [-Wunused-variable]
  149 |             int val = j.s;
      |                 ^~~

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