oj.uz

Submission #715434

# Submission time Handle Problem Language Result Execution time Memory
715434 2023-03-26T17:11:51 Z ismayil Plahte (COCI17_plahte) C++17
160 / 160
 655 ms 65324 KB 
#include <bits/stdc++.h>
#define int 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] == -1 || lx == rx) return;
        tree[2 * x + 1] = tree[x];
        tree[2 * x + 2] = tree[x];
        tree[x] = -1;
    }
    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[160002];
vector<int> adj[160002];
set<int> colors[160002];
int ans[160002];
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();
}
signed 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){
        //cout << i.x << " " << i.y1 << " " << i.y2 << " " << i.type << " " << i.idx << endl;
        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);
            //cout << "query " << st.query(i.y1) << endl;
            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]);
            //cout<<"clear "<<i.y1 << " " << i.y2 << " " << parent[i.idx] << endl;
        }
    }

    dfs(0, -1);
    for(int i = 1; i <= n; i++)
        cout<<ans[i]<<endl;
}

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 28976 KB Output is correct
2 Correct 150 ms 29496 KB Output is correct
3 Correct 6 ms 11612 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 31608 KB Output is correct
2 Correct 184 ms 30868 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 46856 KB Output is correct
2 Correct 340 ms 41316 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 65324 KB Output is correct
2 Correct 655 ms 60812 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 63728 KB Output is correct
2 Correct 581 ms 59208 KB Output is correct
3 Correct 6 ms 11604 KB Output is correct