Submission #35203

#	Time	Username	Problem	Language	Result	Execution time	Memory
35203		ztrong	도로 건설 사업 (JOI13_construction)	C++14	100 / 100	989 ms	41492 KiB

construction

#include <bits/stdc++.h>
#define llint long long
#define fi first
#define se second
using namespace std;

inline void read(int &x) {
    register char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    x = 0;
    while ('0' <= c && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
}

int cs[20], ncs;
inline void writeln(llint x) {
    if (x == -1) {
        puts("-1");
        return;
    }

    ncs = 0;
    while (x) {
        cs[++ncs] = x % 10;
        x /= 10;
    }
    for (int i = ncs; i >= 1; --i) {
        putchar(cs[i] + '0');
    }
    putchar('\n');
}

void openFile() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
#ifdef Tr___
    freopen("test.inp", "r", stdin);
    freopen("test.out", "w", stdout);
#else
    //freopen("name.inp", "r", stdin);
    //freopen("name.out", "w", stdout);
#endif
}

const int maxn = 1e5 + 5;
const int maxm = 1e6 + 5;
const llint inf = 1e9 + 7;

int N, M, C;
struct point {
    int x, y;
    int id;
} p[maxn * 2];
struct rect {
    int x, y, u, v;
    rect() {}
    rect(int x, int y, int u, int v): x(x), y(y), u(u), v(v) {}
} rec[maxn * 2], realRec[maxn * 4];
struct query {
    int b, h;
} q[maxn * 5];

void enter() {
    read(N); read(M); read(C);
    for (int i = 1; i <= N; ++i) {
        read(p[i].x); read(p[i].y);
        //cin >> p[i].x >> p[i].y;
        p[i].id = i;
    }
    for (int i = 1; i <= M; ++i) {
        read(rec[i].x); read(rec[i].y); read(rec[i].u); read(rec[i].v);
        //cin >> rec[i].x >> rec[i].y >> rec[i].u >> rec[i].v;
    }
    for (int i = 1; i <= C; ++i) {
        read(q[i].b); read(q[i].h);
        //cin >> q[i].b >> q[i].h;
        //h <= 1e5
    }
}

int lastId;
multiset<int> coor;
bool checkCoor(int x, int u, int v) {
    while (lastId <= M * 2 && realRec[lastId].x <= x) {

        if (realRec[lastId].v == 1) {
            coor.insert(realRec[lastId].y);
            coor.insert(realRec[lastId].u);
        }
        else {
            coor.erase(coor.find(realRec[lastId].y));
            coor.erase(coor.find(realRec[lastId].u));
        }
        ++lastId;
    }
    multiset<int> :: iterator it = coor.lower_bound(u);
    if (it == coor.end()) return true;
    if (*it <= v) return false;
    return true;
}

struct edge {
    int u, v, w;
    edge() {}
    edge(int u, int v, int w): u(u), v(v), w(w) {}
};
vector<edge> E;
inline void addEdge(int u, int v, int w) {
    E.push_back(edge(u, v, w));
    //cout << u << " " << v << " " << w << endl;
}

bool sortByX(const point &a, const point &b) {
    if (a.x != b.x) return a.x < b.x;
    return a.y < b.y;
}

bool sortByY(const point &a, const point &b) {
    if (a.y != b.y) return a.y < b.y;
    return a.x < b.x;
}

void buildEdge() {
    //num edge

    sort(p + 1, p + N + 1, sortByX);
    for (int i = 1; i <= M; ++i) {
        realRec[i] = rect(rec[i].x, rec[i].y, rec[i].v, 1);
        realRec[i + M] = rect(rec[i].u + 1, rec[i].y, rec[i].v, -1);
    }

    sort(realRec + 1, realRec + M * 2 + 1, [] (const rect &a, const rect &b) {
            if (a.x != b.x) return a.x < b.x;
            if (a.v != b.v) return a.v > b.v;
            if (a.y != b.y) return a.y < b.y;
            return a.u < b.u;
            });

    coor.clear();
    lastId = 1;
    for (int i = 2; i <= N; ++i) {
        if (p[i].x != p[i - 1].x) continue;
        if (checkCoor(p[i].x, p[i - 1].y, p[i].y)) {
            addEdge(p[i - 1].id, p[i].id, p[i].y - p[i - 1].y);
        }
    }

    sort(p + 1, p + N + 1, sortByY);
    for (int i = 1; i <= M; ++i) {
        realRec[i] = rect(rec[i].y, rec[i].x, rec[i].u, 1);
        realRec[i + M] = rect(rec[i].v + 1, rec[i].x, rec[i].u, -1);
    }
    
    sort(realRec + 1, realRec + M * 2 + 1, [] (const rect &a, const rect &b) {
            if (a.x != b.x) return a.x < b.x;
            if (a.v != b.v) return a.v > b.v;
            if (a.y != b.y) return a.y < b.y;
            return a.u < b.u;
            });

    coor.clear();
    lastId = 1;
    for (int i = 2; i <= N; ++i) {
        if (p[i].y != p[i - 1].y) continue;
        //cout << p[i - 1].id << " " << p[i].id << endl;
        if (checkCoor(p[i].y, p[i - 1].x, p[i].x)) {
            addEdge(p[i - 1].id, p[i].id, p[i].x - p[i - 1].x);
        }
    }
}

int lab[maxn * 2];
int find(int u) {
    return lab[u] <= 0 ? u : u = find(lab[u]);
}

inline void Union(int s, int t) {
    if (lab[s] < lab[t]) lab[t] = s;
    else {
        if (lab[s] == lab[t]) --lab[t];
        lab[s] = t;
    }
}

vector<int> allEdge;
void buildMST() {
    sort(E.begin(), E.end(), [] (const edge &a, const edge &b) {
            return a.w < b.w;
            });

    for (auto e : E) {
        int s = e.u, t = e.v, w = e.w;
        s = find(s), t = find(t);
        if (s != t) {
            Union(s, t);
            allEdge.push_back(w);
            //cout << e.u << " " << e.v << " " << e.w << endl;
        }
    }
}

void calcQuery() {
    //allEdge already sorted
    vector<llint> tot;
    tot.clear();
    for (int i = 0; i < allEdge.size(); ++i) {
        if (i == 0) tot.push_back(allEdge[i]);
        else tot.push_back(tot[i - 1] + allEdge[i]);
        //cout << allEdge[i] << endl;
    }
    if (tot.empty()) tot.push_back(0);
    int tplt = N - allEdge.size();
    for (int i = 1; i <= C; ++i) {
        if (tplt <= q[i].h) {
            llint res = 1ll * tplt * q[i].b;
           // cout << "r: " << res << endl;
            //q[i].h - tplt
            int mx = upper_bound(allEdge.begin(), allEdge.end(), q[i].b) - allEdge.begin();
            if (mx == allEdge.size()) {
                writeln(res + tot.back());
                continue;
            }
            //mx: id > q[i].b
            int sl = allEdge.size() - mx;
            sl = min(sl, q[i].h - tplt);
            mx = allEdge.size() - sl - 1;

           // cout << mx << endl;
           // cout << "r: " << tot[mx] << endl;
            res = res + 1ll * q[i].b * sl + (mx >= 0 ? tot[mx] : 0);
            writeln(res);
        }
        else {
            writeln(-1);
        }
    }
}

void solve() {
    buildEdge();
    buildMST();
    calcQuery();
}

int main() {
    openFile();
    enter();
    solve();
    return 0;
}

Compilation message (stderr)

construction.cpp: In function 'void calcQuery()':
construction.cpp:208:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < allEdge.size(); ++i) {
                       ^
construction.cpp:221:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if (mx == allEdge.size()) {
                    ^

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