제출 #284816

#제출 시각아이디문제언어결과실행 시간메모리
284816arnold518도로 건설 사업 (JOI13_construction)C++14
0 / 100
458 ms136564 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXN = 2e5; const int MAXM = 2e5; const int MAXC = 5e5; const int MAXV = 2e6; const ll INF = 1e18; struct Point { int x, y, p; }; struct Rect { int x1, y1, x2, y2; }; struct Line { int x, y1, y2, p, q; }; struct Edge { int u, v, w; }; struct Query { ll B, H; }; int N, M, C; Point A[MAXN+10]; Rect B[MAXM+10]; Query D[MAXC+10]; vector<int> comp; vector<Edge> E; int getcomp(int x) { return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1; } ll tree[MAXV*4+10], lazy[MAXV*4+10]; void init() { memset(tree, 0, sizeof(tree)); memset(lazy, 0, sizeof(lazy)); } void busy(int node, int tl, int tr) { if(lazy[node]==0) return; tree[node]+=lazy[node]*(tr-tl+1); if(tl!=tr) lazy[node*2]+=lazy[node], lazy[node*2+1]+=lazy[node]; lazy[node]=0; } void update(int node, int tl, int tr, int l, int r, int k) { busy(node, tl, tr); if(r<tl || tr<l) return; if(l<=tl && tr<=r) { lazy[node]+=k; busy(node, tl, tr); return; } int mid=tl+tr>>1; update(node*2, tl, mid, l, r, k); update(node*2+1, mid+1, tr, l, r, k); tree[node]=tree[node*2]+tree[node*2+1]; } ll query(int node, int tl, int tr, int l, int r) { busy(node, tl, tr); if(l<=tl && tr<=r) return tree[node]; if(r<tl || tr<l) return 0; int mid=tl+tr>>1; return query(node*2, tl, mid, l, r)+query(node*2+1, mid+1, tr, l, r); } int par[MAXN+10]; int Find(int x) { if(x==par[x]) return x; return par[x]=Find(par[x]); } void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; } ll VV[MAXN+10]; int main() { scanf("%d%d%d", &N, &M, &C); for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i; for(int i=1; i<=M; i++) scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2); for(int i=1; i<=N; i++) comp.push_back(A[i].x), comp.push_back(A[i].y); for(int i=1; i<=M; i++) comp.push_back(B[i].x1), comp.push_back(B[i].x2), comp.push_back(B[i].y1), comp.push_back(B[i].y2); sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); if(comp.size()>MAXV) while(1); { vector<Line> V; init(); sort(A+1, A+N+1, [&](const Point &p, const Point &q) { if(p.x==q.x) return p.y<q.y; return p.x<q.x; }); for(int i=2; i<=N; i++) { if(A[i].x!=A[i-1].x) continue; V.push_back({A[i].x, A[i-1].y, A[i].y, 0, i}); } for(int i=1; i<=M; i++) { V.push_back({B[i].x1, B[i].y1, B[i].y2, 1, 0}); V.push_back({B[i].x2, B[i].y1, B[i].y2, -1, 0}); } sort(V.begin(), V.end(), [&](const Line &p, const Line &q) { if(p.x!=q.x) return p.x<q.x; return p.p>q.p; }); for(auto it : V) { if(it.p!=0) { update(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2), it.p); } else { if(query(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2))==0) { E.push_back({A[it.q-1].p, A[it.q].p, A[it.q].y-A[it.q-1].y}); } } } } //for(auto it : E) printf("E : %d %d %d\n", it.u, it.v, it.w); { vector<Line> V; init(); sort(A+1, A+N+1, [&](const Point &p, const Point &q) { if(p.y==q.y) return p.x<q.x; return p.y<q.y; }); for(int i=2; i<=N; i++) { if(A[i].y!=A[i-1].y) continue; V.push_back({A[i].y, A[i-1].x, A[i].x, 0, i}); } for(int i=1; i<=M; i++) { V.push_back({B[i].y1, B[i].x1, B[i].x2, 1, 0}); V.push_back({B[i].y2, B[i].x1, B[i].x2, -1, 0}); } sort(V.begin(), V.end(), [&](const Line &p, const Line &q) { if(p.x!=q.x) return p.x<q.x; return p.p>q.p; }); for(auto it : V) { if(it.p!=0) { update(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2), it.p); } else { if(query(1, 1, comp.size(), getcomp(it.y1), getcomp(it.y2))==0) { E.push_back({A[it.q-1].p, A[it.q].p, A[it.q].x-A[it.q-1].x}); } } } } //for(auto it : E) printf("E : %d %d %d\n", it.u, it.v, it.w); for(int i=1; i<=N; i++) par[i]=i; sort(E.begin(), E.end(), [&](const Edge &p, const Edge &q) { return p.w<q.w; }); int S=0; for(auto it : E) { if(Find(it.u)==Find(it.v)) continue; Union(it.u, it.v); S++; VV[S]=VV[S-1]+it.w; } for(int i=1; i<=C; i++) { scanf("%lld%lld", &D[i].B, &D[i].H); if(N-D[i].H>S) { return printf("-1\n"); printf("\n"); } ll ans=INF; for(int j=N-D[i].H; j<=S; j++) { ans=min(ans, (N-j)*D[i].B+VV[j]); } if(ans==INF) ans=-1; printf("%lld\n", ans); } }

컴파일 시 표준 에러 (stderr) 메시지

construction.cpp: In function 'void update(int, int, int, int, int, int)':
construction.cpp:78:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |  int mid=tl+tr>>1;
      |          ~~^~~
construction.cpp: In function 'll query(int, int, int, int, int)':
construction.cpp:89:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |  int mid=tl+tr>>1;
      |          ~~^~~
construction.cpp: In function 'int main()':
construction.cpp:119:23: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
  119 |  if(comp.size()>MAXV) while(1);
      |                       ^~~~~
construction.cpp:121:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  121 |  {
      |  ^
construction.cpp:110:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  110 |  scanf("%d%d%d", &N, &M, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:111:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  111 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:112:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  112 |  for(int i=1; i<=M; i++) scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:222:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  222 |   scanf("%lld%lld", &D[i].B, &D[i].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...