Submission #49486

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49486	2018-05-29T15:48:04 Z	minkank	도로 건설 사업 (JOI13_construction)	C++17	Compilation error	0 ms	0 KB

construction

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int, int> ii;
typedef pair<int, ii> II;
#define x first
#define y second

const int N = 5e5 + 5;

struct data {
	int x, y, x2, y2;
};

int n, m, c, par[N];
long long f[N];
II qu[N * 2];
data p[N * 2];
vector<II> E;

bool cmp(data u, data v) {
	return u.x < v.x;
}

void sweep() {
	sort(p + 1, p + n + m + 1, cmp);
	set<ii> s;
	for(int i = 1; i <= n + m; ++i) {
		if(p[i].x2 < 0) {
			set<ii>::iterator it = s.lower_bound(ii(p[i].y, 0));
			if(it != s.end() && (*it).x == p[i].y) {
				int id = (*it).y;
				E.push_back(II(p[i].x - p[id].x, ii(-p[id].x2, -p[i].x2)));
				s.erase(it);
			}
			s.insert(ii(p[i].y, i));
		}
		else {
			while(1) {
				set<ii>::iterator it = s.lower_bound(ii(p[i].y, 0));
				if(it == s.end() || (*it).x > p[i].y2) break;
				s.erase(it);
			}
		}
	}
}

void reverse() {
	for(int i = 1; i <= n + m; ++i) {
		swap(p[i].x, p[i].x2);
		swap(p[i].y, p[i].y2);
	}
}

int find(int u) {
	if(par[u] == u) return u;
	return par[u] = find(par[u]);
}

bool join(int u, int v) {
	u = find(u); v = find(v);
	if(u == v) return false;
	par[u] = v;
	return true;
}

vector<ii> d;

bool bad(int l1, int l2, int l3) {
	return 1LL * (d[l2].y - d[l1].y) * (d[l3].x - d[l2].x) > 1LL * (d[l3].y - d[l2].y) * (d[l2].x - d[l1].x);
}
 
void add(int a, long long b) {
	d.push_back(ii(a, b));
	while(d.size() >= 3 && !bad(d.size() - 1, d.size() - 2, d.size() - 3)) d.erase(d.end() - 2);
}
 
long long query(int x) {
	int l = 0, r = d.size() - 1;
	while(l != r) {
		int mid = (l + r) >> 1;
		if(1LL * d[mid].x * x + d[mid].y > 1LL * d[mid + 1].x * x + d[mid + 1].y) l = mid + 1;
		else r = mid;
	}
	return 1LL * d[l].x * x + d[l].y;
}

long long ans[N];

signed main() {
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> c;
	for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y, p[i].x2 = p[i].y2 = -i;
	for(int i = 1; i <= m; ++i) cin >> p[i + n].x >> p[i + n].y >> p[i + n].x >> p[i + n].y;
	sweep();
	reverse();
	sweep();
	sort(E.begin(), E.end());
	int tot = 0;
	vector<int> E2;
	for(int i = 1; i <= n; ++i) par[i] = i;
	for(int i = E.size() - 1; i >= 0; --i) {
		int w = E[i].x, u = E[i].y.x, v = E[i].y.y;
		if(join(u, v)) E2.push_back(w), tot += w;
	}
	int cnt = 0;
	for(int i = 1; i <= n; ++i) if(find(i) == i) cnt++;
	memset(f, 69, sizeof f);
	f[cnt] = tot;
	for(int i = 0; i < E2.size(); ++i) {
		tot -= E2[i];
		f[cnt + 1 + i] = tot;
	}
	for(int i = 1; i <= c; ++i) cin >> qu[i].y.x >> qu[i].x, qu[i].y.y = i;
	for(int i = 1; i <= n; ++i) qu[i + c].x = i, qu[i + c].y.y = -1;
	sort(qu + 1, qu + n + c + 1);
	for(int i = 1; i <= n + c; ++i) {
		if(qu[i].y.y < 0) {
			add(qu[i].x, f[qu[i].x]);
		}
		else {
			ans[qu[i].y.y] = query(qu[i].y.x);
		}
	}
	for(int i = 1; i <= c; ++i) {
		if(ans[i] > 1e18) ans[i] = -1;
		cout << ans[i] << '\n';
	}
}

Compilation message

construction.cpp:20:1: error: reference to 'data' is ambiguous
 data p[N * 2];
 ^~~~
construction.cpp:13:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from construction.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
construction.cpp:23:10: error: reference to 'data' is ambiguous
 bool cmp(data u, data v) {
          ^~~~
construction.cpp:13:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from construction.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
construction.cpp:23:18: error: reference to 'data' is ambiguous
 bool cmp(data u, data v) {
                  ^~~~
construction.cpp:13:8: note: candidates are: struct data
 struct data {
        ^~~~
In file included from /usr/include/c++/7/string:51:0,
                 from /usr/include/c++/7/bits/locale_classes.h:40,
                 from /usr/include/c++/7/bits/ios_base.h:41,
                 from /usr/include/c++/7/ios:42,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from construction.cpp:1:
/usr/include/c++/7/bits/range_access.h:318:5: note:                 template<class _Tp> constexpr const _Tp* std::data(std::initializer_list<_Tp>)
     data(initializer_list<_Tp> __il) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:309:5: note:                 template<class _Tp, long unsigned int _Nm> constexpr _Tp* std::data(_Tp (&)[_Nm])
     data(_Tp (&__array)[_Nm]) noexcept
     ^~~~
/usr/include/c++/7/bits/range_access.h:299:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(const _Container&)
     data(const _Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
/usr/include/c++/7/bits/range_access.h:289:5: note:                 template<class _Container> constexpr decltype (__cont.data()) std::data(_Container&)
     data(_Container& __cont) noexcept(noexcept(__cont.data()))
     ^~~~
construction.cpp:23:24: error: expression list treated as compound expression in initializer [-fpermissive]
 bool cmp(data u, data v) {
                        ^
construction.cpp: In function 'void sweep()':
construction.cpp:28:7: error: 'p' was not declared in this scope
  sort(p + 1, p + n + m + 1, cmp);
       ^
construction.cpp: In function 'void reverse()':
construction.cpp:52:8: error: 'p' was not declared in this scope
   swap(p[i].x, p[i].x2);
        ^
construction.cpp: In function 'int main()':
construction.cpp:95:37: error: 'p' was not declared in this scope
  for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y, p[i].x2 = p[i].y2 = -i;
                                     ^
construction.cpp:96:37: error: 'p' was not declared in this scope
  for(int i = 1; i <= m; ++i) cin >> p[i + n].x >> p[i + n].y >> p[i + n].x >> p[i + n].y;
                                     ^
construction.cpp:112:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < E2.size(); ++i) {
                 ~~^~~~~~~~~~~