Submission #35253

#TimeUsernameProblemLanguageResultExecution timeMemory
35253bql20000도로 건설 사업 (JOI13_construction)C++14
100 / 100
1018 ms40380 KiB
#include <bits/stdc++.h> #define ff(i,a,b) for(int i=(a), _b=(b); i<=_b; ++i) #define gg(i,a,b) for(int i=(a), _b=(b); i>=_b; --i) #define REP(i,b) for(int i=(0), _b=(b); i< _b; ++i) #define endl '\n' #define long long long #define ALL(x) (x).begin(), (x).end() #define Love(a) {cerr << #a << " = " << a << endl;} #define _ << "," << #define BIT(i, x) (((x)>>(i))&1) #define X first #define Y second #define gc getchar #define pc putchar #define NAME "Construction" using namespace std; const int N = 2e5 + 8, maxQ = 5e5 + 7; typedef pair<int, int> ii; inline void read(int &x){ register int c = gc(); x = 0; int neg = 0; for (;((c<48 || c>57) && c != '-') ;c = gc()); if(c=='-') {neg=1;c=gc();} for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;} if(neg) x=-x; } inline void writeln(long x){ char buffor[21]; register int i=0; int neg=0; if (x<0) {neg=1; x= -x;} do{ buffor[i++]=(x%10)+'0'; x/=10; } while(x); i--; if (neg) pc('-'); while(i>=0) pc(buffor[i--]); pc('\n'); } struct HCN { int x, y, u, v; HCN () {} HCN (int x, int y, int u, int v) : x(x), y(y), u(u), v(v) {} }rect[N]; struct city { int x, y, id; city () {} bool operator < (const city &b) { return x < b.x || x == b.x && y < b.y; } }a[N]; struct Doan { int x, l, r; bool open; Doan () {} Doan (int x, int l, int r, bool open) : x(x), l(l), r(r), open(open) {} bool operator < (const Doan &b) {return x < b.x;} void print() { cerr << x << ' ' << l << ' ' << r << ' ' << open << endl; } }Line[2*N]; struct edge { int x, y, w; edge () {} edge (int x, int y, int w) : x(x), y(y), w(w) {} bool operator < (const edge &b) {return w < b.w;}; }e[2*N]; int n, m, Q, rankX, rankY, E, lab[N], TPLT; long pre[N]; void Enter() { read(n); read(m); read(Q); ff(i, 1, n) { read(a[i].x); read(a[i].y); a[i].id = i; } ff(i, 1, m) { read(rect[i].x); read(rect[i].y); read(rect[i].u); read(rect[i].v); } } void CreateLine() { ff(i, 1, m) { Line[i] = Doan(rect[i].x, rect[i].y, rect[i].v, 1); Line[i+m] = Doan(rect[i].u+1, rect[i].y, rect[i].v, 0); //rect[u]+1 => tri tue vai~ } sort(Line+1, Line+1+2*m); // ff(i, 1, 2*m) { // Love(i); Line[i].print(); // } } multiset<int> st; void BuildEdge() { CreateLine(); sort(a+1, a+1+n); //sort cac diem theo x tang dan, x = nhau thi y tang dan //ff(i, 1, n) Love(i _ a[i].x _ a[i].y) st.clear(); int k = 1; ff(i, 2, n) if (a[i].x == a[i-1].x) { for(; k <= 2*m && Line[k].x <= a[i].x; ++k) { if (Line[k].open) { st.insert(Line[k].l); st.insert(Line[k].r); } else { st.erase(st.find(Line[k].l)); st.erase(st.find(Line[k].r)); } } multiset<int> :: iterator it = st.lower_bound(a[i-1].y); if (it == st.end() || (*it) > a[i].y) { e[++E] = edge(a[i].id, a[i-1].id, a[i].y - a[i-1].y); } } } void Reverse() { ff(i, 1, n) { swap(a[i].x , a[i].y); } ff(i, 1, m) { swap(rect[i].x, rect[i].y); swap(rect[i].u, rect[i].v); } } int FindSet(int u) { return lab[u] < 0 ? u : lab[u] = FindSet(lab[u]); } void Union(int r, int s) { --TPLT; if (lab[r] < lab[s]) swap(r, s); if (lab[r] == lab[s]) lab[s]--; lab[r] = s; } void Answer() { sort(e+1, e+1+E); fill_n(lab, n+1, -1); TPLT = n; vector <int> v; long res = 0; ff(i, 1, E) { int r = FindSet(e[i].x), s = FindSet(e[i].y); if (r != s) { Union(r, s); res += e[i].w; v.push_back(e[i].w); } } int top = v.size(); REP(i, top) pre[i] = (i == 0 ? v[i] : pre[i-1] + v[i]); ff(i, 1, Q) { int w, cnt; read(w); read(cnt); if (cnt < TPLT) writeln(-1); else { //if (v.back() <= w) cout << pre[top-1] + 1ll * w * TPLT << endl; int x = v.end() - upper_bound(ALL(v), w); int can = min(cnt - TPLT, x); long ans = (can == top ? 0 : pre[top-can-1]) + 1ll * (can + TPLT) * w; writeln(ans); } } } void Process() { BuildEdge(); Reverse(); BuildEdge(); //ff(i, 1, E) Love(e[i].x _ e[i].y _ e[i].w) Answer(); } int main() { //ios_base::sync_with_stdio(0); cin.tie(0); //freopen(NAME".inp", "r", stdin); // freopen(NAME".out", "w", stdout); Enter(); Process(); return 0; }

Compilation message (stderr)

construction.cpp: In member function 'bool city::operator<(const city&)':
construction.cpp:57:36: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
         return x < b.x || x == b.x && y < b.y;
                                    ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...