oj.uz

Submission #377782

# Submission time Handle Problem Language Result Execution time Memory
377782 2021-03-15T05:08:54 Z hoaphat1 도로 건설 사업 (JOI13_construction) C++17
100 / 100
 2480 ms 100180 KB 
#include <bits/stdc++.h>
 
using namespace std;

class segtree {
 public:
  struct node {
    // don't forget to set default value (used for leaves)
    // not necessarily neutral element!
    int val = 0;
    int put = 0;
 
    void apply(int l, int r, int v) {
      val += v;
      put += v;
    }
  };
 
  node unite(const node &a, const node &b) const {
    node res;
    res.val = max(a.val, b.val);
    return res;
  }
 
  inline void push(int x, int l, int r) {
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    if (tree[x].put != 0) {
      tree[x + 1].apply(l, y, tree[x].put);
      tree[z].apply(y + 1, r, tree[x].put);
      tree[x].put = 0;
    }
  }
 
  inline void pull(int x, int z) {
    tree[x] = unite(tree[x + 1], tree[z]);
  }
 
  int n;
  vector<node> tree;
 
  void build(int x, int l, int r) {
    if (l == r) {
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y);
    build(z, y + 1, r);
    pull(x, z);
  }
 
  template <typename M>
  void build(int x, int l, int r, const vector<M> &v) {
    if (l == r) {
      tree[x].apply(l, r, v[l]);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    build(x + 1, l, y, v);
    build(z, y + 1, r, v);
    pull(x, z);
  }
 
  node get(int x, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) {
      return tree[x];
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    node res{};
    if (rr <= y) {
      res = get(x + 1, l, y, ll, rr);
    } else {
      if (ll > y) {
        res = get(z, y + 1, r, ll, rr);
      } else {
        res = unite(get(x + 1, l, y, ll, rr), get(z, y + 1, r, ll, rr));
      }
    }
    pull(x, z);
    return res;
  }
 
  template <typename... M>
  void modify(int x, int l, int r, int ll, int rr, const M&... v) {
    if (ll <= l && r <= rr) {
      tree[x].apply(l, r, v...);
      return;
    }
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    push(x, l, r);
    if (ll <= y) {
      modify(x + 1, l, y, ll, rr, v...);
    }
    if (rr > y) {
      modify(z, y + 1, r, ll, rr, v...);
    }
    pull(x, z);
  }
 
  int find_first_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[x + 1])) {
      res = find_first_knowingly(x + 1, l, y, f);
    } else {
      res = find_first_knowingly(z, y + 1, r, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_first(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_first_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (ll <= y) {
      res = find_first(x + 1, l, y, ll, rr, f);
    }
    if (rr > y && res == -1) {
      res = find_first(z, y + 1, r, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_last_knowingly(int x, int l, int r, const function<bool(const node&)> &f) {
    if (l == r) {
      return l;
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res;
    if (f(tree[z])) {
      res = find_last_knowingly(z, y + 1, r, f);
    } else {
      res = find_last_knowingly(x + 1, l, y, f);
    }
    pull(x, z);
    return res;
  }
 
  int find_last(int x, int l, int r, int ll, int rr, const function<bool(const node&)> &f) {
    if (ll <= l && r <= rr) {
      if (!f(tree[x])) {
        return -1;
      }
      return find_last_knowingly(x, l, r, f);
    }
    push(x, l, r);
    int y = (l + r) >> 1;
    int z = x + ((y - l + 1) << 1);
    int res = -1;
    if (rr > y) {
      res = find_last(z, y + 1, r, ll, rr, f);
    }
    if (ll <= y && res == -1) {
      res = find_last(x + 1, l, y, ll, rr, f);
    }
    pull(x, z);
    return res;
  }
 
  segtree(int _n) : n(_n) {
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1);
  }
 
  template <typename M>
  segtree(const vector<M> &v) {
    n = v.size();
    assert(n > 0);
    tree.resize(2 * n - 1);
    build(0, 0, n - 1, v);
  }
 
  node get(int ll, int rr) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return get(0, 0, n - 1, ll, rr);
  }
 
  node get(int p) {
    assert(0 <= p && p <= n - 1);
    return get(0, 0, n - 1, p, p);
  }
 
  template <typename... M>
  void modify(int ll, int rr, const M&... v) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    modify(0, 0, n - 1, ll, rr, v...);
  }
 
  // find_first and find_last call all FALSE elements
  // to the left (right) of the sought position exactly once
 
  int find_first(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_first(0, 0, n - 1, ll, rr, f);
  }
 
  int find_last(int ll, int rr, const function<bool(const node&)> &f) {
    assert(0 <= ll && ll <= rr && rr <= n - 1);
    return find_last(0, 0, n - 1, ll, rr, f);
  }
};

struct dsu {
	vector<int> p;
	dsu(int n) {
		p.resize(n, -1);
	}
	int get(int x) {
		return p[x] < 0 ? x : p[x] = get(p[x]);
	}
	int unite(int x, int y) {
		x = get(x); y = get(y);
		if (x != y) {
			if (p[x] < p[y]) swap(x, y);
			p[y] += p[x];
			p[x] = y;
			return 1;
		} 
		return 0;
	}
};

struct node {
	long long a, b;
	node(long long a = 0, long long b = 1e18) : a(a), b(b) {
	}
	long long get(int x) {
		return a * x + b;
	}
};

struct Eins {
	vector<node> st;
	vector<int> b;
	int n;
	Eins(vector<int> &b) : b(b) {
		n = (int) b.size();
		st.resize(n << 2 | 1);
	}
	void modify(int id, int l, int r, node val) {
		int mid = l + r >> 1;
		if (st[id].get(b[mid]) > val.get(b[mid])) swap(val, st[id]);
		if (l == r) return ;
		if (st[id].get(b[l]) > val.get(b[l])) modify(id << 1, l, mid, val);
		if (st[id].get(b[r]) > val.get(b[r])) modify(id << 1|1, mid + 1, r, val);
	}
	long long get(int id, int l, int r, int x) {
		long long ans = st[id].get(x);
		if (l == r) return ans;
		int mid = l + r >> 1;
		if (x <= b[mid]) return min(ans, get(id << 1, l, mid, x));
		return min(ans, get(id << 1|1, mid + 1, r, x));
	}
};

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	#define getp(a, x) get<x>(a)
	int n, m, q;
	cin >> n >> m >> q;
	vector<pair<int,int>> a(n);
	vector<int> b;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second;
		b.push_back(a[i].first);
		b.push_back(a[i].second);
	}
	vector<tuple<int, int, int, int>> ban;
	for (int i = 0; i < m; i++) {
		int u, v, x, y;
		cin >> u >> v >> x >> y;
		ban.emplace_back(u, v, x, y);
		b.push_back(u);
		b.push_back(v);
		b.push_back(x);
		b.push_back(y);
	}
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());
	auto find = [&](int x) {return lower_bound(b.begin(), b.end(), x) - b.begin();};
	for (int i = 0; i < n; i++) {
		a[i].first = find(a[i].first);
		a[i].second = find(a[i].second);
	}
	for (int i = 0; i < m; i++) {
		getp(ban[i], 0) = find(getp(ban[i], 0));
		getp(ban[i], 1) = find(getp(ban[i], 1));
		getp(ban[i], 2) = find(getp(ban[i], 2));
		getp(ban[i], 3) = find(getp(ban[i], 3));
	}
	vector<tuple<int,int,int>> edges;
	auto solve = [&]() {
		vector<int> id(n);
		iota(id.begin(), id.end(), 0);
		sort(id.begin(), id.end(), [&](int x, int y) {
			return a[x] < a[y];
		});
		vector<vector<tuple<int,int,int>>> inner((int) b.size());
		for (auto& x : ban) {
			inner[getp(x, 0)].emplace_back(getp(x, 1), getp(x, 3), 1);
			if (getp(x, 2) + 1 < (int) b.size()) inner[getp(x, 2) + 1].emplace_back(getp(x, 1), getp(x, 3), -1);
		}
		int pos = 0;
		segtree Tree((int) b.size());
		for (int i = 0, j; i < n; i = j) {
			j = i;
			while (j < n && a[id[i]].first == a[id[j]].first) j++;
			while (pos <= a[id[i]].first) {
				for (auto&x : inner[pos]) {
					Tree.modify(getp(x, 0), getp(x, 1), getp(x, 2));
				}
				pos++;
			}
			for (int k = j - 1; k > i; k--) {
				if (Tree.get(a[id[k - 1]].second, a[id[k]].second).val == 0) edges.emplace_back(b[a[id[k]].second] - b[a[id[k-1]].second], id[k-1], id[k]);
			}
		}
	};
	solve();
	for (int i = 0; i < n; i++) swap(a[i].first, a[i].second);
	for (int i = 0; i < m; i++) {
		auto &x = ban[i];
		swap(getp(x, 0), getp(x, 1));
		swap(getp(x, 2), getp(x, 3));
	}
	solve();
	sort(edges.begin(), edges.end());
	int last = n;
	vector<long long> ab(n + 1);
	dsu d(n);
	for (auto& x : edges) {
		if (d.unite(getp(x, 1), getp(x, 2))) {
			--last;
			ab[last] = ab[last + 1] + getp(x, 0);
		}
	}
	vector<vector<pair<int,int>>> Query(n + 1);
	b.clear();
	for (int i = 0; i < q; i++) {
		int c, h;
		cin >> c >> h;
		Query[h].emplace_back(c, i);
		b.push_back(c);
	}
	sort(b.begin(), b.end());
	b.resize(unique(b.begin(), b.end()) - b.begin());
	vector<long long> ans(q);
	Eins Tree(b);
	for (int i = 0; i <= n; i++) {
		if (i >= last) {
			Tree.modify(1, 0, Tree.n - 1, node(i, ab[i]));
		}
		for (auto&x : Query[i]) {
			if (i < last) ans[x.second] = -1;
			else {
				ans[x.second] = Tree.get(1, 0, Tree.n - 1, x.first);
			}
		}
	}
	for (int i = 0; i < q; i++) cout << ans[i] <<"\n";
}

Compilation message

construction.cpp: In member function 'void Eins::modify(int, int, int, node)':
construction.cpp:263:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  263 |   int mid = l + r >> 1;
      |             ~~^~~
construction.cpp: In member function 'long long int Eins::get(int, int, int, int)':
construction.cpp:272:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  272 |   int mid = l + r >> 1;
      |             ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1944 KB Output is correct
2 Correct 378 ms 18260 KB Output is correct
3 Correct 397 ms 17816 KB Output is correct
4 Correct 335 ms 17112 KB Output is correct
5 Correct 432 ms 18032 KB Output is correct
6 Correct 384 ms 17748 KB Output is correct
7 Correct 196 ms 18144 KB Output is correct
8 Correct 269 ms 20472 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1944 KB Output is correct
2 Correct 378 ms 18260 KB Output is correct
3 Correct 397 ms 17816 KB Output is correct
4 Correct 335 ms 17112 KB Output is correct
5 Correct 432 ms 18032 KB Output is correct
6 Correct 384 ms 17748 KB Output is correct
7 Correct 196 ms 18144 KB Output is correct
8 Correct 269 ms 20472 KB Output is correct
9 Correct 2017 ms 63836 KB Output is correct
10 Correct 1991 ms 63984 KB Output is correct
11 Correct 1991 ms 63896 KB Output is correct
12 Correct 2021 ms 63824 KB Output is correct
13 Correct 706 ms 27104 KB Output is correct
14 Correct 416 ms 17996 KB Output is correct
15 Correct 2017 ms 64064 KB Output is correct
16 Correct 518 ms 31468 KB Output is correct
17 Correct 545 ms 35536 KB Output is correct
18 Correct 920 ms 52860 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1944 KB Output is correct
2 Correct 378 ms 18260 KB Output is correct
3 Correct 397 ms 17816 KB Output is correct
4 Correct 335 ms 17112 KB Output is correct
5 Correct 432 ms 18032 KB Output is correct
6 Correct 384 ms 17748 KB Output is correct
7 Correct 196 ms 18144 KB Output is correct
8 Correct 269 ms 20472 KB Output is correct
9 Correct 849 ms 66832 KB Output is correct
10 Correct 980 ms 66616 KB Output is correct
11 Correct 920 ms 65000 KB Output is correct
12 Correct 767 ms 34904 KB Output is correct
13 Correct 790 ms 62932 KB Output is correct
14 Correct 1008 ms 68112 KB Output is correct
15 Correct 815 ms 66364 KB Output is correct
16 Correct 803 ms 65072 KB Output is correct
17 Correct 829 ms 63448 KB Output is correct
18 Correct 732 ms 34880 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1944 KB Output is correct
2 Correct 378 ms 18260 KB Output is correct
3 Correct 397 ms 17816 KB Output is correct
4 Correct 335 ms 17112 KB Output is correct
5 Correct 432 ms 18032 KB Output is correct
6 Correct 384 ms 17748 KB Output is correct
7 Correct 196 ms 18144 KB Output is correct
8 Correct 269 ms 20472 KB Output is correct
9 Correct 2017 ms 63836 KB Output is correct
10 Correct 1991 ms 63984 KB Output is correct
11 Correct 1991 ms 63896 KB Output is correct
12 Correct 2021 ms 63824 KB Output is correct
13 Correct 706 ms 27104 KB Output is correct
14 Correct 416 ms 17996 KB Output is correct
15 Correct 2017 ms 64064 KB Output is correct
16 Correct 518 ms 31468 KB Output is correct
17 Correct 545 ms 35536 KB Output is correct
18 Correct 920 ms 52860 KB Output is correct
19 Correct 849 ms 66832 KB Output is correct
20 Correct 980 ms 66616 KB Output is correct
21 Correct 920 ms 65000 KB Output is correct
22 Correct 767 ms 34904 KB Output is correct
23 Correct 790 ms 62932 KB Output is correct
24 Correct 1008 ms 68112 KB Output is correct
25 Correct 815 ms 66364 KB Output is correct
26 Correct 803 ms 65072 KB Output is correct
27 Correct 829 ms 63448 KB Output is correct
28 Correct 732 ms 34880 KB Output is correct
29 Correct 2480 ms 100180 KB Output is correct
30 Correct 1507 ms 73644 KB Output is correct
31 Correct 2336 ms 94040 KB Output is correct
32 Correct 806 ms 60752 KB Output is correct
33 Correct 2314 ms 94084 KB Output is correct
34 Correct 776 ms 59688 KB Output is correct
35 Correct 2195 ms 70672 KB Output is correct
36 Correct 2420 ms 98560 KB Output is correct
37 Correct 1169 ms 68344 KB Output is correct
38 Correct 1328 ms 48164 KB Output is correct
39 Correct 776 ms 34000 KB Output is correct