제출 #163202

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
163202		TadijaSebez	도로 건설 사업 (JOI13_construction)	C++11	100 / 100	2564 ms	99612 KiB

construction

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N=200050;
struct Edge{ int u,v,w;Edge(){}Edge(int a, int b, int c):u(a),v(b),w(c){}bool operator < (Edge b) const { return w<b.w;}};
vector<Edge> edges;
struct DSU
{
	int p[N];
	DSU(){}
	int Find(int x){ return p[x]?p[x]=Find(p[x]):x;}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
ll ans[N];
int cnt;
void MST()
{
	sort(edges.begin(),edges.end());
	cnt=0;
	for(auto e:edges)
	{
		if(DS.Find(e.u)!=DS.Find(e.v))
		{
			DS.Union(e.u,e.v);
			cnt++;
			ans[cnt]=ans[cnt-1]+e.w;
		}
	}
}
const int H=3*N;
const int M=2*H;
struct SegmentTree
{
	int ls[M],rs[M],tsz,root,lzy[M];
	ll sum[M];
	void init(){ for(int i=1;i<=tsz;i++) ls[i]=rs[i]=lzy[i]=sum[i]=0;tsz=root=0;}
	SegmentTree(){}
	void Add(int &c, int ss, int se, int qs, int qe, int f)
	{
		if(qs>qe || qs>se || ss>qe) return;
		if(!c) c=++tsz;
		if(qs<=ss && qe>=se){ sum[c]+=(ll)(se-ss+1)*f;lzy[c]+=f;return;}
		int mid=ss+se>>1;
		Add(ls[c],ss,mid,qs,qe,f);
		Add(rs[c],mid+1,se,qs,qe,f);
		sum[c]=sum[ls[c]]+sum[rs[c]]+(ll)(se-ss+1)*lzy[c];
	}
	int sec(int ss, int se, int qs, int qe){ return max(0,min(qe,se)-max(qs,ss)+1);}
	ll Get(int c, int ss, int se, int qs, int qe)
	{
		if(qs>qe || ss>qe || qs>se) return 0;
		if(qs<=ss && qe>=se) return sum[c];
		int mid=ss+se>>1;
		return Get(ls[c],ss,mid,qs,qe)+Get(rs[c],mid+1,se,qs,qe)+(ll)sec(ss,se,qs,qe)*lzy[c];
	}
} ST;
vector<int> xs,ys;
int n,m,x[N],y[N],X1[N],Y1[N],X2[N],Y2[N];
vector<pair<int,int>> Us[H];
vector<int> Qs[H];
void Sweep()
{
	for(int i=0;i<=xs.size();i++) Us[i].clear(),Qs[i].clear();
	for(int i=1;i<=n;i++) Qs[x[i]].pb(i);
	for(int i=1;i<=m;i++) Us[X1[i]].pb({i,1}),Us[X2[i]+1].pb({i,-1});
	ST.init();
	for(int i=0;i<xs.size();i++)
	{
		for(auto p:Us[i]) ST.Add(ST.root,0,ys.size(),Y1[p.first],Y2[p.first],p.second);
		sort(Qs[i].begin(),Qs[i].end(),[&](int i, int j){ return y[i]<y[j];});
		for(int j=1;j<Qs[i].size();j++)
		{
			int a=Qs[i][j-1],b=Qs[i][j];
			ll tmp=ST.Get(ST.root,0,ys.size(),y[a],y[b]);
			if(tmp==0) edges.pb(Edge(a,b,ys[y[b]]-ys[y[a]]));
		}
	}
}
int GetX(int x){ return lower_bound(xs.begin(),xs.end(),x)-xs.begin();}
int GetY(int y){ return lower_bound(ys.begin(),ys.end(),y)-ys.begin();}
int main()
{
	int q;
	scanf("%i %i %i",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),xs.pb(x[i]),ys.pb(y[i]);
	for(int i=1;i<=m;i++) scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]),xs.pb(X1[i]),xs.pb(X2[i]),ys.pb(Y1[i]),ys.pb(Y2[i]);
	sort(xs.begin(),xs.end());xs.resize(unique(xs.begin(),xs.end())-xs.begin());
	sort(ys.begin(),ys.end());ys.resize(unique(ys.begin(),ys.end())-ys.begin());
	for(int i=1;i<=n;i++) x[i]=GetX(x[i]),y[i]=GetY(y[i]);
	for(int i=1;i<=m;i++) X1[i]=GetX(X1[i]),X2[i]=GetX(X2[i]),Y1[i]=GetY(Y1[i]),Y2[i]=GetY(Y2[i]);
	Sweep();
	for(int i=1;i<=n;i++) swap(x[i],y[i]);
	for(int i=1;i<=m;i++) swap(X1[i],Y1[i]),swap(X2[i],Y2[i]);
	swap(xs,ys);
	Sweep();
	MST();
	while(q--)
	{
		int b,h;
		scanf("%i %i",&b,&h);
		if(cnt+h<n) printf("-1\n");
		else
		{
			int bot=n-h,top=cnt,mid,sol;
			sol=top;top--;
			while(bot<=top)
			{
				mid=top+bot>>1;
				if(ans[mid]+(ll)b*(n-mid)<ans[mid+1]+(ll)b*(n-mid-1)) sol=mid,top=mid-1;
				else bot=mid+1;
			}
			printf("%lld\n",ans[sol]+(ll)b*(n-sol));
		}
	}
	return 0;
}

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

construction.cpp: In member function 'void SegmentTree::Add(int&, int, int, int, int, int)':
construction.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
construction.cpp: In member function 'long long int SegmentTree::Get(int, int, int, int, int)':
construction.cpp:54:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid=ss+se>>1;
           ~~^~~
construction.cpp: In function 'void Sweep()':
construction.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<=xs.size();i++) Us[i].clear(),Qs[i].clear();
              ~^~~~~~~~~~~
construction.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<xs.size();i++)
              ~^~~~~~~~~~
construction.cpp:72:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=1;j<Qs[i].size();j++)
               ~^~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:109:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     mid=top+bot>>1;
         ~~~^~~~
construction.cpp:85:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i %i",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
construction.cpp:86:62: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=n;i++) scanf("%i %i",&x[i],&y[i]),xs.pb(x[i]),ys.pb(y[i]);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
construction.cpp:87:111: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i %i",&X1[i],&Y1[i],&X2[i],&Y2[i]),xs.pb(X1[i]),xs.pb(X2[i]),ys.pb(Y1[i]),ys.pb(Y2[i]);
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~
construction.cpp:101:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%i %i",&b,&h);
   ~~~~~^~~~~~~~~~~~~~~

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