Submission #738573

#	Time	Username	Problem	Language	Result	Execution time	Memory
738573		GrindMachine	Plahte (COCI17_plahte)	C++17	0 / 160	2076 ms	147516 KiB

plahte

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 8e4 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

template<typename T>
struct segtree {
    // https://codeforces.com/blog/entry/18051

    /*=======================================================*/

    struct data {
        set<pii> st;
    };

    data neutral = {};

    data merge(data &left, data &right) {
        return data();
    }

    void create(int i, T v) {

    }

    void modify(int i, T v) {

    }

    /*=======================================================*/

    int n;
    vector<data> tr;

    segtree() {

    }

    segtree(int siz) {
        init(siz);
    }

    void init(int siz) {
        n = siz;
        tr.assign(2 * n, neutral);
    }

    void build(vector<T> &a, int siz) {
        rep(i, siz) create(i + n, a[i]);
        rev(i, n - 1, 1) tr[i] = merge(tr[i << 1], tr[i << 1 | 1]);
    }

    void pupd(int i, T v) {
        pii p = {v[1], v[2]};

        for (i += n; i; i >>= 1) {
            if (v[0] == 1) {
                tr[i].st.insert(p);
            }
            else {
                tr[i].st.erase(p);
            }
        }
    }

    vector<pii> query(int l, int r, int mn, int mx) {
        vector<pii> res;
        pii key = {mn, -1};

        for (l += n, r += n; l <= r; l >>= 1, r >>= 1) {
            if (l & 1) {
                auto &st = tr[l++].st;
                auto it = st.lower_bound(key);
                vector<pii> toerase;

                for (; it != st.end() and it->first <= mx; ++it) {
                    res.pb(*it);
                    toerase.pb(*it);
                }

                trav(p, toerase) {
                    st.erase(p);
                }
            }

            if (!(r & 1)) {
                auto &st = tr[r--].st;
                auto it = st.lower_bound(key);
                vector<pii> toerase;

                for (; it != st.end() and it->first <= mx; ++it) {
                    res.pb(*it);
                    toerase.pb(*it);
                }

                trav(p, toerase) {
                    st.erase(p);
                }
            }
        }

        return res;
    }
};

vector<int> adj[N];
vector<int> subsiz(N);
set<int> here[N];

void dfs1(int u, int p) {
    subsiz[u] = sz(here[u]);
    trav(v, adj[u]) {
        if (v == p) conts;
        dfs1(v, u);
        subsiz[u] += subsiz[v];
    }
}

vector<int> ans(N);
set<int> st[N];

void dfs2(int u, int p) {
    int mx = -1, largest = -1;
    trav(v, adj[u]) {
        if (v == p) conts;
        if (subsiz[v] > mx) {
            mx = subsiz[v];
            largest = v;
        }
    }

    if (largest != -1) {
        dfs2(largest, u);
        swap(st[u], st[largest]);
    }

    trav(v, adj[u]) {
        if (v == p or v == largest) conts;
        dfs2(v, u);

        trav(x, st[v]) {
            st[u].insert(x);
        }

        st[v].clear();
    }

    trav(x, here[u]) {
        st[u].insert(x);
    }

    ans[u] = sz(st[u]);
}

void solve(int test_case)
{
    auto start = chrono::steady_clock::now();

    int n, m; cin >> n >> m;
    vector<array<int, 4>> a(n);
    vector<array<int, 3>> b(m);
    rep(i, n) rep(j, 4) cin >> a[i][j];
    rep(i, m) rep(j, 3) cin >> b[i][j];

    vector<pair<ll, int>> process_order;
    rep(i, n) {
        ll area = (ll) (a[i][2] - a[i][0]) * (a[i][3] - a[i][1]);
        process_order.pb({area, i});
    }

    sort(all(process_order));

    vector<pii> points;
    rep(i, n) points.pb({a[i][0], a[i][1]});
    rep(i, m) points.pb({b[i][0], b[i][1]});
    sort(all(points));
    points.resize(unique(all(points)) - points.begin());
    int siz = sz(points);

    segtree<array<int, 3>> st(siz + 5);
    vector<int> par(n, -1);

    rep(j, m) {
        auto [x, y, c] = b[j];
        pii p = {x, y};
        int ind = lower_bound(all(points), p) - points.begin();
        st.pupd(ind, {1, y, j + n});
    }

    for (auto [area, i] : process_order) {
        auto [x1, y1, x2, y2] = a[i];
        pii p = {x1, -1};
        int l = lower_bound(all(points), p) - points.begin();
        p = {x2 + 1, -1};
        int r = upper_bound(all(points), p) - points.begin() - 1;

        vector<pii> guys = st.query(l, r, y1, y2);

        for (auto [mny, j] : guys) {
            if (j < n) {
                adj[i].pb(j);
                par[j] = i;
            }
            else {
                j -= n;
                here[i].insert(b[j][2]);
            }
        }

        p = {x1, y1};
        int ind = lower_bound(all(points), p) - points.begin();
        st.pupd(ind, {1, a[i][1], i});
    }

    auto end = chrono::steady_clock::now();
    auto diff = end - start;

    double elapsed = chrono::duration <double, milli> (diff).count();
    // if (elapsed > 1200) {
    //     exit(1);
    // }

    rep(i, n) {
        if (par[i] == -1) {
            dfs1(i, -1);
            dfs2(i, -1);
        }
    }

    rep(i, n) cout << ans[i] << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

plahte.cpp: In function 'void solve(int)':
plahte.cpp:274:12: warning: unused variable 'elapsed' [-Wunused-variable]
  274 |     double elapsed = chrono::duration <double, milli> (diff).count();
      |            ^~~~~~~

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