oj.uz

Submission #837073

# Submission time Handle Problem Language Result Execution time Memory
837073 2023-08-24T21:16:59 Z Nicolas125841 Plahte (COCI17_plahte) C++17
0 / 160
 2000 ms 492932 KB 
#include <bits/stdc++.h>

#pragma GCC optimize("unroll-loops")

using namespace std;

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

// void resolve(Container* node, vector<int> &colorCounts){
//     for(Container* child : node->children)
//         resolve(child, colorCounts);
    
//     if(node->index != -1)
//         colorCounts[node->index] = node->colors.size();
// }

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 a.y_low < b.y_low;
            else if(a.color == -1 && b.color != -1)
                return !b.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);

                // cout << "Closing: " << child->index << "\n";

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

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

                parent->children.push_back(new Container(parent, event.index));

                // cout << "Opening: " << event.index << "\n";

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

            // cout << "Inserting into: " << sheet->index << "\n";

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

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

Compilation message

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

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 747 ms 191404 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2054 ms 464020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2078 ms 473328 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2059 ms 475080 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2091 ms 492932 KB Time limit exceeded
2 Halted 0 ms 0 KB -