oj.uz

답안 #361259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361259 2021-01-29T01:19:54 Z RyoPham 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 2070 ms 209992 KB 
#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 = 6e5 + 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 133228 KB Output is correct
2 Correct 493 ms 150100 KB Output is correct
3 Correct 463 ms 150100 KB Output is correct
4 Correct 391 ms 152660 KB Output is correct
5 Correct 469 ms 152400 KB Output is correct
6 Correct 462 ms 150276 KB Output is correct
7 Correct 263 ms 150952 KB Output is correct
8 Correct 341 ms 151504 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 133228 KB Output is correct
2 Correct 493 ms 150100 KB Output is correct
3 Correct 463 ms 150100 KB Output is correct
4 Correct 391 ms 152660 KB Output is correct
5 Correct 469 ms 152400 KB Output is correct
6 Correct 462 ms 150276 KB Output is correct
7 Correct 263 ms 150952 KB Output is correct
8 Correct 341 ms 151504 KB Output is correct
9 Correct 1948 ms 178928 KB Output is correct
10 Correct 1884 ms 190100 KB Output is correct
11 Correct 1901 ms 189996 KB Output is correct
12 Correct 1912 ms 189932 KB Output is correct
13 Correct 800 ms 168900 KB Output is correct
14 Correct 482 ms 156368 KB Output is correct
15 Correct 1859 ms 190164 KB Output is correct
16 Correct 574 ms 176572 KB Output is correct
17 Correct 548 ms 176188 KB Output is correct
18 Correct 971 ms 183108 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 133228 KB Output is correct
2 Correct 493 ms 150100 KB Output is correct
3 Correct 463 ms 150100 KB Output is correct
4 Correct 391 ms 152660 KB Output is correct
5 Correct 469 ms 152400 KB Output is correct
6 Correct 462 ms 150276 KB Output is correct
7 Correct 263 ms 150952 KB Output is correct
8 Correct 341 ms 151504 KB Output is correct
9 Correct 679 ms 161876 KB Output is correct
10 Correct 668 ms 160436 KB Output is correct
11 Correct 628 ms 158420 KB Output is correct
12 Correct 556 ms 160740 KB Output is correct
13 Correct 585 ms 156632 KB Output is correct
14 Correct 714 ms 163120 KB Output is correct
15 Correct 698 ms 161364 KB Output is correct
16 Correct 678 ms 160860 KB Output is correct
17 Correct 437 ms 159940 KB Output is correct
18 Correct 553 ms 160440 KB Output is correct

Subtask #4
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 133 ms 133228 KB Output is correct
2 Correct 493 ms 150100 KB Output is correct
3 Correct 463 ms 150100 KB Output is correct
4 Correct 391 ms 152660 KB Output is correct
5 Correct 469 ms 152400 KB Output is correct
6 Correct 462 ms 150276 KB Output is correct
7 Correct 263 ms 150952 KB Output is correct
8 Correct 341 ms 151504 KB Output is correct
9 Correct 1948 ms 178928 KB Output is correct
10 Correct 1884 ms 190100 KB Output is correct
11 Correct 1901 ms 189996 KB Output is correct
12 Correct 1912 ms 189932 KB Output is correct
13 Correct 800 ms 168900 KB Output is correct
14 Correct 482 ms 156368 KB Output is correct
15 Correct 1859 ms 190164 KB Output is correct
16 Correct 574 ms 176572 KB Output is correct
17 Correct 548 ms 176188 KB Output is correct
18 Correct 971 ms 183108 KB Output is correct
19 Correct 679 ms 161876 KB Output is correct
20 Correct 668 ms 160436 KB Output is correct
21 Correct 628 ms 158420 KB Output is correct
22 Correct 556 ms 160740 KB Output is correct
23 Correct 585 ms 156632 KB Output is correct
24 Correct 714 ms 163120 KB Output is correct
25 Correct 698 ms 161364 KB Output is correct
26 Correct 678 ms 160860 KB Output is correct
27 Correct 437 ms 159940 KB Output is correct
28 Correct 553 ms 160440 KB Output is correct
29 Correct 2050 ms 209992 KB Output is correct
30 Correct 1224 ms 182896 KB Output is correct
31 Correct 2007 ms 203456 KB Output is correct
32 Correct 598 ms 165212 KB Output is correct
33 Correct 1986 ms 203756 KB Output is correct
34 Correct 647 ms 166616 KB Output is correct
35 Correct 1798 ms 204804 KB Output is correct
36 Correct 2070 ms 208068 KB Output is correct
37 Correct 715 ms 191420 KB Output is correct
38 Correct 1110 ms 196036 KB Output is correct
39 Correct 591 ms 171688 KB Output is correct