oj.uz

Submission #787348

# Submission time Handle Problem Language Result Execution time Memory
787348 2023-07-19T06:01:30 Z 박상훈(#10032) 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 853 ms 49712 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[2002000], 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 = m2-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);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1312 KB Output is correct
2 Correct 317 ms 16096 KB Output is correct
3 Correct 300 ms 15840 KB Output is correct
4 Correct 269 ms 17336 KB Output is correct
5 Correct 359 ms 20244 KB Output is correct
6 Correct 342 ms 15888 KB Output is correct
7 Correct 155 ms 17312 KB Output is correct
8 Correct 224 ms 22468 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1312 KB Output is correct
2 Correct 317 ms 16096 KB Output is correct
3 Correct 300 ms 15840 KB Output is correct
4 Correct 269 ms 17336 KB Output is correct
5 Correct 359 ms 20244 KB Output is correct
6 Correct 342 ms 15888 KB Output is correct
7 Correct 155 ms 17312 KB Output is correct
8 Correct 224 ms 22468 KB Output is correct
9 Correct 715 ms 39680 KB Output is correct
10 Correct 717 ms 40132 KB Output is correct
11 Correct 686 ms 40160 KB Output is correct
12 Correct 693 ms 40260 KB Output is correct
13 Correct 530 ms 37540 KB Output is correct
14 Correct 376 ms 20696 KB Output is correct
15 Correct 706 ms 40256 KB Output is correct
16 Correct 307 ms 42672 KB Output is correct
17 Correct 306 ms 42708 KB Output is correct
18 Correct 525 ms 44228 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1312 KB Output is correct
2 Correct 317 ms 16096 KB Output is correct
3 Correct 300 ms 15840 KB Output is correct
4 Correct 269 ms 17336 KB Output is correct
5 Correct 359 ms 20244 KB Output is correct
6 Correct 342 ms 15888 KB Output is correct
7 Correct 155 ms 17312 KB Output is correct
8 Correct 224 ms 22468 KB Output is correct
9 Correct 528 ms 23388 KB Output is correct
10 Correct 504 ms 23524 KB Output is correct
11 Correct 520 ms 20636 KB Output is correct
12 Correct 435 ms 17404 KB Output is correct
13 Correct 475 ms 19172 KB Output is correct
14 Correct 599 ms 28476 KB Output is correct
15 Correct 540 ms 23004 KB Output is correct
16 Correct 480 ms 22628 KB Output is correct
17 Correct 342 ms 17160 KB Output is correct
18 Correct 449 ms 27436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 1312 KB Output is correct
2 Correct 317 ms 16096 KB Output is correct
3 Correct 300 ms 15840 KB Output is correct
4 Correct 269 ms 17336 KB Output is correct
5 Correct 359 ms 20244 KB Output is correct
6 Correct 342 ms 15888 KB Output is correct
7 Correct 155 ms 17312 KB Output is correct
8 Correct 224 ms 22468 KB Output is correct
9 Correct 715 ms 39680 KB Output is correct
10 Correct 717 ms 40132 KB Output is correct
11 Correct 686 ms 40160 KB Output is correct
12 Correct 693 ms 40260 KB Output is correct
13 Correct 530 ms 37540 KB Output is correct
14 Correct 376 ms 20696 KB Output is correct
15 Correct 706 ms 40256 KB Output is correct
16 Correct 307 ms 42672 KB Output is correct
17 Correct 306 ms 42708 KB Output is correct
18 Correct 525 ms 44228 KB Output is correct
19 Correct 528 ms 23388 KB Output is correct
20 Correct 504 ms 23524 KB Output is correct
21 Correct 520 ms 20636 KB Output is correct
22 Correct 435 ms 17404 KB Output is correct
23 Correct 475 ms 19172 KB Output is correct
24 Correct 599 ms 28476 KB Output is correct
25 Correct 540 ms 23004 KB Output is correct
26 Correct 480 ms 22628 KB Output is correct
27 Correct 342 ms 17160 KB Output is correct
28 Correct 449 ms 27436 KB Output is correct
29 Correct 849 ms 39600 KB Output is correct
30 Correct 575 ms 26808 KB Output is correct
31 Correct 821 ms 39588 KB Output is correct
32 Correct 412 ms 18232 KB Output is correct
33 Correct 816 ms 39568 KB Output is correct
34 Correct 405 ms 13668 KB Output is correct
35 Correct 817 ms 40244 KB Output is correct
36 Correct 853 ms 39464 KB Output is correct
37 Correct 521 ms 49712 KB Output is correct
38 Correct 636 ms 46896 KB Output is correct
39 Correct 468 ms 30312 KB Output is correct