Submission #787343

# Submission time Handle Problem Language Result Execution time Memory
787343 2023-07-19T05:55:59 Z 박상훈(#10032) 도로 건설 사업 (JOI13_construction) C++17
0 / 100
17 ms 1512 KB
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr ll INF = 4e18;

struct Event{
	int x, l, r, typ;
	Event(){}
	Event(int _x, int _l, int _r, int _t): x(_x), l(_l), r(_r), typ(_t) {}
	bool operator < (const Event &E)const{
		return tie(x, typ) < tie(E.x, E.typ);
	}
};

struct Seg{
	int tree[400400], sz;
	set<pair<int, int>> st;
	void init(int n){
		sz = n;
		fill(tree, tree+sz*2, 0);
		st.clear();
	}

	void update(int l, int r, int x){
		if (x < 0){
			auto iter = st.lower_bound(pair<int, int>(l, -1));
			while(iter!=st.end() && iter->first <= r){
				// printf("  delete %d %d\n", iter->first, iter->second);
				iter = st.erase(iter);
			} 
		}

		++r;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1){
				tree[l] += x;
				l++;
			}
			if (r&1){
				--r;
				tree[r] += x;
			}
		}
	}

	void push(int p, int x){
		auto iter = st.lower_bound(pair<int, int>(p, -1));
		if (iter!=st.end() && iter->first==p) st.erase(iter);

		st.emplace(p, x);
	}

	int query(int p){
		int o = p;
		int ret = 0;
		for (p+=sz;p;p>>=1) ret += tree[p];
		if (ret < 0) return ret;

		p = o;
		auto iter = st.lower_bound(pair<int, int>(p, -1));
		if (iter!=st.end() && iter->first==p) return iter->second;
		return 0;
	}
}tree;

struct Edge{
	int u, v, w;
	Edge(){}
	Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}

	bool operator < (const Edge &E) const{
		return w < E.w;
	}
};

struct DSU{
	int path[200200];
	void init(int n){
		for (int i=1;i<=n;i++) path[i] = i;
	}

	int find(int s){
		if (s==path[s]) return s;
		return path[s] = find(path[s]);
	}

	bool merge(int s, int v){
		s = find(s), v = find(v);
		if (s==v) return false;
		path[v] = s;
		return true;
	}
}dsu;

int x[200200], y[200200], Px[200200], Py[200200], Qx[200200], Qy[200200];
vector<int> Cx, Cy;
vector<Edge> E;

ll f[200200];
int lim;

inline int dist(int i, int j){return abs(x[i] - x[j]) + abs(y[i] - y[j]);}
void compress(vector<int> &a){
	sort(a.begin(), a.end());
	a.erase(unique(a.begin(), a.end()), a.end());
}
int getidx(const vector<int> &a, int x){return lower_bound(a.begin(), a.end(), x) - a.begin();}

void sweep(int n, int m){
	vector<Event> Q;

	for (int i=1;i<=n;i++){
		Q.emplace_back(x[i], getidx(Cy, y[i]), i, 1);
	}

	for (int i=1;i<=m;i++){
		Q.emplace_back(Px[i], getidx(Cy, Py[i]), getidx(Cy, Qy[i]), 0);
		Q.emplace_back(Qx[i], getidx(Cy, Py[i]), getidx(Cy, Qy[i]), 2);
	}

	tree.init(Cy.size() + 10);
	sort(Q.begin(), Q.end());
	for (auto &[_, l, r, typ]:Q){
		// printf(" Event at x = %d: %d %d %d\n", _, l, r, typ);
		if (typ==0){
			tree.update(l, r, -1);
		}
		else if (typ==1){
			int tmp = tree.query(l);
			if (tmp > 0){
				// printf("  ok %d %d %d\n", tmp, r, dist(tmp, r));
				E.emplace_back(tmp, r, dist(tmp, r));
			} 

			if (tmp >= 0){
				tree.push(l, r);
			}
		}
		else{
			tree.update(l, r, 1);
		}
	}

	// printf("ok done\n");
}

void run(int n){
	dsu.init(n);
	sort(E.begin(), E.end());

	lim = n;
	f[lim] = 0;
	for (auto &[u, v, w]:E){
		// printf(" ok edge %d %d %d\n", u, v, w);
		if (dsu.merge(u, v)){
			--lim;
			f[lim] = f[lim+1] + w;
		}
	}
}

ll calc(int x, ll c){
	return c*x + f[x];
}

ll query(int c, int mx){
	int l = lim, r = mx;
	ll ans = INF;

	while(r-l>=4){
		int m1 = (l+r)>>1;
		int m2 = m1+1;

		if (calc(m1, c) > calc(m2, c)) l = m1+1;
		else r = m1-1;
	}

	for (int i=l;i<=r;i++) ans = min(ans, calc(i, c));
	return ans==INF?-1:ans;
}

int main(){
	int n, m, q;
	scanf("%d %d %d", &n, &m, &q);

	for (int i=1;i<=n;i++){
		scanf("%d %d", x+i, y+i);
		Cx.push_back(x[i]);
		Cy.push_back(y[i]);
	}

	for (int i=1;i<=m;i++){
		scanf("%d %d %d %d", Px+i, Py+i, Qx+i, Qy+i);
		Cx.push_back(Px[i]);
		Cx.push_back(Qx[i]);

		Cy.push_back(Py[i]);
		Cy.push_back(Qy[i]);
	}

	compress(Cx); compress(Cy);

	sweep(n, m);

	// flip xy
	for (int i=1;i<=n;i++){
		swap(x[i], y[i]);
	}
	for (int i=1;i<=m;i++){
		swap(Px[i], Py[i]);
		swap(Qx[i], Qy[i]);
	}
	swap(Cx, Cy);

	sweep(n, m);

	// get mst
	run(n);

	while(q--){
		int b, h;
		scanf("%d %d", &b, &h);
		printf("%lld\n", query(b, h));
	}
}

Compilation message

construction.cpp: In function 'int main()':
construction.cpp:185:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |  scanf("%d %d %d", &n, &m, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:188:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |   scanf("%d %d", x+i, y+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
construction.cpp:194:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  194 |   scanf("%d %d %d %d", Px+i, Py+i, Qx+i, Qy+i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
construction.cpp:223:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  223 |   scanf("%d %d", &b, &h);
      |   ~~~~~^~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1512 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 1512 KB Output isn't correct
2 Halted 0 ms 0 KB -