Submission #284826

#	Time	Username	Problem	Language	Result	Execution time	Memory
284826		arnold518	도로 건설 사업 (JOI13_construction)	C++14	40 / 100	5080 ms	73036 KiB

construction

#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;

void massert(bool p)
{
	if(!p) while(1);
}

int getcomp(int x)
{
	return lower_bound(comp.begin(), comp.end(), x)-comp.begin()+1;
}


ll tree[MAXV+10];
void init() { memset(tree, 0, sizeof(tree)); }
void update(int i, int k) { for(; i<=MAXV; i+=(i&-i)) tree[i]+=k; }
ll query(int i) { ll ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
ll query(int l, int r) { return query(r)-query(l-1); }

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());

	massert(comp.size()<=MAXV);

	{
		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(getcomp(it.y1), it.p);
				update(getcomp(it.y2), it.p);
			}
			else
			{
				if(query(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(getcomp(it.y1), it.p);
				update(getcomp(it.y2), it.p);
			}
			else
			{
				if(query(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;
		massert(it.w>0);
	}
	massert(S<N);


	for(int i=1; i<=C; i++)
	{
		scanf("%lld%lld", &D[i].B, &D[i].H);

		if(N-D[i].H>S) { printf("-1\n"); continue; }
		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);
	}
	return 0;
}

Compilation message (stderr)

construction.cpp: In function 'int main()':
construction.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   81 |  scanf("%d%d%d", &N, &M, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:82:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   82 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:83:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   83 |  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:198:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  198 |   scanf("%lld%lld", &D[i].B, &D[i].H);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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