oj.uz

Submission #787878

# Submission time Handle Problem Language Result Execution time Memory
787878 2023-07-19T13:49:55 Z puppy 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 1090 ms 182688 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#define int long long
using namespace std;
vector<int> cpx, cpy;
int N, M, C, x[200005], y[200005], P[200005], Q[200005], R[200005], S[200005];
vector<int> xlist[600005], ylist[600005];
struct UnionFind
{
    vector<int> par;
    UnionFind(int n){par.resize(n+1); for(int i=1;i<=n;i++) par[i] = i;}
    int fin(int i){return i==par[i]?i:(par[i] = fin(par[i]));}
    void uni(int u, int v){par[fin(u)] = fin(v);}
    bool isuni(int u, int v){return fin(u) == fin(v);}
};
vector<pair<int, pair<int, int>>> edge;
vector<pair<int, pair<int, int>>> redge;
vector<pair<int, pair<int, int>>> cand;
int maxc;
int tree[600005];
void init()
{
    fill(tree, tree + 600005, 0);
}
void upd(int id, int x)
{
    for (int i = id; i <= maxc; i += i&-i) tree[i] += x;
}
int query(int id)
{
    int ret = 0;
    for (int i = id; i; i -= i&-i) ret += tree[i];
    return ret;
}
int sum(int l, int r)
{
    return query(r) - query(l-1);
}
signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> N >> M >> C;
    for (int i = 1; i <= N; i++) {
        cin >> x[i] >> y[i];
        cpx.push_back(x[i]);
        cpy.push_back(y[i]);
    }
    for (int i = 1; i <= M; i++) {
        cin >> P[i] >> Q[i] >> R[i] >> S[i];
        cpx.push_back(P[i]); cpx.push_back(R[i]);
        cpy.push_back(Q[i]); cpy.push_back(S[i]);
    }
    sort(cpx.begin(), cpx.end());
    sort(cpy.begin(), cpy.end());
    for (int i = 1; i <= N; i++) {
        x[i] = lower_bound(cpx.begin(), cpx.end(), x[i]) - cpx.begin() + 1;
        y[i] = lower_bound(cpy.begin(), cpy.end(), y[i]) - cpy.begin() + 1;
    }
    for (int i = 1; i <= M; i++) {
        P[i] = lower_bound(cpx.begin(), cpx.end(), P[i]) - cpx.begin() + 1;
        R[i] = lower_bound(cpx.begin(), cpx.end(), R[i]) - cpx.begin() + 1;
        Q[i] = lower_bound(cpy.begin(), cpy.end(), Q[i]) - cpy.begin() + 1;
        S[i] = lower_bound(cpy.begin(), cpy.end(), S[i]) - cpy.begin() + 1;
    }
    for (int i = 1; i <= N; i++) {
        xlist[x[i]].push_back(i);
        ylist[y[i]].push_back(i);
    }
    maxc = N + 2 * M;
    for (int i = 1; i <= maxc; i++) {
        sort(xlist[i].begin(), xlist[i].end(), [&](int p, int q){return y[p] < y[q];});
        for (int j = 0; j < (int)xlist[i].size() - 1; j++) {
            edge.push_back(make_pair(cpy[y[xlist[i][j+1]]-1] - cpy[y[xlist[i][j]]-1], make_pair(xlist[i][j], xlist[i][j+1])));
        }
    }
    for (int i = 1; i <= maxc; i++) {
        sort(ylist[i].begin(), ylist[i].end(), [&](int p, int q){return x[p] < x[q];});
        for (int j = 0; j < (int)ylist[i].size() - 1; j++) {
            edge.push_back(make_pair(cpx[x[ylist[i][j+1]]-1] - cpx[x[ylist[i][j]]-1], make_pair(ylist[i][j], ylist[i][j+1])));
        }
    }
    sort(edge.begin(), edge.end());
    vector<vector<int>> linex(maxc+2), liney(maxc+2);
    vector<vector<int>> rectx(maxc+2), recty(maxc+2);
    for (int i = 0; i < (int)edge.size(); i++) {
        if (x[edge[i].second.first] == x[edge[i].second.second]) {
            linex[x[edge[i].second.first]].push_back(i);
        }
        else {
            liney[y[edge[i].second.first]].push_back(i);
        }
    }
    for (int i = 1; i <= M; i++) {
        rectx[P[i]].push_back(Q[i]);
        rectx[P[i]].push_back(S[i]);
        rectx[R[i]+1].push_back(-Q[i]);
        rectx[R[i]+1].push_back(-S[i]);
        recty[Q[i]].push_back(P[i]);
        recty[Q[i]].push_back(R[i]);
        recty[S[i]+1].push_back(-P[i]);
        recty[S[i]+1].push_back(-R[i]);
    }
    init();
    for (int i = 1; i <= maxc; i++) {
        for (int j:rectx[i]) {
            if (j > 0) upd(j, 1);
            else upd(-j, -1);
        }
        for (int j:linex[i]) {
            if (sum(y[edge[j].second.first], y[edge[j].second.second]) == 0) redge.push_back(edge[j]);
        }
    }
    init();
    for (int i = 1; i <= maxc; i++) {
        for (int j:recty[i]) {
            if (j > 0) upd(j, 1);
            else upd(-j, -1);
        }
        for (int j:liney[i]) {
            if (sum(x[edge[j].second.first], x[edge[j].second.second]) == 0) redge.push_back(edge[j]);
        }
    }
    sort(redge.begin(), redge.end());
    UnionFind uf(N);
    for (auto i:redge) {
        if (uf.isuni(i.second.first, i.second.second)) continue;
        cand.push_back(i);
        uf.uni(i.second.first, i.second.second);
    }
    vector<int> weight;
    for (auto i:cand) weight.push_back(i.first);
    vector<long long> costs(weight.size()+1);
    for (int i = 1; i <= weight.size(); i++) costs[i] = costs[i-1] + weight[i-1];
    for (int i = 1; i <= C; i++) {
        long long b, k; cin >> b >> k;
        if (weight.size() < N - k) {
            cout << -1 << '\n';
        }
        else {
            int id = lower_bound(weight.begin(), weight.end(), b) - weight.begin();
            id = max(id, N - k);
            cout << costs[id] + (N - id) * b << '\n';
        }
    }
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:134:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |     for (int i = 1; i <= weight.size(); i++) costs[i] = costs[i-1] + weight[i-1];
      |                     ~~^~~~~~~~~~~~~~~~
construction.cpp:137:27: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  137 |         if (weight.size() < N - k) {
      |             ~~~~~~~~~~~~~~^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36352 KB Output is correct
2 Correct 278 ms 86548 KB Output is correct
3 Correct 283 ms 87080 KB Output is correct
4 Correct 322 ms 100344 KB Output is correct
5 Correct 316 ms 92400 KB Output is correct
6 Correct 275 ms 87144 KB Output is correct
7 Correct 182 ms 99336 KB Output is correct
8 Correct 193 ms 92388 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36352 KB Output is correct
2 Correct 278 ms 86548 KB Output is correct
3 Correct 283 ms 87080 KB Output is correct
4 Correct 322 ms 100344 KB Output is correct
5 Correct 316 ms 92400 KB Output is correct
6 Correct 275 ms 87144 KB Output is correct
7 Correct 182 ms 99336 KB Output is correct
8 Correct 193 ms 92388 KB Output is correct
9 Correct 919 ms 150940 KB Output is correct
10 Correct 915 ms 150888 KB Output is correct
11 Correct 934 ms 150824 KB Output is correct
12 Correct 929 ms 150732 KB Output is correct
13 Correct 646 ms 154448 KB Output is correct
14 Correct 314 ms 92196 KB Output is correct
15 Correct 923 ms 150552 KB Output is correct
16 Correct 347 ms 165192 KB Output is correct
17 Correct 345 ms 164280 KB Output is correct
18 Correct 546 ms 151868 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36352 KB Output is correct
2 Correct 278 ms 86548 KB Output is correct
3 Correct 283 ms 87080 KB Output is correct
4 Correct 322 ms 100344 KB Output is correct
5 Correct 316 ms 92400 KB Output is correct
6 Correct 275 ms 87144 KB Output is correct
7 Correct 182 ms 99336 KB Output is correct
8 Correct 193 ms 92388 KB Output is correct
9 Correct 449 ms 100864 KB Output is correct
10 Correct 428 ms 102396 KB Output is correct
11 Correct 422 ms 99868 KB Output is correct
12 Correct 446 ms 110128 KB Output is correct
13 Correct 373 ms 92596 KB Output is correct
14 Correct 476 ms 104340 KB Output is correct
15 Correct 455 ms 103532 KB Output is correct
16 Correct 436 ms 102192 KB Output is correct
17 Correct 309 ms 111496 KB Output is correct
18 Correct 362 ms 104436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 36352 KB Output is correct
2 Correct 278 ms 86548 KB Output is correct
3 Correct 283 ms 87080 KB Output is correct
4 Correct 322 ms 100344 KB Output is correct
5 Correct 316 ms 92400 KB Output is correct
6 Correct 275 ms 87144 KB Output is correct
7 Correct 182 ms 99336 KB Output is correct
8 Correct 193 ms 92388 KB Output is correct
9 Correct 919 ms 150940 KB Output is correct
10 Correct 915 ms 150888 KB Output is correct
11 Correct 934 ms 150824 KB Output is correct
12 Correct 929 ms 150732 KB Output is correct
13 Correct 646 ms 154448 KB Output is correct
14 Correct 314 ms 92196 KB Output is correct
15 Correct 923 ms 150552 KB Output is correct
16 Correct 347 ms 165192 KB Output is correct
17 Correct 345 ms 164280 KB Output is correct
18 Correct 546 ms 151868 KB Output is correct
19 Correct 449 ms 100864 KB Output is correct
20 Correct 428 ms 102396 KB Output is correct
21 Correct 422 ms 99868 KB Output is correct
22 Correct 446 ms 110128 KB Output is correct
23 Correct 373 ms 92596 KB Output is correct
24 Correct 476 ms 104340 KB Output is correct
25 Correct 455 ms 103532 KB Output is correct
26 Correct 436 ms 102192 KB Output is correct
27 Correct 309 ms 111496 KB Output is correct
28 Correct 362 ms 104436 KB Output is correct
29 Correct 1090 ms 175872 KB Output is correct
30 Correct 698 ms 128180 KB Output is correct
31 Correct 1068 ms 169336 KB Output is correct
32 Correct 399 ms 91292 KB Output is correct
33 Correct 1071 ms 169684 KB Output is correct
34 Correct 431 ms 93460 KB Output is correct
35 Correct 932 ms 166456 KB Output is correct
36 Correct 1072 ms 174044 KB Output is correct
37 Correct 467 ms 182688 KB Output is correct
38 Correct 662 ms 171440 KB Output is correct
39 Correct 369 ms 108164 KB Output is correct