oj.uz

Submission #199735

# Submission time Handle Problem Language Result Execution time Memory
199735 2020-02-03T04:12:19 Z arnold518 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 1282 ms 71460 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 = 6e5;
const ll INF = 2e18;

struct Point { int x, y, p; };
struct Rect { int x1, y1, x2, y2; };
struct Line
{
	int x, y1, y2, p;
	bool operator < (const Line &p) const { return x<p.x; }
};
struct Edge
{
	int u, v, w;
	bool operator < (const Edge &p) const { return w<p.w; }
};

int N, M, C, SX, SY, S;
Point A[MAXN+10];
Rect B[MAXN+10];
vector<int> xcomp, ycomp;
vector<Edge> E;
ll D[MAXN+10];

int getxcomp(int x) { return lower_bound(xcomp.begin(), xcomp.end(), x)-xcomp.begin()+1; }
int getycomp(int y) { return lower_bound(ycomp.begin(), ycomp.end(), y)-ycomp.begin()+1; }

struct BIT
{
	int tree[MAXN+10];
	BIT() { memset(tree, 0, sizeof(tree)); }
	void update(int i, int v) { for(; i<=S; i+=(i&-i)) tree[i]+=v; }
	void updater(int l, int r) { update(l, 1); update(r+1, -1); }
	int query(int i) { int ret=0; for(; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
}bit;

int xcnt[MAXN+10], ycnt[MAXN+10];

int par[MAXN+10];
int Find(int x) { return x==par[x] ? x : par[x]=Find(par[x]); }
void Union(int x, int y) { x=Find(x); y=Find(y); par[x]=y; }

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

struct Query
{
	ll b; int h, p;
	bool operator < (const Query &p) const { return h<p.h; }
}query[MAXN+10];
ll ans[MAXN+10];

int main()
{
	int i, j;

	scanf("%d%d%d", &N, &M, &C);
	for(i=1; i<=N; i++)
	{
		scanf("%d%d", &A[i].x, &A[i].y); A[i].p=i;
		xcomp.push_back(A[i].x);
		ycomp.push_back(A[i].y);
	}
	for(i=1; i<=M; i++)
	{
		scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
		xcomp.push_back(B[i].x1); xcomp.push_back(B[i].x2);
		ycomp.push_back(B[i].y1); ycomp.push_back(B[i].y2);
	}
	for(i=1; i<=C; i++) scanf("%lld%d", &query[i].b, &query[i].h), query[i].p=i;

	sort(query+1, query+C+1);

	sort(xcomp.begin(), xcomp.end());
	xcomp.erase(unique(xcomp.begin(), xcomp.end()), xcomp.end());
	sort(ycomp.begin(), ycomp.end());
	ycomp.erase(unique(ycomp.begin(), ycomp.end()), ycomp.end());
	SX=xcomp.size(); SY=ycomp.size(); S=max(SX, SY);

	vector<Line> todo;
	todo.clear(); bit=BIT();
	for(i=1; i<=M; i++) todo.push_back({B[i].x1, B[i].y1, B[i].y2, 0}), todo.push_back({B[i].x2, B[i].y1, B[i].y2, 0});
	for(i=1; i<=N; i++) todo.push_back({A[i].x, A[i].y, A[i].y, A[i].p});
	sort(todo.begin(), todo.end());

	for(auto it : todo)
	{
		if(it.p==0) bit.updater(getycomp(it.y1), getycomp(it.y2));
		else xcnt[it.p]=bit.query(getycomp(it.y1));
	}

	todo.clear(); bit=BIT();
	for(i=1; i<=M; i++) todo.push_back({B[i].y1, B[i].x1, B[i].x2, 0}), todo.push_back({B[i].y2, B[i].x1, B[i].x2, 0});
	for(i=1; i<=N; i++) todo.push_back({A[i].y, A[i].x, A[i].x, A[i].p});
	sort(todo.begin(), todo.end());

	for(auto it : todo)
	{
		if(it.p==0) bit.updater(getxcomp(it.y1), getxcomp(it.y2));
		else ycnt[it.p]=bit.query(getxcomp(it.y1));
	}

	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(i=1; i<=N;)
	{
		int y=A[i].y;
		for(i++; i<=N && A[i].y==y; i++)
		{
			if(xcnt[A[i].p]==xcnt[A[i-1].p])
			{
				int u=A[i].p, v=A[i-1].p, w=A[i].x-A[i-1].x;
				E.push_back({u, v, w});
			}
		}
	}

	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(i=1; i<=N;)
	{
		int x=A[i].x;
		for(i++; i<=N && A[i].x==x; i++)
		{
			if(ycnt[A[i].p]==ycnt[A[i-1].p])
			{
				int u=A[i].p, v=A[i-1].p, w=A[i].y-A[i-1].y;
				E.push_back({u, v, w});
			}
		}
	}

	sort(E.begin(), E.end());
	for(i=1; i<=N; i++) par[i]=i;

	for(i=1; i<N; i++) D[i]=INF;
	int cnt=N;
	for(auto it : E)
	{
		if(Find(it.u)==Find(it.v)) continue;
		Union(it.u, it.v);
		cnt--; D[cnt]=D[cnt+1]+it.w;
	}

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

Compilation message

construction.cpp: In member function 'll CHT::query(ll)':
construction.cpp:64:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    int mid=lo+hi>>1;
            ~~^~~
construction.cpp: In function 'int main()':
construction.cpp:83:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &M, &C);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
construction.cpp:86:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &A[i].x, &A[i].y); A[i].p=i;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:92:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &B[i].x1, &B[i].y1, &B[i].x2, &B[i].y2);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:96:63: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=C; i++) scanf("%lld%d", &query[i].b, &query[i].h), query[i].p=i;
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 6072 KB Output is correct
2 Correct 299 ms 25300 KB Output is correct
3 Correct 298 ms 25152 KB Output is correct
4 Correct 279 ms 25544 KB Output is correct
5 Correct 315 ms 28632 KB Output is correct
6 Correct 301 ms 25556 KB Output is correct
7 Correct 192 ms 27128 KB Output is correct
8 Correct 228 ms 25556 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 929 ms 31804 KB Output is correct
2 Correct 945 ms 43696 KB Output is correct
3 Correct 961 ms 43548 KB Output is correct
4 Correct 949 ms 43576 KB Output is correct
5 Correct 614 ms 37412 KB Output is correct
6 Correct 320 ms 28376 KB Output is correct
7 Correct 930 ms 43448 KB Output is correct
8 Correct 408 ms 48036 KB Output is correct
9 Correct 431 ms 48176 KB Output is correct
10 Correct 667 ms 43568 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 609 ms 40828 KB Output is correct
2 Correct 630 ms 49108 KB Output is correct
3 Correct 620 ms 49040 KB Output is correct
4 Correct 533 ms 46796 KB Output is correct
5 Correct 571 ms 45144 KB Output is correct
6 Correct 683 ms 51296 KB Output is correct
7 Correct 667 ms 52308 KB Output is correct
8 Correct 652 ms 51304 KB Output is correct
9 Correct 457 ms 50516 KB Output is correct
10 Correct 594 ms 48128 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1243 ms 48348 KB Output is correct
2 Correct 881 ms 50244 KB Output is correct
3 Correct 1244 ms 61476 KB Output is correct
4 Correct 590 ms 41812 KB Output is correct
5 Correct 1261 ms 61864 KB Output is correct
6 Correct 595 ms 42840 KB Output is correct
7 Correct 1282 ms 61876 KB Output is correct
8 Correct 1232 ms 66212 KB Output is correct
9 Correct 719 ms 71460 KB Output is correct
10 Correct 1004 ms 64164 KB Output is correct
11 Correct 626 ms 49108 KB Output is correct