oj.uz

Submission #163202

# Submission time Handle Problem Language Result Execution time Memory
163202 2019-11-11T18:06:33 Z TadijaSebez 도로 건설 사업 (JOI13_construction) C++11
100 / 100
 2564 ms 99612 KB 
#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;
}

Compilation message

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 30456 KB Output is correct
2 Correct 359 ms 42600 KB Output is correct
3 Correct 357 ms 42676 KB Output is correct
4 Correct 318 ms 42688 KB Output is correct
5 Correct 382 ms 44504 KB Output is correct
6 Correct 364 ms 42844 KB Output is correct
7 Correct 193 ms 43724 KB Output is correct
8 Correct 290 ms 48168 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2246 ms 83648 KB Output is correct
2 Correct 2207 ms 84048 KB Output is correct
3 Correct 2145 ms 83728 KB Output is correct
4 Correct 2138 ms 83816 KB Output is correct
5 Correct 826 ms 52468 KB Output is correct
6 Correct 394 ms 44484 KB Output is correct
7 Correct 2318 ms 83516 KB Output is correct
8 Correct 533 ms 62292 KB Output is correct
9 Correct 538 ms 62020 KB Output is correct
10 Correct 914 ms 89472 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 58600 KB Output is correct
2 Correct 646 ms 56824 KB Output is correct
3 Correct 600 ms 54460 KB Output is correct
4 Correct 557 ms 52140 KB Output is correct
5 Correct 556 ms 53648 KB Output is correct
6 Correct 709 ms 59360 KB Output is correct
7 Correct 704 ms 57660 KB Output is correct
8 Correct 691 ms 56820 KB Output is correct
9 Correct 451 ms 55348 KB Output is correct
10 Correct 632 ms 59056 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2564 ms 99564 KB Output is correct
2 Correct 1357 ms 72508 KB Output is correct
3 Correct 2504 ms 92920 KB Output is correct
4 Correct 569 ms 51352 KB Output is correct
5 Correct 2433 ms 93356 KB Output is correct
6 Correct 605 ms 53804 KB Output is correct
7 Correct 2268 ms 99612 KB Output is correct
8 Correct 2388 ms 97700 KB Output is correct
9 Correct 870 ms 73532 KB Output is correct
10 Correct 1146 ms 98744 KB Output is correct
11 Correct 635 ms 61864 KB Output is correct