Submission #287070

#TimeUsernameProblemLanguageResultExecution timeMemory
287070cki86201도로 건설 사업 (JOI13_construction)C++17
0 / 100
360 ms37844 KiB
#include <bits/stdc++.h> using namespace std; #define Fi first #define Se second typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; #define all(x) (x).begin(), (x).end() #define pb push_back #define szz(x) (int)(x).size() #define rep(i, n) for(int i=0;i<(n);i++) typedef tuple<int, int, int> t3; const int INF = 1e9; struct tree { static const int L = 1 << 19; ll T[L*2], C[L*2]; void add_node(int rt, int x) { T[rt] += x; C[rt] += x; } void pushdown(int rt) { if(C[rt]) { add_node(rt*2, C[rt]); add_node(rt*2+1, C[rt]); C[rt] = 0; } } void update(int s, int e, int x, int rt = 1, int l = 0, int r = L-1) { if(s <= l && r <= e) { add_node(rt, x); return; } pushdown(rt); int m = (l + r) >> 1; if(s <= m) update(s, e, x, rt*2, l, m); if(m < e) update(s, e, x, rt*2+1, m+1, r); T[rt] = max(T[rt*2], T[rt*2+1]); } int Read(int s, int e, int rt = 1, int l = 0, int r = L-1) { if(s <= l && r <= e) return T[rt]; pushdown(rt); int m = (l + r) >> 1, res = 0; if(s <= m) res = max(res, Read(s, e, rt*2, l, m)); if(m < e) res = max(res, Read(s, e, rt*2+1, m+1, r)); return res; } void init() { memset(T, 0, sizeof T); memset(C, 0, sizeof C); } } tree; int N, M, C; struct rect { int x1, y1, x2, y2; } R[200020]; struct point { int x, y, id; } P[200020]; struct event { int x, y1, y2, i1, i2; }; vector <t3> E; void Do(vector <int> &vy) { sort(P+1, P+1+N, [](point a, point b) { return tie(a.x, a.y) < tie(b.x, b.y); }); vector <event> V; for(int i=1;i<N;i++) if(P[i].x == P[i+1].x) { V.pb({P[i].x, P[i].y, P[i+1].y, P[i].id, P[i+1].id}); } for(int i=1;i<=M;i++) { V.pb({R[i].x1, R[i].y1, R[i].y2, -1, 0}); V.pb({R[i].x2, R[i].y1, R[i].y2, INF, 0}); } sort(all(V), [](const event &a, const event &b) { return tie(a.x, a.i1) < tie(b.x, b.i1); }); tree.init(); for(auto &[x, y1, y2, i1, i2] : V) { if(i1 == -1) tree.update(y1, y2, 1); else if(i1 == INF) tree.update(y1, y2, -1); else { int v = tree.Read(y1, y2); if(v == 0) E.pb({vy[y2] - vy[y1], i1, i2}); } } } int pp[200020]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); } int main() { scanf("%d%d%d", &N, &M, &C); vector <int> vx, vy; for(int i=1;i<=N;i++) { int x, y; scanf("%d%d", &x, &y); P[i] = {x, y, i}; vx.pb(x); vy.pb(y); } for(int i=1;i<=M;i++) { int x1, y1, x2, y2; scanf("%d%d%d%d", &x1, &y1, &x2, &y2); R[i] = {x1, y1, x2, y2}; vx.pb(x1), vx.pb(x2); vy.pb(y1), vy.pb(y2); } sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin()); sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin()); auto fix = [](vector <int> &a, int &b) { b = (int)(lower_bound(all(a), b) - a.begin()); }; for(int i=1;i<=N;i++) fix(vx, P[i].x), fix(vy, P[i].y); for(int i=1;i<=M;i++) { fix(vx, R[i].x1), fix(vx, R[i].x2); fix(vy, R[i].y1), fix(vy, R[i].y2); } rep(v, 2) { Do(v == 0 ? vy : vx); for(int i=1;i<=M;i++) { swap(R[i].x1, R[i].y1); swap(R[i].x2, R[i].y2); } for(int i=1;i<=N;i++) swap(P[i].x, P[i].y); } sort(all(E)); for(int i=1;i<=N;i++) pp[i] = i; vector <int> V; vector <ll> SV; for(auto &[l, x, y] : E) { int px = Find(x), py = Find(y); if(px != py) V.pb(l); } int lv = szz(V); SV.resize(lv); rep(i, lv) SV[i] = (i ? SV[i-1] : 0) + V[i]; rep(c, C) { int b, h; scanf("%d%d", &b, &h); if(N - lv > h) puts("-1"); else { int cnt = (int)(lower_bound(all(V), b) - V.begin()); cnt = max(cnt, N - h); printf("%lld\n", (ll)(N - cnt) * b + (cnt ? SV[cnt-1] : 0)); } } return 0; }

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:93:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   93 |  scanf("%d%d%d", &N, &M, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:96:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   96 |   int x, y; scanf("%d%d", &x, &y);
      |             ~~~~~^~~~~~~~~~~~~~~~
construction.cpp:102:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  102 |   scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  138 |   scanf("%d%d", &b, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...