Submission #543745

#	Time	Username	Problem	Language	Result	Execution time	Memory
543745		Sorting	Plahte (COCI17_plahte)	C++17	0 / 160	627 ms	199964 KiB

plahte

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
template<class T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; }
template<class T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; }
#define all(x) (x).begin(), (x).end()

const int N = 24e4 + 3;

struct SegmentTree{
    int lp[4 * N];
    bool b[4 * N];

    SegmentTree(){
        fill(lp, lp + 4 * N, -1);
    }

    void push_lazy(int i, int l, int r){
        if(!b[i]) return;
        if(l == r) return;
        b[2 * i + 1] = true;
        b[2 * i + 2] = true;
        lp[2 * i + 1] = lp[i];
        lp[2 * i + 2] = lp[i];
        lp[i] = -1;
        b[i] = false;
    }

    void update(int sl, int sr, int val, int i = 0, int l = 0, int r = N - 1){
        push_lazy(i, l, r);
        if(sr < l || r < sl) return;
        if(sl <= l && r <= sr){
            lp[i] = val;
            b[i] = true; 
            push_lazy(i, l, r);
            return;
        }
        int mid = (l + r) >> 1;
        update(sl, sr, val, 2 * i + 1, l, mid);
        update(sl, sr, val, 2 * i + 2, mid + 1, r);
    }

    int query(int s_idx, int i = 0, int l = 0, int r = N - 1){
        push_lazy(i, l, r);
        if(s_idx < l || r < s_idx) return -1;
        if(l == r) return lp[i];
        int mid = (l + r) >> 1;
        return max(query(s_idx, 2 * i + 1, l, mid), query(s_idx, 2 * i + 2, mid + 1, r));
    }
} st;

int n, m;
int a[N], b[N], c[N], d[N], x[N], y[N], k[N];
vector<int> adj[N];
int pr[N];
bool vis[N];

set<int> s[N];

vector<int> val;
vector<array<int, 3>> sweepline;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> a[i] >> b[i];
        cin >> c[i] >> d[i];
        val.push_back(b[i]);
        val.push_back(d[i]);
    }
    for(int i = 0; i < m; ++i){
        cin >> x[i] >> y[i] >> k[i];
        val.push_back(y[i]);
    }
    sort(all(val));
    val.resize(unique(all(val)) - val.begin());

    for(int i = 0; i < n; ++i){
        sweepline.push_back({a[i], 0, i});
        sweepline.push_back({c[i], 2, i});
    }

    for(int i = 0; i < m; ++i){
        sweepline.push_back({x[i], 1, i});
    }

    sort(all(sweepline));
    for(auto [x, type, i]: sweepline){
        if(type == 0){
            pr[i] = st.query(b[i]);
            if(pr[i] != -1)
                adj[pr[i]].push_back(i);
            st.update(b[i], d[i], i);
        }
        else if(type == 2){
            st.update(b[i], d[i], pr[i]);
        }
        else{
            int idx = st.query(y[i]);
            if(idx != -1)
                adj[idx].push_back(i + n);
        }
    }

    for(int i = 0; i < m; ++i){
        s[i + n].insert(k[i]);
        vis[i + n] = true;
    }

    auto merge = [&](int u, int to){
        if(s[to].size() < s[to].size())
            swap(s[u], s[to]);

        for(int x: s[to])
            s[u].insert(x);
    };

    function<void(int)> dfs = [&](int u){
        vis[u] = true;
        for(int to: adj[u]){
            if(!vis[to])
                dfs(to);
            merge(u, to);
        }
    };

    for(int i = 0; i < n; ++i)
        if(!vis[i])
            dfs(i);

    for(int i = 0; i < n; ++i)
        cout << s[i].size() << "\n";
}

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