oj.uz

Submission #284826

# Submission time Handle Problem Language Result Execution time Memory
284826 2020-08-28T05:22:11 Z arnold518 도로 건설 사업 (JOI13_construction) C++14
40 / 100
 5000 ms 73036 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16964 KB Output is correct
2 Correct 263 ms 26780 KB Output is correct
3 Correct 278 ms 30688 KB Output is correct
4 Correct 319 ms 36956 KB Output is correct
5 Correct 309 ms 31412 KB Output is correct
6 Correct 275 ms 30892 KB Output is correct
7 Correct 242 ms 38288 KB Output is correct
8 Correct 205 ms 33112 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16964 KB Output is correct
2 Correct 263 ms 26780 KB Output is correct
3 Correct 278 ms 30688 KB Output is correct
4 Correct 319 ms 36956 KB Output is correct
5 Correct 309 ms 31412 KB Output is correct
6 Correct 275 ms 30892 KB Output is correct
7 Correct 242 ms 38288 KB Output is correct
8 Correct 205 ms 33112 KB Output is correct
9 Correct 1066 ms 57936 KB Output is correct
10 Correct 1095 ms 58008 KB Output is correct
11 Correct 1082 ms 57744 KB Output is correct
12 Correct 1079 ms 57884 KB Output is correct
13 Correct 701 ms 65188 KB Output is correct
14 Correct 303 ms 31416 KB Output is correct
15 Correct 1068 ms 57856 KB Output is correct
16 Correct 564 ms 73036 KB Output is correct
17 Correct 556 ms 72908 KB Output is correct
18 Correct 645 ms 68668 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16964 KB Output is correct
2 Correct 263 ms 26780 KB Output is correct
3 Correct 278 ms 30688 KB Output is correct
4 Correct 319 ms 36956 KB Output is correct
5 Correct 309 ms 31412 KB Output is correct
6 Correct 275 ms 30892 KB Output is correct
7 Correct 242 ms 38288 KB Output is correct
8 Correct 205 ms 33112 KB Output is correct
9 Execution timed out 5080 ms 32852 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 16964 KB Output is correct
2 Correct 263 ms 26780 KB Output is correct
3 Correct 278 ms 30688 KB Output is correct
4 Correct 319 ms 36956 KB Output is correct
5 Correct 309 ms 31412 KB Output is correct
6 Correct 275 ms 30892 KB Output is correct
7 Correct 242 ms 38288 KB Output is correct
8 Correct 205 ms 33112 KB Output is correct
9 Correct 1066 ms 57936 KB Output is correct
10 Correct 1095 ms 58008 KB Output is correct
11 Correct 1082 ms 57744 KB Output is correct
12 Correct 1079 ms 57884 KB Output is correct
13 Correct 701 ms 65188 KB Output is correct
14 Correct 303 ms 31416 KB Output is correct
15 Correct 1068 ms 57856 KB Output is correct
16 Correct 564 ms 73036 KB Output is correct
17 Correct 556 ms 72908 KB Output is correct
18 Correct 645 ms 68668 KB Output is correct
19 Execution timed out 5080 ms 32852 KB Time limit exceeded
20 Halted 0 ms 0 KB -