제출 #361257

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
361257		RyoPham	도로 건설 사업 (JOI13_construction)	C++14	40 / 100	715 ms	222444 KiB

construction

#define taskname "test"

#include <bits/stdc++.h>

using namespace std;

#define sz(x) (int)x.size()
#define fi first
#define se second

typedef long long lli;
typedef pair<int, int> pii;

const int maxn = 5e5 + 5;

int n, m, Q;
int x[maxn], y[maxn];
int xl[maxn], yl[maxn], xr[maxn], yr[maxn];

int qB[maxn], qH[maxn];

vector<int> ox, oy;

vector<pii> posX[maxn], posY[maxn];
vector<pii> queryYY_x[maxn], queryXX_y[maxn];

vector<pii> addX[maxn], delX[maxn];
vector<pii> addY[maxn], delY[maxn];

vector<pair<int, pii>> edges;

struct segment_tree
{
    int max_val[maxn * 4], lazy[maxn * 4];

    void init()
    {
        fill(begin(max_val), end(max_val), 0);
        fill(begin(lazy), end(lazy), 0);
    }

    void push(int x)
    {
        if(lazy[x] == 0) return;
        int t = lazy[x];

        for(int i = x * 2; i <= x * 2 + 1; ++i)
        {
            lazy[i] += t;
            max_val[i] += t;
        }

        lazy[x] = 0;
    }

    void update(int x, int l, int r, int L, int R, int k)
    {
        if(L > r || l > R) return;
        if(l >= L && r <= R)
        {
            max_val[x] += k;
            lazy[x] += k;
            return;
        }
        push(x);
        int mid = (l + r) / 2;
        update(x * 2, l, mid, L, R, k);
        update(x * 2 + 1, mid + 1, r, L, R, k);
        max_val[x] = max(max_val[x * 2], max_val[x * 2 + 1]);
    }

    int get(int x, int l, int r, int L, int R)
    {
        if(L > r || l > R) return 0;
        if(l >= L && r <= R)
            return max_val[x];
        push(x);
        int mid = (l + r) / 2;
        return max(get(x * 2, l, mid, L, R),
                   get(x * 2 + 1, mid + 1, r, L, R));
    }
} tree;

void read_input()
{
    cin >> n >> m >> Q;
    for(int i = 1; i <= n; ++i)
        cin >> x[i] >> y[i];
    for(int i = 1; i <= m; ++i)
        cin >> xl[i] >> yl[i] >> xr[i] >> yr[i];
    for(int i = 1; i <= Q; ++i)
        cin >> qB[i] >> qH[i];
}

int lwb(const vector<int>&arr, int k)
{
    return lower_bound(arr.begin(), arr.end(), k) - arr.begin() + 1;
}

void init()
{
    /// compress
    for(int i = 1; i <= n; ++i)
    {
        ox.push_back(x[i]);
        oy.push_back(y[i]);
    }
    for(int i = 1; i <= m; ++i)
    {
        ox.push_back(xl[i]);
        ox.push_back(xr[i]);
        oy.push_back(yl[i]);
        oy.push_back(yr[i]);
    }
    sort(ox.begin(), ox.end());
    ox.erase(unique(ox.begin(), ox.end()), ox.end());
    sort(oy.begin(), oy.end());
    oy.erase(unique(oy.begin(), oy.end()), oy.end());
    for(int i = 1; i <= n; ++i)
    {
        x[i] = lwb(ox, x[i]);
        y[i] = lwb(oy, y[i]);
        posX[y[i]].push_back(pii(x[i], i));
        posY[x[i]].push_back(pii(y[i], i));
    }
    for(int i = 1; i <= m; ++i)
    {
        xl[i] = lwb(ox, xl[i]);
        xr[i] = lwb(ox, xr[i]);
        yl[i] = lwb(oy, yl[i]);
        yr[i] = lwb(oy, yr[i]);
    }

    /// make queries
    for(int x = 1; x <= sz(ox); ++x)
    {
        sort(posY[x].begin(), posY[x].end());
        for(int i = 1; i < sz(posY[x]); ++i)
            queryYY_x[x].push_back(pii(posY[x][i - 1].se, posY[x][i].se));
    }
    for(int y = 1; y <= sz(oy); ++y)
    {
        sort(posX[y].begin(), posX[y].end());
        for(int i = 1; i < sz(posX[y]); ++i)
            queryXX_y[y].push_back(pii(posX[y][i - 1].se, posX[y][i].se));
    }
    for(int i = 1; i <= m; ++i)
    {
        addX[xl[i]].push_back(pii(yl[i], yr[i]));
        delX[xr[i]].push_back(pii(yl[i], yr[i]));

        addY[yl[i]].push_back(pii(xl[i], xr[i]));
        delY[yr[i]].push_back(pii(xl[i], xr[i]));
    }


    /// solve all queries
    tree.init();
    for(int x = 1; x <= sz(ox); ++x)
    {
        for(auto&to: addX[x])
            tree.update(1, 1, sz(oy), to.fi, to.se, 1);
        for(auto&to: queryYY_x[x])
        {
            int i = to.fi, j = to.se;
            int l = y[i], r = y[j];
            if(tree.get(1, 1, sz(oy), l, r) > 0) continue;
            edges.push_back(make_pair(oy[y[j] - 1] - oy[y[i] - 1], pii(i, j)));
        }
        for(auto&to: delX[x])
            tree.update(1, 1, sz(oy), to.fi, to.se, -1);
    }
    tree.init();
    for(int y = 1; y <= sz(oy); ++y)
    {
        for(auto&to: addY[y])
            tree.update(1, 1, sz(ox), to.fi, to.se, 1);
        for(auto&to: queryXX_y[y])
        {
            int i = to.fi, j = to.se;
            int l = x[i], r = x[j];
            if(tree.get(1, 1, sz(ox), l, r) > 0) continue;
            edges.push_back(make_pair(ox[x[j] - 1] - ox[x[i] - 1], pii(i, j)));
        }
        for(auto&to: delY[y])
            tree.update(1, 1, sz(ox), to.fi, to.se, -1);
    }
}

int lab[maxn];
int cnt = 0;
int arr[maxn];

int find_set(int u)
{
    return lab[u] < 0 ? u : lab[u] = find_set(lab[u]);
}

bool union_sets(int u, int v)
{
    u = find_set(u); v = find_set(v);
    if(u == v) return false;
    if(lab[u] < lab[v]) swap(u, v);
    lab[v] += lab[u];
    lab[u] = v;
    return true;
}

lli pref[maxn];

void solve()
{
    sort(edges.begin(), edges.end());
    //for(auto&to: edges) cerr << to.fi << ' ' << to.se.fi << ' ' << to.se.se << '\n';
    fill(lab + 1, lab + n + 1, -1);
    int ncc = n;
    for(auto&e: edges)
    {
        int w = e.fi;
        int u = e.se.fi, v = e.se.se;
        if(union_sets(u, v))
        {
            arr[++cnt] = w;
            --ncc;
        }
    }

    reverse(arr + 1, arr + cnt + 1);
    pref[0] = 0;
    for(int i = 1; i <= cnt; ++i)
        pref[i] = pref[i - 1] + arr[i];

    for(int i = 1; i <= Q; ++i)
    {
        int B = qB[i], H = qH[i];
        if(H < ncc)
        {
            cout << "-1\n";
            continue;
        }
        H -= ncc;
        int low = 1, high = min(cnt, H);
        while(low <= high)
        {
            int mid = (low + high) / 2;
            if(arr[mid] > B)
                low = mid + 1;
            else high = mid - 1;
        }
        cout << pref[cnt] - pref[high] + B * 1LL * (high + ncc) << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    read_input();
    init();
    solve();
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30