Submission #377782

#	Time	Username	Problem	Language	Result	Execution time	Memory
377782		hoaphat1	도로 건설 사업 (JOI13_construction)	C++17	100 / 100	2480 ms	100180 KiB

construction

#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 (stderr)

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 / 10
• Subtask 2: 30 / 30
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30