oj.uz

Submission #544130

# Submission time Handle Problem Language Result Execution time Memory
544130 2022-04-01T06:07:27 Z Sorting Plahte (COCI17_plahte) C++17
160 / 160
 292 ms 44800 KB 
#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];
int ans[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){
        b[i] = lower_bound(all(val), b[i]) - val.begin();
        d[i] = lower_bound(all(val), d[i]) - val.begin();
    }

    for(int i = 0; i < m; ++i)
        y[i] = lower_bound(all(val), y[i]) - 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]);
            // cout << pr[i] << " " << i << " pr[i] i" <<endl;
            if(pr[i] != -1){
                // if(pr[i] < i)
                    adj[pr[i]].push_back(i);
                // else
                    // adj[i].push_back(pr[i]);
            }
            // if(pr[i] < 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[u].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);
        }
        ans[u] = s[u].size(); 
    };

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

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

Subtask #1
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 27716 KB Output is correct
2 Correct 94 ms 30028 KB Output is correct
3 Correct 12 ms 20948 KB Output is correct

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 28776 KB Output is correct
2 Correct 112 ms 29872 KB Output is correct
3 Correct 10 ms 21076 KB Output is correct

Subtask #3
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 34392 KB Output is correct
2 Correct 174 ms 35164 KB Output is correct
3 Correct 11 ms 20948 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 290 ms 44036 KB Output is correct
2 Correct 292 ms 44800 KB Output is correct
3 Correct 11 ms 21012 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 42304 KB Output is correct
2 Correct 287 ms 44268 KB Output is correct
3 Correct 11 ms 21060 KB Output is correct