Submission #56985

#	Time	Username	Problem	Language	Result	Execution time	Memory
56985		choikiwon	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	3562 ms	226980 KiB

construction

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double lf;
typedef pair<int, int> pii;

const int MN = 600010;

int N, M, C;
pii P[MN];
struct Rect {
    int x1, y1, x2, y2;
};
Rect rect[MN];

struct Query {
    int b, h, id;
    bool operator <(const Query &i) const {
        return h < i.h;
    }
};
Query Q[MN];

int Xn, Yn;
vector<int> X, Y;
unordered_map<int, int> dx, dy;

struct BIT {
    vector<int> tree, lazy;
    void init() {
        tree = vector<int>(4 * MN, 0);
        lazy = vector<int>(4 * MN, 0);
    }
    void prop(int l, int r, int n) {
        if(l != r) {
            tree[2*n] += lazy[n];
            lazy[2*n] += lazy[n];
            tree[2*n + 1] += lazy[n];
            lazy[2*n + 1] += lazy[n];
            lazy[n] = 0;
        }
    }
    void upd(int a, int b, int d, int l, int r, int n) {
        if(b < l || r < a) return;
        if(a <= l && r <= b) {
            tree[n] += d;
            lazy[n] += d;
            return;
        }
        prop(l, r, n);
        int m = (l + r)>>1;
        upd(a, b, d, l, m, 2*n);
        upd(a, b, d, m + 1, r, 2*n + 1);
        tree[n] = max(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) return tree[n];
        prop(l, r, n);
        int m = (l + r)>>1;
        int L = quer(a, b, l, m, 2*n);
        int R = quer(a, b, m + 1, r, 2*n + 1);
        return max(L, R);
    }
} bit;

struct Edge {
    int u, v, w;
    bool operator <(const Edge &i) const {
        return w < i.w;
    }
};
vector<Edge> edge;

vector<pii> query[MN], add[MN], rem[MN];

void proc(vector<int> &Z) {
    for(int i = 0; i < MN; i++) {
        query[i].clear();
        add[i].clear();
        rem[i].clear();
    }
    for(int i = 0; i < N; i++) {
        query[ P[i].second ].push_back({ P[i].first, i });
    }
    for(int i = 0; i < M; i++) {
        add[ rect[i].y1 ].push_back({ rect[i].x1, rect[i].x2 });
        rem[ rect[i].y2 ].push_back({ rect[i].x1, rect[i].x2 });
    }
    bit.init();
    for(int i = 0; i < MN; i++) {
        for(int j = 0; j < add[i].size(); j++) {
            bit.upd(add[i][j].first, add[i][j].second, 1, 0, MN - 1, 1);
        }

        sort(query[i].begin(), query[i].end());

        for(int j = 1; j < query[i].size(); j++) {
            int x1 = query[i][j - 1].first;
            int x2 = query[i][j].first;

            if(!bit.quer(x1, x2, 0, MN - 1, 1)) {
                int id1 = query[i][j - 1].second;
                int id2 = query[i][j].second;

                edge.push_back({ id1, id2, Z[x2] - Z[x1] });
            }
        }

        for(int j = 0; j < rem[i].size(); j++) {
            bit.upd(rem[i][j].first, rem[i][j].second, -1, 0, MN - 1, 1);
        }
    }
}

struct CHT {
    vector<ll> M, B;
    void init() {
        M.clear();
        B.clear();
    }
    bool bad(int l1, int l2, int l3) {
        return (lf) (B[l3] - B[l1]) / (M[l1] - M[l3]) <= (lf) (B[l2] - B[l1]) / (M[l1] - M[l2]);
    }
    void add(ll m, ll b) {
        M.push_back(m);
        B.push_back(b);
        while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
            M.erase(M.end() - 2);
            B.erase(B.end() - 2);
        }
        if(M.size() == 2 && M[0] == M[1]) {
            M.erase(M.end() - 2);
            B.erase(B.end() - 2);
        }
    }
    ll query(ll x) {
        if(M.size() == 0) return 1e18;
        int s = 0, e = (int)M.size() - 2, p = 0;
        while(s <= e) {
            int m = (s + e)>>1;

            if(x >= (lf) (B[m + 1] - B[m]) / (M[m] - M[m + 1])) {
                p = m + 1;
                s = m + 1;
            }
            else e = m - 1;
        }
        return M[p] * x + B[p];
    }
} cht;

int fa[MN];
void init() {
    for(int i = 0; i < N; i++) fa[i] = i;
}
int find(int u) {
    if(fa[u] == u) return u;
    else return fa[u] = find(fa[u]);
}
void mrg(int u, int v) {
    u = find(u);
    v = find(v);
    fa[v] = u;
}
vector<pair<int, ll> > line;
ll ans[MN];

int main() {
    scanf("%d %d %d", &N, &M, &C);

    for(int i = 0; i < N; i++) {
        scanf("%d %d", &P[i].first, &P[i].second);
        X.push_back(P[i].first);
        Y.push_back(P[i].second);
    }
    for(int i = 0; i < M; i++) {
        int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
        rect[i] = {x1, y1, x2, y2};
        X.push_back(x1);
        X.push_back(x2);
        Y.push_back(y1);
        Y.push_back(y2);
    }
    for(int i = 0; i < C; i++) {
        scanf("%d %d", &Q[i].b, &Q[i].h);
        Q[i].id = i;
    }
    sort(Q, Q + C);

    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    X.resize(unique(X.begin(), X.end()) - X.begin());
    Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
    Xn = X.size();
    Yn = Y.size();
    for(int i = 0; i < Xn; i++) dx[X[i]] = i;
    for(int i = 0; i < Yn; i++) dy[Y[i]] = i;
    for(int i = 0; i < N; i++) {
        P[i].first = dx[ P[i].first ];
        P[i].second = dy[ P[i].second ];
    }
    for(int i = 0; i < M; i++) {
        rect[i].x1 = dx[ rect[i].x1 ];
        rect[i].x2 = dx[ rect[i].x2 ];
        rect[i].y1 = dy[ rect[i].y1 ];
        rect[i].y2 = dy[ rect[i].y2 ];
    }

    proc(X);

    for(int i = 0; i < N; i++) swap(P[i].first, P[i].second);
    for(int i = 0; i < M; i++) {
        swap(rect[i].x1, rect[i].y1);
        swap(rect[i].x2, rect[i].y2);
    }

    proc(Y);

    sort(edge.begin(), edge.end());
    init();

    int cnt = N;
    ll cost = 0;
    line.push_back({cnt, cost});
    for(int i = 0; i < edge.size(); i++) {
        int u = edge[i].u;
        int v = edge[i].v;
        int w = edge[i].w;

        if(find(u) == find(v)) continue;

        mrg(u, v);
        cnt--;
        cost += w;
        line.push_back({cnt, cost});
    }

    /*
    for(int i = 0; i < line.size(); i++) {
        cout << line[i].first << ' ' << line[i].second << endl;
    }
    //*/

    cht.init();
    int pos = (int)line.size() - 1;
    for(int i = 0; i < C; i++) {
        while(pos >= 0 && line[pos].first <= Q[i].h) {
            cht.add(-line[pos].first, line[pos].second);
            pos--;
        }
        ans[ Q[i].id ] = cht.query(-Q[i].b);
    }

    for(int i = 0; i < C; i++) {
        if(ans[i] == 1e18) printf("-1\n");
        else printf("%lld\n", ans[i]);
    }
}

Compilation message (stderr)

construction.cpp: In function 'void proc(std::vector<int>&)':
construction.cpp:93:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < add[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~
construction.cpp:99:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 1; j < query[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~~~
construction.cpp:111:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < rem[i].size(); j++) {
                        ~~^~~~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:227:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < edge.size(); i++) {
                    ~~^~~~~~~~~~~~~
construction.cpp:171:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d", &N, &M, &C);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:174:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &P[i].first, &P[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:179:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int x1, y1, x2, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:187:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &Q[i].b, &Q[i].h);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30