oj.uz

Submission #361258

# Submission time Handle Problem Language Result Execution time Memory
361258 2021-01-29T01:06:07 Z RyoPham 도로 건설 사업 (JOI13_construction) C++14
40 / 100
 875 ms 262148 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 = 1e6 + 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

# Verdict Execution time Memory Grader output
1 Correct 178 ms 221292 KB Output is correct
2 Correct 515 ms 238676 KB Output is correct
3 Correct 555 ms 238676 KB Output is correct
4 Correct 440 ms 241288 KB Output is correct
5 Correct 525 ms 240976 KB Output is correct
6 Correct 526 ms 238792 KB Output is correct
7 Correct 308 ms 239556 KB Output is correct
8 Correct 402 ms 240156 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 221292 KB Output is correct
2 Correct 515 ms 238676 KB Output is correct
3 Correct 555 ms 238676 KB Output is correct
4 Correct 440 ms 241288 KB Output is correct
5 Correct 525 ms 240976 KB Output is correct
6 Correct 526 ms 238792 KB Output is correct
7 Correct 308 ms 239556 KB Output is correct
8 Correct 402 ms 240156 KB Output is correct
9 Runtime error 875 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 221292 KB Output is correct
2 Correct 515 ms 238676 KB Output is correct
3 Correct 555 ms 238676 KB Output is correct
4 Correct 440 ms 241288 KB Output is correct
5 Correct 525 ms 240976 KB Output is correct
6 Correct 526 ms 238792 KB Output is correct
7 Correct 308 ms 239556 KB Output is correct
8 Correct 402 ms 240156 KB Output is correct
9 Correct 751 ms 250088 KB Output is correct
10 Correct 733 ms 248656 KB Output is correct
11 Correct 728 ms 246736 KB Output is correct
12 Correct 606 ms 249200 KB Output is correct
13 Correct 639 ms 245080 KB Output is correct
14 Correct 743 ms 251216 KB Output is correct
15 Correct 753 ms 249688 KB Output is correct
16 Correct 761 ms 249044 KB Output is correct
17 Correct 484 ms 247876 KB Output is correct
18 Correct 607 ms 248656 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 221292 KB Output is correct
2 Correct 515 ms 238676 KB Output is correct
3 Correct 555 ms 238676 KB Output is correct
4 Correct 440 ms 241288 KB Output is correct
5 Correct 525 ms 240976 KB Output is correct
6 Correct 526 ms 238792 KB Output is correct
7 Correct 308 ms 239556 KB Output is correct
8 Correct 402 ms 240156 KB Output is correct
9 Runtime error 875 ms 262148 KB Execution killed with signal 9
10 Halted 0 ms 0 KB -