oj.uz

Submission #377776

# Submission time Handle Problem Language Result Execution time Memory
377776 2021-03-15T03:31:17 Z two_sides 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 1520 ms 61612 KB 
#include <bits/stdc++.h>

using namespace std;

using ii = pair <int, int>;

struct segTree {
    vector <int> val; int n, lo, hi;
    
    void reset() {
        val.assign(n * 4, 0);
    }
    
    segTree(int n): n(n) {
        val.assign(n * 4, 0);
    }
    
    void pushDown(int i) {
        if (val[i] >= 0) {
            val[i * 2] = val[i * 2 + 1] = val[i];
            val[i] = -1;
        }
    }
    
    void setVal(int i, int l, int r, int v) {
        assert(l <= r);
        if (l >= lo && r <= hi)
            return void(val[i] = v);
        pushDown(i); int m = (l + r) / 2;
        if (m >= lo) setVal(i * 2, l, m, v);
        if (m < hi) setVal(i * 2 + 1, m + 1, r, v);
    }
    
    int getVal(int i, int l, int r, int p) {
        assert(l <= r);
        if (val[i] >= 0) return val[i];
        pushDown(i); int m = (l + r) / 2;
        if (m >= p) return getVal(i * 2, l, m, p);
        return getVal(i * 2 + 1, m + 1, r, p);
    }
    
    void setVal(int l, int r, int v) {
        lo = l; hi = r; setVal(1, 1, n, v);
    }
    
    int getVal(int p) {
        return getVal(1, 1, n, p);
    }
};

using ll = long long;

struct point {
    int x, y, id;
};

struct rect {
    int l, b, r, t;
};

struct edge {
    int u, v, w;
};

const int N = 200005;

point A[N]; rect B[N];
map <ii, int> idx;
vector <edge> Edge;
vector <int> MST;
vector <ll> Sum;
int Par[N];

int Find(int u) {
    return Par[u] < 0 ? u : Par[u] = Find(Par[u]);
}

bool Unite(int u, int v) {
    u = Find(u); v = Find(v);
    return u != v ? Par[v] = u, true : false;
}

void compress(vector <int> &cmp) {
    sort(cmp.begin(), cmp.end());
    cmp.erase(unique(cmp.begin(),
    cmp.end()), cmp.end());
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n, m, q; cin >> n >> m >> q;
    vector <int> cmpx, cmpy;
    segTree ST(n + 2 * m);
    for (int i = 0; i < n; i++) {
        cin >> A[i].x >> A[i].y;
        A[i].x++; A[i].y++;
        cmpx.push_back(A[i].x);
        cmpy.push_back(A[i].y);
        A[i].id = i;
        idx[ii(A[i].x, A[i].y)] = i;
    }
    for (int i = 0; i < m; i++) {
        cin >> B[i].l >> B[i].b;
        cin >> B[i].r >> B[i].t;
        B[i].l++; B[i].b++;
        B[i].r++; B[i].t++;
        cmpx.push_back(B[i].l);
        cmpx.push_back(B[i].r);
        cmpy.push_back(B[i].b);
        cmpy.push_back(B[i].t);
    }
    compress(cmpx); compress(cmpy);
    sort(A, A + n, [](point p, point q) {
        return p.x < q.x;
    });
    sort(B, B + m, [](rect p, rect q) {
        return p.r < q.r;
    });
    for (int i = 0, j = 0; i < n; i++) {
        while (j < m && B[j].r <= A[i].x) {
            int l = upper_bound(cmpy.begin(),
            cmpy.end(), B[j].b) - cmpy.begin();
            int r = upper_bound(cmpy.begin(),
            cmpy.end(), B[j].t) - cmpy.begin();
            ST.setVal(l, r, B[j].r); j++;
        }
        int p = upper_bound(cmpy.begin(),
        cmpy.end(), A[i].y) - cmpy.begin();
        int x = ST.getVal(p);
        if (idx.count(ii(x, A[i].y)))
            Edge.push_back({idx[ii(x, A[i].y)],
            A[i].id, A[i].x - x});
        ST.setVal(p, p, A[i].x);
    }
    ST.reset();
    sort(A, A + n, [](point p, point q) {
        return p.y < q.y;
    });
    sort(B, B + m, [](rect p, rect q) {
        return p.t < q.t;
    });
    for (int i = 0, j = 0; i < n; i++) {
        while (j < m && B[j].t <= A[i].y) {
            int l = upper_bound(cmpx.begin(),
            cmpx.end(), B[j].l) - cmpx.begin();
            int r = upper_bound(cmpx.begin(),
            cmpx.end(), B[j].r) - cmpx.begin();
            ST.setVal(l, r, B[j].t); j++;
        }
        int p = upper_bound(cmpx.begin(),
        cmpx.end(), A[i].x) - cmpx.begin();
        int y = ST.getVal(p);
        if (idx.count(ii(A[i].x, y)))
            Edge.push_back({idx[ii(A[i].x, y)],
            A[i].id, A[i].y - y});
        ST.setVal(p, p, A[i].y);
    }
    int cmp = n;
    sort(Edge.begin(), Edge.end(),
    [](edge p, edge q) {
        return p.w < q.w;
    });
    memset(Par, -1, sizeof Par);
    for (auto e : Edge)
        if (Unite(e.u, e.v)) {
            MST.push_back(e.w); cmp--;
        }
    int len = MST.size();
    reverse(MST.begin(), MST.end());
    Sum.resize(len + 1);
    for (int i = 0; i < MST.size(); i++)
        Sum[i + 1] = Sum[i] + MST[i];
    while (q--) {
        int cost, lim;
        cin >> cost >> lim;
        if (lim < cmp) {
            cout << "-1\n"; continue;
        }
        ll res = Sum.back() + ll(cost) * cmp;
        int lo = 0, p = -1;
        int hi = min(lim - cmp, len) - 1;
        while (lo <= hi) {
            int mi = (lo + hi) / 2;
            if (MST[mi] >= cost) {
                p = mi; lo = mi + 1;
            }
            else hi = mi - 1;
        }
        res -= Sum[p + 1] - ll(cost) * (p + 1);
        cout << res << '\n';
    }
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:171:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  171 |     for (int i = 0; i < MST.size(); i++)
      |                     ~~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2028 KB Output is correct
2 Correct 694 ms 27508 KB Output is correct
3 Correct 707 ms 27640 KB Output is correct
4 Correct 705 ms 30836 KB Output is correct
5 Correct 755 ms 30468 KB Output is correct
6 Correct 713 ms 27700 KB Output is correct
7 Correct 383 ms 31868 KB Output is correct
8 Correct 417 ms 30412 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2028 KB Output is correct
2 Correct 694 ms 27508 KB Output is correct
3 Correct 707 ms 27640 KB Output is correct
4 Correct 705 ms 30836 KB Output is correct
5 Correct 755 ms 30468 KB Output is correct
6 Correct 713 ms 27700 KB Output is correct
7 Correct 383 ms 31868 KB Output is correct
8 Correct 417 ms 30412 KB Output is correct
9 Correct 1286 ms 44984 KB Output is correct
10 Correct 1277 ms 44968 KB Output is correct
11 Correct 1298 ms 45040 KB Output is correct
12 Correct 1268 ms 45112 KB Output is correct
13 Correct 893 ms 39796 KB Output is correct
14 Correct 841 ms 30412 KB Output is correct
15 Correct 1288 ms 45128 KB Output is correct
16 Correct 665 ms 50196 KB Output is correct
17 Correct 596 ms 50284 KB Output is correct
18 Correct 609 ms 48440 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2028 KB Output is correct
2 Correct 694 ms 27508 KB Output is correct
3 Correct 707 ms 27640 KB Output is correct
4 Correct 705 ms 30836 KB Output is correct
5 Correct 755 ms 30468 KB Output is correct
6 Correct 713 ms 27700 KB Output is correct
7 Correct 383 ms 31868 KB Output is correct
8 Correct 417 ms 30412 KB Output is correct
9 Correct 934 ms 43512 KB Output is correct
10 Correct 896 ms 42588 KB Output is correct
11 Correct 914 ms 39376 KB Output is correct
12 Correct 877 ms 40040 KB Output is correct
13 Correct 849 ms 36820 KB Output is correct
14 Correct 985 ms 44592 KB Output is correct
15 Correct 996 ms 42812 KB Output is correct
16 Correct 931 ms 41552 KB Output is correct
17 Correct 572 ms 43872 KB Output is correct
18 Correct 662 ms 41292 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2028 KB Output is correct
2 Correct 694 ms 27508 KB Output is correct
3 Correct 707 ms 27640 KB Output is correct
4 Correct 705 ms 30836 KB Output is correct
5 Correct 755 ms 30468 KB Output is correct
6 Correct 713 ms 27700 KB Output is correct
7 Correct 383 ms 31868 KB Output is correct
8 Correct 417 ms 30412 KB Output is correct
9 Correct 1286 ms 44984 KB Output is correct
10 Correct 1277 ms 44968 KB Output is correct
11 Correct 1298 ms 45040 KB Output is correct
12 Correct 1268 ms 45112 KB Output is correct
13 Correct 893 ms 39796 KB Output is correct
14 Correct 841 ms 30412 KB Output is correct
15 Correct 1288 ms 45128 KB Output is correct
16 Correct 665 ms 50196 KB Output is correct
17 Correct 596 ms 50284 KB Output is correct
18 Correct 609 ms 48440 KB Output is correct
19 Correct 934 ms 43512 KB Output is correct
20 Correct 896 ms 42588 KB Output is correct
21 Correct 914 ms 39376 KB Output is correct
22 Correct 877 ms 40040 KB Output is correct
23 Correct 849 ms 36820 KB Output is correct
24 Correct 985 ms 44592 KB Output is correct
25 Correct 996 ms 42812 KB Output is correct
26 Correct 931 ms 41552 KB Output is correct
27 Correct 572 ms 43872 KB Output is correct
28 Correct 662 ms 41292 KB Output is correct
29 Correct 1520 ms 61084 KB Output is correct
30 Correct 1078 ms 43220 KB Output is correct
31 Correct 1499 ms 54448 KB Output is correct
32 Correct 817 ms 34436 KB Output is correct
33 Correct 1519 ms 54812 KB Output is correct
34 Correct 814 ms 35804 KB Output is correct
35 Correct 1504 ms 54340 KB Output is correct
36 Correct 1513 ms 59092 KB Output is correct
37 Correct 799 ms 61612 KB Output is correct
38 Correct 810 ms 57784 KB Output is correct
39 Correct 682 ms 42060 KB Output is correct