oj.uz

Submission #284828

# Submission time Handle Problem Language Result Execution time Memory
284828 2020-08-28T05:41:47 Z arnold518 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 1353 ms 100200 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 p;
};

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], ans[MAXC+10];

struct LLine { ll a, b; };
double cross(LLine p, LLine q) { return (double)(q.b-p.b)/(p.a-q.a); }

struct CHT
{
	vector<LLine> S;
	void update(LLine p)
	{
		while(S.size()>1 && cross(S[S.size()-1], S[S.size()-2])<=cross(S[S.size()-1], p)) S.pop_back();
		S.push_back(p);
	}
	ll query(ll x)
	{
		if(S.empty()) return -1;
		int lo=0, hi=S.size();
		while(lo+1<hi)
		{
			int mid=lo+hi>>1;
			if(cross(S[mid], S[mid-1])>=x) lo=mid;
			else hi=mid;
		}
		return S[lo].a*x+S[lo].b;
	}
} cht;

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);
		D[i].p=i; D[i].h=N-D[i].h;
	}
	sort(D+1, D+C+1, [&](const Query &p, const Query &q)
	{
		return p.h>q.h;
	});

	for(int i=1, j=S; i<=C; i++)
	{
		for(; j>=0 && j>=D[i].h; j--) cht.update({N-j, VV[j]});
		ans[D[i].p]=cht.query(D[i].b);
	}
	for(int i=1; i<=C; i++) printf("%lld\n", ans[i]);
}

Compilation message

construction.cpp: In member function 'll CHT::query(ll)':
construction.cpp:95:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   95 |    int mid=lo+hi>>1;
      |            ~~^~~
construction.cpp: In function 'int main()':
construction.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  105 |  scanf("%d%d%d", &N, &M, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:106:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |  for(int i=1; i<=N; i++) scanf("%d%d", &A[i].x, &A[i].y), A[i].p=i;
      |                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:107:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  107 |  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:221:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  221 |   scanf("%lld%lld", &D[i].b, &D[i].h);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16840 KB Output is correct
2 Correct 263 ms 27052 KB Output is correct
3 Correct 284 ms 27200 KB Output is correct
4 Correct 302 ms 35028 KB Output is correct
5 Correct 294 ms 31744 KB Output is correct
6 Correct 274 ms 27304 KB Output is correct
7 Correct 243 ms 35112 KB Output is correct
8 Correct 200 ms 29272 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16840 KB Output is correct
2 Correct 263 ms 27052 KB Output is correct
3 Correct 284 ms 27200 KB Output is correct
4 Correct 302 ms 35028 KB Output is correct
5 Correct 294 ms 31744 KB Output is correct
6 Correct 274 ms 27304 KB Output is correct
7 Correct 243 ms 35112 KB Output is correct
8 Correct 200 ms 29272 KB Output is correct
9 Correct 1092 ms 46460 KB Output is correct
10 Correct 1058 ms 46336 KB Output is correct
11 Correct 1051 ms 46320 KB Output is correct
12 Correct 1086 ms 46360 KB Output is correct
13 Correct 704 ms 59812 KB Output is correct
14 Correct 288 ms 31868 KB Output is correct
15 Correct 1063 ms 46524 KB Output is correct
16 Correct 519 ms 64460 KB Output is correct
17 Correct 525 ms 64332 KB Output is correct
18 Correct 639 ms 57044 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16840 KB Output is correct
2 Correct 263 ms 27052 KB Output is correct
3 Correct 284 ms 27200 KB Output is correct
4 Correct 302 ms 35028 KB Output is correct
5 Correct 294 ms 31744 KB Output is correct
6 Correct 274 ms 27304 KB Output is correct
7 Correct 243 ms 35112 KB Output is correct
8 Correct 200 ms 29272 KB Output is correct
9 Correct 602 ms 58028 KB Output is correct
10 Correct 629 ms 62584 KB Output is correct
11 Correct 582 ms 58536 KB Output is correct
12 Correct 584 ms 53956 KB Output is correct
13 Correct 521 ms 54276 KB Output is correct
14 Correct 630 ms 64844 KB Output is correct
15 Correct 630 ms 61868 KB Output is correct
16 Correct 605 ms 60728 KB Output is correct
17 Correct 529 ms 57500 KB Output is correct
18 Correct 550 ms 58124 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 16840 KB Output is correct
2 Correct 263 ms 27052 KB Output is correct
3 Correct 284 ms 27200 KB Output is correct
4 Correct 302 ms 35028 KB Output is correct
5 Correct 294 ms 31744 KB Output is correct
6 Correct 274 ms 27304 KB Output is correct
7 Correct 243 ms 35112 KB Output is correct
8 Correct 200 ms 29272 KB Output is correct
9 Correct 1092 ms 46460 KB Output is correct
10 Correct 1058 ms 46336 KB Output is correct
11 Correct 1051 ms 46320 KB Output is correct
12 Correct 1086 ms 46360 KB Output is correct
13 Correct 704 ms 59812 KB Output is correct
14 Correct 288 ms 31868 KB Output is correct
15 Correct 1063 ms 46524 KB Output is correct
16 Correct 519 ms 64460 KB Output is correct
17 Correct 525 ms 64332 KB Output is correct
18 Correct 639 ms 57044 KB Output is correct
19 Correct 602 ms 58028 KB Output is correct
20 Correct 629 ms 62584 KB Output is correct
21 Correct 582 ms 58536 KB Output is correct
22 Correct 584 ms 53956 KB Output is correct
23 Correct 521 ms 54276 KB Output is correct
24 Correct 630 ms 64844 KB Output is correct
25 Correct 630 ms 61868 KB Output is correct
26 Correct 605 ms 60728 KB Output is correct
27 Correct 529 ms 57500 KB Output is correct
28 Correct 550 ms 58124 KB Output is correct
29 Correct 1340 ms 53856 KB Output is correct
30 Correct 879 ms 55656 KB Output is correct
31 Correct 1332 ms 53404 KB Output is correct
32 Correct 540 ms 54372 KB Output is correct
33 Correct 1353 ms 49672 KB Output is correct
34 Correct 543 ms 51068 KB Output is correct
35 Correct 1234 ms 64204 KB Output is correct
36 Correct 1325 ms 66564 KB Output is correct
37 Correct 811 ms 100200 KB Output is correct
38 Correct 972 ms 68772 KB Output is correct
39 Correct 567 ms 58680 KB Output is correct