oj.uz

답안 #361257

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
361257 2021-01-29T01:05:04 Z RyoPham 도로 건설 사업 (JOI13_construction) C++14
40 / 100
 715 ms 222444 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 = 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.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 111724 KB Output is correct
2 Correct 452 ms 132140 KB Output is correct
3 Correct 457 ms 132136 KB Output is correct
4 Correct 362 ms 132548 KB Output is correct
5 Correct 463 ms 134480 KB Output is correct
6 Correct 440 ms 132180 KB Output is correct
7 Correct 262 ms 132196 KB Output is correct
8 Correct 313 ms 133604 KB Output is correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 111724 KB Output is correct
2 Correct 452 ms 132140 KB Output is correct
3 Correct 457 ms 132136 KB Output is correct
4 Correct 362 ms 132548 KB Output is correct
5 Correct 463 ms 134480 KB Output is correct
6 Correct 440 ms 132180 KB Output is correct
7 Correct 262 ms 132196 KB Output is correct
8 Correct 313 ms 133604 KB Output is correct
9 Runtime error 466 ms 222444 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 111724 KB Output is correct
2 Correct 452 ms 132140 KB Output is correct
3 Correct 457 ms 132136 KB Output is correct
4 Correct 362 ms 132548 KB Output is correct
5 Correct 463 ms 134480 KB Output is correct
6 Correct 440 ms 132180 KB Output is correct
7 Correct 262 ms 132196 KB Output is correct
8 Correct 313 ms 133604 KB Output is correct
9 Correct 708 ms 151956 KB Output is correct
10 Correct 706 ms 150280 KB Output is correct
11 Correct 637 ms 147976 KB Output is correct
12 Correct 551 ms 146116 KB Output is correct
13 Correct 572 ms 146760 KB Output is correct
14 Correct 676 ms 153092 KB Output is correct
15 Correct 715 ms 151336 KB Output is correct
16 Correct 671 ms 150252 KB Output is correct
17 Correct 430 ms 147792 KB Output is correct
18 Correct 571 ms 148404 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 111724 KB Output is correct
2 Correct 452 ms 132140 KB Output is correct
3 Correct 457 ms 132136 KB Output is correct
4 Correct 362 ms 132548 KB Output is correct
5 Correct 463 ms 134480 KB Output is correct
6 Correct 440 ms 132180 KB Output is correct
7 Correct 262 ms 132196 KB Output is correct
8 Correct 313 ms 133604 KB Output is correct
9 Runtime error 466 ms 222444 KB Execution killed with signal 11
10 Halted 0 ms 0 KB -