Submission #1247919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247919		tvgk	절취선 (JOI14_ho_t5)	C++20	100 / 100	706 ms	69532 KiB

2014_ho_t5

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 1e5 + 7, inf = 1e9 + 7;

int nRow, nCol, n, cnt[mxN * 4], lazy[mxN * 4], dsu[mxN];
ii u[mxN], v[mxN], tree[mxN * 4];
map<int, int> m[mxN * 4];
vector<int> hor[mxN], ver[mxN], Col, Row;

void Build(int j = 1, int l = 0, int r = Col.size() - 1)
{
    lazy[j] = -1;
    if (l == r)
    {
        tree[j] = {inf, l};
        return;
    }

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
    tree[j] = min(tree[j * 2], tree[j * 2 + 1]);
}

void Ers(int j)
{
    for (ii i : m[j])
    {
        int tmp = j / 2;
        while (tmp)
        {
            m[tmp][i.fi] -= i.se;
            if (!m[tmp][i.fi])
                m[tmp].erase(i.fi);
            tmp /= 2;
        }
    }
    m[j].clear();
}

void Down(int j)
{
    if (lazy[j] == -1)
        return;

    for (int u = 0; u <= 1; u++)
    {
        lazy[j * 2 + u] = lazy[j];
        m[j * 2 + u].clear();
        if (cnt[j * 2 + u])
            m[j * 2 + u][lazy[j]] = cnt[j * 2 + u];
    }
    lazy[j] = -1;
}

void Cut(int vt, int j = 1, int l = 0, int r = Col.size() - 1)
{
    if (l > vt || vt > r)
        return;

    cnt[j]--;
    if (l == r)
    {
        tree[j].fi = inf;
        Ers(j);
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Cut(vt, j * 2, l, mid);
    Cut(vt, j * 2 + 1, mid + 1, r);
    tree[j] = min(tree[j * 2], tree[j * 2 + 1]);
}

void Upd(int vt, int h, int val, int j = 1, int l = 0, int r = Col.size() - 1)
{
    if (l > vt || vt > r)
        return;

    cnt[j]++;
    m[j][val]++;
    tree[j] = min(tree[j], {h, vt});
    if (l == r)
        return;
    Down(j);

    int mid = (l + r) / 2;
    Upd(vt, h, val, j * 2, l, mid);
    Upd(vt, h, val, j * 2 + 1, mid + 1, r);
}

int Find(int j)
{
    if (dsu[j] == j)
        return j;
    else
        return dsu[j] = Find(dsu[j]);
}

bool Union(int u, int v)
{
    u = Find(u);
    v = Find(v);

    if (u == v)
        return 0;

    dsu[v] = u;
    return 1;
}

int mem;
int Get(int u, int v, int id, int j = 1, int l = 0, int r = Col.size() - 1)
{
    if (u > Col[r] || Col[l] > v || !cnt[j])
        return 0;

    if (u <= Col[l] && Col[r] <= v)
    {
        lazy[j] = id;

        for (ii i : m[j])
            mem += Union(id, i.fi);
        Ers(j);
        m[j][id] = cnt[j];
        return cnt[j];
    }
    Down(j);

    int mid = (l + r) / 2;
    int res = Get(u, v, id, j * 2, l, mid) + Get(u, v, id, j * 2 + 1, mid + 1, r);
    if (res)
        m[j][id] = res;
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> nRow >> nCol >> n;

    // Nen bang
    Row.push_back(0);
    Row.push_back(nRow);
    Col.push_back(0);
    Col.push_back(nCol);
    for (int i = 1; i <= n; i++)
    {
        cin >> u[i].fi >> u[i].se >> v[i].fi >> v[i].se;
        Row.push_back(u[i].fi);

        // Chi nen cot
        if (u[i].se == v[i].se)
            Col.push_back(v[i].se);
    }
    sort(Row.begin(), Row.end());
    Row.erase(unique(Row.begin(), Row.end()), Row.end());
    sort(Col.begin(), Col.end());
    Col.erase(unique(Col.begin(), Col.end()), Col.end());

    // Tao thu tu Sweepline
    n++;
    u[n] = {nRow, 0};
    v[n] = {nRow, nCol};
    for (int i = 1; i <= n; i++)
    {
        dsu[i] = i;

        int j = lower_bound(Row.begin(), Row.end(), u[i].fi) - Row.begin();
        if (u[i].fi == v[i].fi)
            hor[j].push_back(i);
        else
            ver[j].push_back(i);
    }

    Build();
    Upd(0, nRow, 0);
    Upd(Col.size() - 1, nRow, 0);
    ll ans = 0;
    for (int i = 0; i < Row.size(); i++)
    {
        // Cat doan het
        while (tree[1].fi < Row[i])
            Cut(tree[1].se);

        // Upd doan doc
        for (int j : ver[i])
            Upd(lower_bound(Col.begin(), Col.end(), u[j].se) - Col.begin(), v[j].fi, j * (i != 0));

        // Upd doan ngang
        for (int j : hor[i])
        {
            mem = 0;
            ans += Get(u[j].se, v[j].se, j) - mem;
        }
    }
    cout << ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50