oj.uz

Submission #787334

# Submission time Handle Problem Language Result Execution time Memory
787334 2023-07-19T05:44:36 Z 이동현(#10034) 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 685 ms 101380 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define int long long
using namespace std;

struct Data{
    int x, y, ey, id;

    Data(){}
    Data(int x, int y, int ey, int id):x(x), y(y), ey(ey), id(id){}

    bool operator<(const Data&r)const{
        return x < r.x;
    }
};

struct Dsu{
    int n;
    vector<int> pr;
    Dsu(int m){
        n = m + 4;
        pr.resize(n);
        iota(pr.begin(), pr.end(), 0);
    }
    int fd(int x){
        return (x == pr[x] ? x : pr[x] = fd(pr[x]));
    }
    bool unite(int x, int y){
        x = fd(x), y = fd(y);
        if(x == y) return false;
        pr[y] = x;
        return true;
    }
};

struct Fenwick{
    int n;
    vector<int> tr;
    Fenwick(int m){
        n = m + 4;
        tr.resize(n);
    }

    void push(int pos, int val){
        ++pos;
        for(int i = pos; i < n; i += (i & -i)){
            tr[i] += val;
        }
    }

    int get(int pos){
        ++pos;
        int rv = 0;
        for(int i = pos; i > 0; i -= (i & -i)){
            rv += tr[i];
        }

        return rv;
    }
};

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, m, c;
    cin >> n >> m >> c;

    vector<vector<int>> a(n, vector<int>(2)), b(m, vector<int>(4));
    for(int i = 0; i < n; ++i){
        cin >> a[i][0] >> a[i][1];
    }
    for(int i = 0; i < m; ++i){
        cin >> b[i][0] >> b[i][1] >> b[i][2] >> b[i][3];
    }

    vector<vector<int>> way;
    auto makeway = [&](){
        vector<int> srt;
        for(int i = 0; i < n; ++i){
            srt.push_back(a[i][1]);
        }
        for(int i = 0; i < m; ++i){
            srt.push_back(b[i][1]);
            srt.push_back(b[i][3]);
        }
        sort(srt.begin(), srt.end());
        srt.erase(unique(srt.begin(), srt.end()), srt.end());
        for(int i = 0; i < n; ++i){
            a[i][1] = lower_bound(srt.begin(), srt.end(), a[i][1]) - srt.begin();
        }
        for(int i = 0; i < m; ++i){
            b[i][1] = lower_bound(srt.begin(), srt.end(), b[i][1]) - srt.begin();
            b[i][3] = lower_bound(srt.begin(), srt.end(), b[i][3]) - srt.begin();
        }

        vector<Data> que;
        for(int i = 0; i < n; ++i){
            que.push_back(Data(a[i][0], a[i][1], -1, i));
        }
        for(int i = 0; i < m; ++i){
            que.push_back(Data(b[i][0], b[i][1], b[i][3], 1));
        }

        sort(que.begin(), que.end());
        Fenwick tr((int)srt.size());
        vector<int> lst((int)srt.size(), -1), val((int)srt.size());
        for(int i = 0; i < (int)que.size(); ++i){
            if(que[i].ey == -1){
                if(lst[que[i].y] != -1 && tr.get(que[i].y) == val[que[i].y]){
                    way.push_back({que[i].x - que[lst[que[i].y]].x, que[i].id, que[lst[que[i].y]].id});
                }
                lst[que[i].y] = i;
                val[que[i].y] = tr.get(que[i].y);
            }
            else{
                // cout << "LINE " << que[i].x << ' ' << que[i].y << ' ' << que[i].ey + 1 << endl;
                tr.push(que[i].y, que[i].id);
                tr.push(que[i].ey + 1, -que[i].id);
            }
        }

        for(int i = 0; i < n; ++i){
            a[i][1] = srt[a[i][1]];
        }
        for(int i = 0; i < m; ++i){
            b[i][1] = srt[b[i][1]];
            b[i][3] = srt[b[i][3]];
        }
    };

    makeway();
    for(int i = 0; i < n; ++i){
        swap(a[i][0], a[i][1]);
    }
    for(int i = 0; i < m; ++i){
        swap(b[i][0], b[i][1]);
        swap(b[i][2], b[i][3]);
    }
    makeway();

    sort(way.begin(), way.end());

    // for(auto&i:way){
    //     cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
    // }
    
    Dsu gr(n);
    vector<int> cost, pre;
    for(int i = 0; i < (int)way.size(); ++i){
        if(gr.unite(way[i][1], way[i][2])){
            pre.push_back(((int)pre.size() ? pre.back() : 0) + way[i][0]);
            cost.push_back(way[i][0]);
        }
    }

    while(c--){
        int x, y;
        cin >> x >> y;

        y = n - y;

        if(y > (int)cost.size()){
            cout << "-1\n";
            
            continue;
        }

        int pos = lower_bound(cost.begin(), cost.end(), x) - cost.begin();
        pos = max(pos, y);
        cout << (pos ? pre[pos - 1] : 0ll) + (n - pos) * x << '\n';
    }

    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1944 KB Output is correct
2 Correct 206 ms 31256 KB Output is correct
3 Correct 206 ms 31060 KB Output is correct
4 Correct 275 ms 46040 KB Output is correct
5 Correct 229 ms 39300 KB Output is correct
6 Correct 198 ms 31348 KB Output is correct
7 Correct 193 ms 46384 KB Output is correct
8 Correct 181 ms 38792 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1944 KB Output is correct
2 Correct 206 ms 31256 KB Output is correct
3 Correct 206 ms 31060 KB Output is correct
4 Correct 275 ms 46040 KB Output is correct
5 Correct 229 ms 39300 KB Output is correct
6 Correct 198 ms 31348 KB Output is correct
7 Correct 193 ms 46384 KB Output is correct
8 Correct 181 ms 38792 KB Output is correct
9 Correct 515 ms 62696 KB Output is correct
10 Correct 522 ms 62704 KB Output is correct
11 Correct 518 ms 62796 KB Output is correct
12 Correct 515 ms 62712 KB Output is correct
13 Correct 374 ms 60108 KB Output is correct
14 Correct 232 ms 39544 KB Output is correct
15 Correct 524 ms 62700 KB Output is correct
16 Correct 314 ms 81404 KB Output is correct
17 Correct 323 ms 81348 KB Output is correct
18 Correct 426 ms 69496 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1944 KB Output is correct
2 Correct 206 ms 31256 KB Output is correct
3 Correct 206 ms 31060 KB Output is correct
4 Correct 275 ms 46040 KB Output is correct
5 Correct 229 ms 39300 KB Output is correct
6 Correct 198 ms 31348 KB Output is correct
7 Correct 193 ms 46384 KB Output is correct
8 Correct 181 ms 38792 KB Output is correct
9 Correct 369 ms 46992 KB Output is correct
10 Correct 369 ms 52196 KB Output is correct
11 Correct 341 ms 46720 KB Output is correct
12 Correct 419 ms 54360 KB Output is correct
13 Correct 298 ms 45508 KB Output is correct
14 Correct 396 ms 57528 KB Output is correct
15 Correct 396 ms 50028 KB Output is correct
16 Correct 364 ms 48952 KB Output is correct
17 Correct 306 ms 58628 KB Output is correct
18 Correct 350 ms 45236 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1944 KB Output is correct
2 Correct 206 ms 31256 KB Output is correct
3 Correct 206 ms 31060 KB Output is correct
4 Correct 275 ms 46040 KB Output is correct
5 Correct 229 ms 39300 KB Output is correct
6 Correct 198 ms 31348 KB Output is correct
7 Correct 193 ms 46384 KB Output is correct
8 Correct 181 ms 38792 KB Output is correct
9 Correct 515 ms 62696 KB Output is correct
10 Correct 522 ms 62704 KB Output is correct
11 Correct 518 ms 62796 KB Output is correct
12 Correct 515 ms 62712 KB Output is correct
13 Correct 374 ms 60108 KB Output is correct
14 Correct 232 ms 39544 KB Output is correct
15 Correct 524 ms 62700 KB Output is correct
16 Correct 314 ms 81404 KB Output is correct
17 Correct 323 ms 81348 KB Output is correct
18 Correct 426 ms 69496 KB Output is correct
19 Correct 369 ms 46992 KB Output is correct
20 Correct 369 ms 52196 KB Output is correct
21 Correct 341 ms 46720 KB Output is correct
22 Correct 419 ms 54360 KB Output is correct
23 Correct 298 ms 45508 KB Output is correct
24 Correct 396 ms 57528 KB Output is correct
25 Correct 396 ms 50028 KB Output is correct
26 Correct 364 ms 48952 KB Output is correct
27 Correct 306 ms 58628 KB Output is correct
28 Correct 350 ms 45236 KB Output is correct
29 Correct 647 ms 90260 KB Output is correct
30 Correct 442 ms 66132 KB Output is correct
31 Correct 606 ms 83460 KB Output is correct
32 Correct 288 ms 41988 KB Output is correct
33 Correct 652 ms 83816 KB Output is correct
34 Correct 282 ms 33864 KB Output is correct
35 Correct 635 ms 76680 KB Output is correct
36 Correct 685 ms 88216 KB Output is correct
37 Correct 442 ms 101380 KB Output is correct
38 Correct 503 ms 81240 KB Output is correct
39 Correct 361 ms 45868 KB Output is correct