oj.uz

Submission #143016

# Submission time Handle Problem Language Result Execution time Memory
143016 2019-08-12T15:18:44 Z kig9981 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 1566 ms 104856 KB 
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

struct lichao
{
	int l, r;
	long long A, B;
	lichao() : l(0), r(0), A(0), B(0x7fffffffffffffffLL) {}
};

const int MAX=1e9;
vector<lichao> node(2);
int tree[600001], color[200000];
long long B[200001], ans[500000];
vector<int> x, y;
vector<tuple<int,int,int>> Edge, Q;
vector<pair<int,int>> P;
vector<tuple<int,int,int,int>> S;
vector<vector<pair<int,int>>> L, R, E;

int get_sign(long long a)
{
	return a<0 ? -1:a>0;
}

void add_line(long long A, long long B, int p=1, int s=1, int e=MAX)
{
	int m=(s+e)>>1;
	long long &pA=node[p].A, &pB=node[p].B;
	long long ys=A*s+B, ym=A*m+B, ye=A*e+B;
	long long pys=pA*s+pB, pym=pA*m+pB, pye=pA*e+pB;
	if(pym>ym) {
		swap(A,pA); swap(B,pB);
		swap(ys,pys); swap(ym,pym); swap(ye,pye);
	}
	if(ys>=pys && ye>=pye) return;
	if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) {
		if(node[p].l==0) node[p].l=node.size(), node.push_back(lichao());
		add_line(A,B,node[p].l,s,m);
	}
	else {
		if(node[p].r==0) node[p].r=node.size(), node.push_back(lichao());
		add_line(A,B,node[p].r,m+1,e);
	}
}

long long query(int x, int p=1, int s=1, int e=MAX)
{
	if(p==0) return 0x7fffffffffffffffLL;
	int m=(s+e)>>1;
	return min(node[p].A*x+node[p].B,x<=m ? query(x,node[p].l,s,m):query(x,node[p].r,m+1,e));
}

int find_(int a)
{
	return color[a]=a==color[a] ? a:find_(color[a]);
}

void union_(int a, int b)
{
	a=find_(a); b=find_(b);
	color[a]=color[b]=min(a,b);
}

void update(int n, int v)
{
	for(++n;n<=600000;n+=n&-n) tree[n]+=v;
}

int get_cnt(int n)
{
	int ret=0;
	for(++n;n;n-=n&-n) ret+=tree[n];
	return ret;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	TEST(freopen("input.txt", "r", stdin));
	TEST(freopen("output.txt", "w", stdout));
	TEST(freopen("debug.txt", "w", stderr));
	int N, M, C, cnt;
	cin>>N>>M>>C; cnt=N;
	P.resize(N);
	for(int i=0;i<N;i++) {
		int X, Y;
		cin>>X>>Y;
		P[i]=make_pair(X,Y);
		x.push_back(X);
		y.push_back(Y);
		color[i]=i;
	}
	S.resize(M);
	for(int i=0;i<M;i++) {
		int x1, y1, x2, y2;
		cin>>x1>>y1>>x2>>y2;
		x.push_back(x1); x.push_back(x2);
		y.push_back(y1); y.push_back(y2);
		S[i]=make_tuple(x1,y1,x2,y2);
	}
	sort(x.begin(),x.end()); sort(y.begin(),y.end());
	x.resize(unique(x.begin(),x.end())-x.begin()); y.resize(unique(y.begin(),y.end())-y.begin());
	E.resize(x.size()); L.resize(x.size()); R.resize(x.size());
	for(int i=0;i<N;i++) {
		int X, Y;
		tie(X,Y)=P[i];
		X=lower_bound(x.begin(),x.end(),X)-x.begin();
		Y=lower_bound(y.begin(),y.end(),Y)-y.begin();
		E[X].emplace_back(Y,i);
		P[i]=make_pair(X,Y);
	}
	for(int i=0;i<M;i++) {
		int x1, y1, x2, y2;
		tie(x1,y1,x2,y2)=S[i];
		x1=lower_bound(x.begin(),x.end(),x1)-x.begin();
		y1=lower_bound(y.begin(),y.end(),y1)-y.begin();
		x2=lower_bound(x.begin(),x.end(),x2)-x.begin();
		y2=lower_bound(y.begin(),y.end(),y2)-y.begin();
		L[x1].emplace_back(y1,y2);
		R[x2].emplace_back(y1,y2);
		S[i]=make_tuple(x1,y1,x2,y2);
	}
	for(int c=0;c<x.size();c++) {
		sort(L[c].begin(),L[c].end());
		sort(E[c].begin(),E[c].end());
		sort(R[c].begin(),R[c].end());
		for(auto n: L[c]) update(n.first,1), update(n.second,1);
		for(int i=1;i<E[c].size();i++) if(get_cnt(E[c][i-1].first-1)==get_cnt(E[c][i].first)) {
			Edge.emplace_back(y[E[c][i].first]-y[E[c][i-1].first],E[c][i-1].second,E[c][i].second);
		}
		for(auto n: R[c]) update(n.first,-1), update(n.second,-1);
	}
	E.clear(); L.clear(); R.clear(); memset(tree,0,sizeof(tree));
	E.resize(y.size()); L.resize(y.size()); R.resize(y.size());
	for(int i=0;i<N;i++) {
		int X, Y;
		tie(X,Y)=P[i];
		E[Y].emplace_back(X,i);
	}
	for(int i=0;i<M;i++) {
		int x1, y1, x2, y2;
		tie(x1,y1,x2,y2)=S[i];
		L[y1].emplace_back(x1,x2);
		R[y2].emplace_back(x1,x2);
	}
	for(int c=0;c<y.size();c++) {
		sort(L[c].begin(),L[c].end());
		sort(E[c].begin(),E[c].end());
		sort(R[c].begin(),R[c].end());
		for(auto n: L[c]) update(n.first,1), update(n.second,1);
		for(int i=1;i<E[c].size();i++) if(get_cnt(E[c][i-1].first-1)==get_cnt(E[c][i].first)) {
			Edge.emplace_back(x[E[c][i].first]-x[E[c][i-1].first],E[c][i-1].second,E[c][i].second);
		}
		for(auto n: R[c]) update(n.first,-1), update(n.second,-1);
	}
	sort(Edge.begin(),Edge.end());
	for(int i=0;i<Edge.size();i++) {
		int w, u, v;
		tie(w,u,v)=Edge[i];
		if(find_(u)!=find_(v)) {
			union_(u,v);
			B[cnt-1]=B[cnt]+w;
			cnt--;
		}
	}
	Q.resize(C);
	for(int i=0;i<C;i++) {
		int b, h;
		cin>>b>>h;
		Q[i]=make_tuple(h,b,i);
	}
	sort(Q.begin(),Q.end());
	for(int i=0;i<C;i++) {
		int h, b, idx;
		tie(h,b,idx)=Q[i];
		for(;cnt<=h;cnt++) add_line(cnt,B[cnt]);
		ans[idx]=query(b);
		if(ans[idx]==0x7fffffffffffffffLL) ans[idx]=-1;
	}
	for(int i=0;i<C;i++) cout<<ans[i]<<'\n';
	return 0;
}

Compilation message

construction.cpp: In function 'void add_line(long long int, long long int, int, int, int)':
construction.cpp:46:52: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  if(get_sign(ys-pys)*get_sign(ym-pym)<0 || ym==pym && ys<pys) {
                                            ~~~~~~~~^~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:134:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int c=0;c<x.size();c++) {
              ~^~~~~~~~~
construction.cpp:139:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<E[c].size();i++) if(get_cnt(E[c][i-1].first-1)==get_cnt(E[c][i].first)) {
               ~^~~~~~~~~~~~
construction.cpp:157:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int c=0;c<y.size();c++) {
              ~^~~~~~~~~
construction.cpp:162:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=1;i<E[c].size();i++) if(get_cnt(E[c][i-1].first-1)==get_cnt(E[c][i].first)) {
               ~^~~~~~~~~~~~
construction.cpp:168:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<Edge.size();i++) {
              ~^~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4856 KB Output is correct
2 Correct 312 ms 27076 KB Output is correct
3 Correct 315 ms 28852 KB Output is correct
4 Correct 303 ms 18140 KB Output is correct
5 Correct 366 ms 34652 KB Output is correct
6 Correct 317 ms 29120 KB Output is correct
7 Correct 220 ms 18768 KB Output is correct
8 Correct 336 ms 31712 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1248 ms 76436 KB Output is correct
2 Correct 1176 ms 76388 KB Output is correct
3 Correct 1201 ms 76472 KB Output is correct
4 Correct 1192 ms 76368 KB Output is correct
5 Correct 544 ms 27696 KB Output is correct
6 Correct 363 ms 31720 KB Output is correct
7 Correct 1239 ms 76368 KB Output is correct
8 Correct 469 ms 33896 KB Output is correct
9 Correct 465 ms 34048 KB Output is correct
10 Correct 911 ms 85712 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 54680 KB Output is correct
2 Correct 660 ms 53832 KB Output is correct
3 Correct 608 ms 47936 KB Output is correct
4 Correct 623 ms 36952 KB Output is correct
5 Correct 599 ms 49696 KB Output is correct
6 Correct 687 ms 55476 KB Output is correct
7 Correct 673 ms 54168 KB Output is correct
8 Correct 656 ms 50192 KB Output is correct
9 Correct 527 ms 40272 KB Output is correct
10 Correct 742 ms 52372 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1531 ms 102088 KB Output is correct
2 Correct 962 ms 67052 KB Output is correct
3 Correct 1482 ms 95632 KB Output is correct
4 Correct 565 ms 42436 KB Output is correct
5 Correct 1566 ms 95800 KB Output is correct
6 Correct 563 ms 44584 KB Output is correct
7 Correct 1507 ms 104856 KB Output is correct
8 Correct 1539 ms 100192 KB Output is correct
9 Correct 787 ms 55096 KB Output is correct
10 Correct 1219 ms 95848 KB Output is correct
11 Correct 755 ms 54700 KB Output is correct