Submission #35203

#TimeUsernameProblemLanguageResultExecution timeMemory
35203ztrong도로 건설 사업 (JOI13_construction)C++14
100 / 100
989 ms41492 KiB
#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()) {
                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...