Submission #1108804

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108804		juliany2	Plahte (COCI17_plahte)	C++17	160 / 160	322 ms	74988 KiB

plahte

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()

template<class T> struct LZ_ST {
    static constexpr T ID = 2e9, LZ_ID = -1; // or whatever ID
    inline T comb(T a, T b) { return min(a, b); } // or whatever function
 
    int sz;
    vector<T> t, lz;
 
    void init(int _sz, T val = ID) {
        sz = _sz;
        t.assign(sz * 4, val);
        lz.assign(sz * 4, LZ_ID);
    }
    inline void push(int l, int r, int v) {
        if (lz[v] != LZ_ID && l != r) { // might have to change
            int m = l + r >> 1;
            //change if set (=) or adding(+=) on range
            t[v * 2] = lz[v];
            t[v * 2 + 1] = lz[v];
            lz[v * 2] = lz[v];
            lz[v * 2 + 1] = lz[v];
        }
        lz[v] = LZ_ID;
    }
    void upd(int ql, int qr, T x, int l, int r, int v) {
        if (qr < l || ql > r) return;
        if (l >= ql && r <= qr) // might have to change, same as above
            t[v] = x, lz[v] = x;
        else {
            push(l, r, v);
            int m = l + r >> 1;
            upd(ql, qr, x, l, m, v * 2);
            upd(ql, qr, x, m + 1, r, v * 2 + 1);
            t[v] = comb(t[v * 2], t[v * 2 + 1]);
        }
    }
    void upd(int ql, int qr, T x) {
        return upd(ql, qr, x, 0, sz - 1, 1);
    }
    T query(int ql, int qr, int l, int r, int v) {
        if (qr < l || ql > r) return ID;
        if (l >= ql && r <= qr) return t[v];
        push(l, r, v);
        int m = l + r >> 1;
        return comb(query(ql, qr, l, m, v * 2), query(ql, qr, m + 1, r, v * 2 + 1));
    }
    T query(int ql, int qr) {
        return query(ql, qr, 0, sz - 1, 1);
    }
    T query(int x) {
        return query(x, x);
    }
};

const int N = 3e5 + 7;
int n, m;
array<int, 4> a[N];
array<int, 3> b[N];
vector<int> e[N], qry[N], adj[N];
set<int> s[N];
int p[N], ans[N];
LZ_ST<int> st;

void dfs(int v = 0, int p = -1) {
    for (int u : adj[v]) {
        if (u == p)
            continue;

        dfs(u, v);

        if (s[u].size() > s[v].size())
            s[u].swap(s[v]);

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

    ans[v] = s[v].size();
}

int main() {
    cin.tie(0)->sync_with_stdio(false);

    cin >> n >> m;

    vector<int> x, y;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1] >> a[i][2] >> a[i][3];
        x.push_back(a[i][0]);
        y.push_back(a[i][1]);
        x.push_back(a[i][2]);
        y.push_back(a[i][3]);
    }

    for (int i = 1; i <= m; i++) {
        cin >> b[i][0] >> b[i][1] >> b[i][2];
        x.push_back(b[i][0]);
        y.push_back(b[i][1]);
    }

    sort(all(x));
    x.erase(unique(all(x)), x.end());
    sort(all(y));
    y.erase(unique(all(y)), y.end());

    for (int i = 1; i <= n; i++) {
        a[i][0] = lower_bound(all(x), a[i][0]) - x.begin();
        a[i][1] = lower_bound(all(y), a[i][1]) - y.begin();
        a[i][2] = lower_bound(all(x), a[i][2]) - x.begin();
        a[i][3] = lower_bound(all(y), a[i][3]) - y.begin();

        e[a[i][0]].push_back(i);
        e[a[i][2] + 1].push_back(-i);
    }

    for (int i = 1; i <= m; i++) {
        b[i][0] = lower_bound(all(x), b[i][0]) - x.begin();
        b[i][1] = lower_bound(all(y), b[i][1]) - y.begin();

        qry[b[i][0]].push_back(i);
    }

    st.init(N, 0);

    for (int i = 0; i < N; i++) {
        for (int j : e[i]) {
            if (j < 0) {
                j = -j;
                st.upd(a[j][1], a[j][3], p[j]);
            }
        }

        for (int j : e[i]) {
            if (j > 0) {
                p[j] = st.query(a[j][1]);
                st.upd(a[j][1], a[j][3], j);
            }
        }

        for (int j : qry[i]) {
            int t = st.query(b[j][1]);
            s[t].insert(b[j][2]);
        }
    }

    for (int i = 1; i <= n; i++) {
        adj[p[i]].push_back(i);
    }

    dfs();

    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';

    return 0;
}

Compilation message (stderr)

plahte.cpp: In instantiation of 'void LZ_ST<T>::upd(int, int, T, int, int, int) [with T = int]':
plahte.cpp:42:19:   required from 'void LZ_ST<T>::upd(int, int, T) [with T = int]'
plahte.cpp:133:46:   required from here
plahte.cpp:35:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |             int m = l + r >> 1;
      |                     ~~^~~
plahte.cpp: In instantiation of 'void LZ_ST<T>::push(int, int, int) [with T = int]':
plahte.cpp:34:13:   required from 'void LZ_ST<T>::upd(int, int, T, int, int, int) [with T = int]'
plahte.cpp:42:19:   required from 'void LZ_ST<T>::upd(int, int, T) [with T = int]'
plahte.cpp:133:46:   required from here
plahte.cpp:20:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   20 |             int m = l + r >> 1;
      |                     ~~^~~
plahte.cpp:20:17: warning: unused variable 'm' [-Wunused-variable]
   20 |             int m = l + r >> 1;
      |                 ^
plahte.cpp: In instantiation of 'T LZ_ST<T>::query(int, int, int, int, int) [with T = int]':
plahte.cpp:52:21:   required from 'T LZ_ST<T>::query(int, int) [with T = int]'
plahte.cpp:55:21:   required from 'T LZ_ST<T>::query(int) [with T = int]'
plahte.cpp:139:40:   required from here
plahte.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |         int m = l + r >> 1;
      |                 ~~^~~

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