Submission #837099

#	Time	Username	Problem	Language	Result	Execution time	Memory
837099		Nicolas125841	Plahte (COCI17_plahte)	C++17	160 / 160	409 ms	180940 KiB

plahte

#include <bits/stdc++.h>

using namespace std;

//Paint info: 845 966305103 70503
//Bad box info: 825 966200021 979406993 966308497

struct Container {
    int index;
    unordered_set<int> colors;
    Container* parent;
    vector<Container*> children;

    Container(Container* p, int i): parent(p), index(i) {}
};

struct Event {
    int index;
    int color;
    int x_pos;
    int y_low, y_high;
    bool close;

    Event(int col, int x, int yl, int yh, bool c, int i): 
        color(col), x_pos(x), y_low(yl), y_high(yh), close(c), index(i) {}
};

struct Node {
    Node *l = 0, *r = 0;

    int lo, hi;
    Container* mset = NULL;
    Container* val = NULL;

    Node(int lo,int hi): lo(lo), hi(hi) {}

    Container* query(int L, int R) {
        if (R <= lo || hi <= L) return NULL;
        if (L <= lo && hi <= R) return val;

        push();

        Container* result;

        if((result = l->query(L, R)) != NULL)
            return result;
        else if((result = r->query(L, R)) != NULL)
            return result;
        else
            return NULL;
    }

    void set(int L, int R, Container* x) {
        if (R <= lo || hi <= L) return;
        if (L <= lo && hi <= R) mset = val = x;
        else {
            push(), l->set(L, R, x), r->set(L, R, x);
        }
    }

    void push() {
        if (!l) {
            int mid = lo + (hi - lo)/2;
            l = new Node(lo, mid); r = new Node(mid, hi);
        }

        if (mset != NULL)
            l->set(lo,hi,mset), r->set(lo,hi,mset), mset = NULL;
    }
};

int main(){
    cin.tie(NULL)->sync_with_stdio(false);

    int n, m;
    cin >> n >> m;

    vector<Event> actions;
    for(int i = 0; i < n; i++){
        int lx, ly, ux, uy;
        cin >> lx >> ly >> ux >> uy;

        actions.emplace_back(-1, lx, ly, uy, false, i);
        actions.emplace_back(-1, ux, ly, uy, true, i);
    }    
    
    for(int i = 0; i < m; i++){
        int x, y, c;
        cin >> x >> y >> c;

        actions.emplace_back(c, x, y, y, true, i);
    }

    auto actionComp = [](const auto &a, const auto &b){
        if(a.x_pos == b.x_pos){
            if(a.color == -1 && b.color == -1)
                return b.close;
            else if(a.color == -1 && b.color != -1)
                return !a.close;
            else if(a.color != -1 && b.color == -1)
                return b.close;
            else
                return a.y_low < b.y_low;
        }else
            return a.x_pos < b.x_pos;
    };

    sort(actions.begin(), actions.end(), actionComp);

    Container root(NULL, -1);

    Node* containerQuery = new Node(-10, 1e9+10);
    vector<int> colorCounts(n, 0);

    containerQuery->set(0, (1e9 + 1) + 1, &root);

    for(const Event event : actions){
        if(event.color == -1){
            if(event.close){
                Container* child = containerQuery->query(event.y_low, event.y_high + 1);

                assert(child != NULL);

                // if(child->index == 130)
                //     fout << "Closing: " << child->index << "\n";

                colorCounts[child->index] = child->colors.size();

                if(child->parent->colors.size() < child->colors.size())
                    swap(child->parent->colors, child->colors);

                child->parent->colors.insert(child->colors.begin(), child->colors.end());

                containerQuery->set(event.y_low, event.y_high + 1, child->parent);
            }else{
                Container* parent = containerQuery->query(event.y_low, event.y_high + 1);

                assert(parent != NULL);

                parent->children.push_back(new Container(parent, event.index));
                
                containerQuery->set(event.y_low, event.y_high + 1, parent->children.back());

                // if(event.index == 130){
                //     fout << "Opening: " << event.index << " " << event.y_low << " " << event.y_high << " " << parent->index << "\n";
                //     fout << "Testing: " << containerQuery->query(966305103, 966305104)->index << "\n";
                // }
            }
        }else{
            Container* sheet = containerQuery->query(event.y_low, event.y_high + 1); 

            assert(sheet != NULL);

            // if(sheet->index == 130)
            //     fout << "Inserting into: " << sheet->index << "\n";

            // if(event.index == 33905)
            //     fout << "Wrong insert: " << sheet->index << " " << event.y_low << " " << event.y_high << "\n";

            sheet->colors.insert(event.color);
        }
    }

    for(const int &count : colorCounts)
        cout << count << "\n";
}

/*
3 9
1 1 8 8
4 2 5 3
2 5 6 7
7 4 10
4 2 1
5 2 2
5 3 3
4 3 4
2 5 1
6 5 2
6 7 3
2 7 4
*/

/*
5 5
1 1 10 10
2 2 9 9
3 3 8 8 
4 4 7 7 
5 5 6 6
1 1 1
2 2 1
3 3 1
4 4 1
5 5 1
*/

Compilation message (stderr)

plahte.cpp: In constructor 'Container::Container(Container*, int)':
plahte.cpp:11:16: warning: 'Container::parent' will be initialized after [-Wreorder]
   11 |     Container* parent;
      |                ^~~~~~
plahte.cpp:9:9: warning:   'int Container::index' [-Wreorder]
    9 |     int index;
      |         ^~~~~
plahte.cpp:14:5: warning:   when initialized here [-Wreorder]
   14 |     Container(Container* p, int i): parent(p), index(i) {}
      |     ^~~~~~~~~
plahte.cpp: In constructor 'Event::Event(int, int, int, int, bool, int)':
plahte.cpp:22:10: warning: 'Event::close' will be initialized after [-Wreorder]
   22 |     bool close;
      |          ^~~~~
plahte.cpp:18:9: warning:   'int Event::index' [-Wreorder]
   18 |     int index;
      |         ^~~~~
plahte.cpp:24:5: warning:   when initialized here [-Wreorder]
   24 |     Event(int col, int x, int yl, int yh, bool c, int i):
      |     ^~~~~

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