oj.uz

Submission #715412

# Submission time Handle Problem Language Result Execution time Memory
715412 2023-03-26T16:10:34 Z ismayil Plahte (COCI17_plahte) C++17
64 / 160
 595 ms 54284 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct segtree{
    vector<int> tree;
    int size;
    void init(int n){
        size = 1;
        while(size < n) size *= 2;
        tree.resize(2 * size - 1, 0);
    }
    void propagate(int x, int lx, int rx){
        if(tree[x] == 0 || lx == rx) return;
        tree[2 * x + 1] = tree[x];
        tree[2 * x + 2] = tree[x];
        tree[x] = 0;
    }
    void update(int l, int r, int v, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(r < lx || rx < l) return;
        if(l <= lx && rx <= r){
            tree[x] = v;
            return;
        } 
        int mx = (lx + rx) / 2;
        update(l, r, v, 2 * x + 1, lx, mx);
        update(l, r, v, 2 * x + 2, mx + 1, rx);
    }
    void update(int l, int r, int v){
        update(l, r, v, 0, 0, size - 1);
    }
    int query(int i, int x, int lx, int rx){
        propagate(x, lx, rx);
        if(lx == rx) return tree[x];
        int mx = (lx + rx) / 2;
        if(i <= mx) return query(i, 2 * x + 1, lx, mx);
        return query(i, 2 * x + 2, mx + 1, rx);
    }
    int query(int i){
        return query(i, 0, 0, size - 1);
    }
};
struct event
{
    int x, y1, y2, type, idx;
    bool operator<(event other){
        if(x == other.x) return type < other.type;
        return x < other.x;
    }
};
int parent[160001];
vector<int> adj[160001];
set<int> colors[160001];
int ans[160001];
void dfs(int u, int p){
    for(auto v : adj[u]){
        if(v != p){
            dfs(v, u);
            if(colors[u].size() < colors[v].size()) swap(colors[u], colors[v]);
            for(auto i : colors[v]){
                colors[u].insert(i);
            }
        }
    }
    ans[u] = colors[u].size();
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<event> events;
    int squares[n + 1][4];
    int points[m + 1][2];
    map<int, int> d;
    for (int i = 1; i <= n; i++)
    {
        cin >> squares[i][0] >> squares[i][1] >> squares[i][2] >> squares[i][3];
        d[squares[i][1]]; d[squares[i][3]];
        //events.push_back({x1, y1, y2, 0, i});
        //events.push_back({x2, y1, y2, 2, i});
    }
    for(int i = 1; i <= m; i++){
        int c;
        cin >> points[i][0] >> points[i][1] >> c;
        d[points[i][1]];
        colors[i + n].insert(c);
        //events.push_back({x, y, y, 1, i});
    }
    int idx = 0;
    for(auto& i : d){
        i.second = ++idx;
    }
    for (int i = 1; i <= n; i++)
    {
        events.push_back({squares[i][0], d[squares[i][1]], d[squares[i][3]], 0, i});
        events.push_back({squares[i][2], d[squares[i][1]], d[squares[i][3]], 2, i});
    }
    for(int i = 1; i <= m; i++){
        events.push_back({points[i][0], d[points[i][1]], d[points[i][1]], 1, i + n});
    }
    sort(events.begin(), events.end());
    segtree st;
    st.init(idx);
    for(auto i : events){
        if(i.type == 0){
            parent[i.idx] = st.query(i.y1);
            adj[parent[i.idx]].push_back(i.idx);
            adj[i.idx].push_back(parent[i.idx]);
            st.update(i.y1, i.y2, i.idx);
        }else if(i.type == 1){
            parent[i.idx] = st.query(i.y1);
            adj[parent[i.idx]].push_back(i.idx);
            adj[i.idx].push_back(parent[i.idx]);
        }else{
            st.update(i.y1, i.y2, parent[i.idx]);
        }
    }
    /*for(int i = 1; i <= n + m; i++){
        cout << i << " : ";
        for(auto j : adj[i]){
            cout << j << ", ";
        }
        cout << endl;
    }*/
    dfs(0, -1);
    for(int i = 1; i <= n; i++)
        cout<<ans[i]<<endl;
}

Subtask #1
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 25564 KB Output is correct
2 Incorrect 143 ms 26324 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 27748 KB Output is correct
2 Correct 181 ms 27056 KB Output is correct
3 Incorrect 6 ms 11604 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 40176 KB Output is correct
2 Correct 349 ms 35892 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 587 ms 54284 KB Output is correct
2 Correct 571 ms 49792 KB Output is correct
3 Correct 7 ms 11604 KB Output is correct

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 595 ms 52616 KB Output is correct
2 Incorrect 564 ms 48744 KB Output isn't correct
3 Halted 0 ms 0 KB -