oj.uz

Submission #289914

# Submission time Handle Problem Language Result Execution time Memory
289914 2020-09-03T08:33:09 Z 임성재(#5780) None (JOI12_invitation) C++17
100 / 100
 180 ms 21480 KB 
#include<bits/stdc++.h>
using namespace std;

#define fast ios::sync_with_stdio(false);
#define fi first
#define se second
#define em emplace
#define eb emplace_back
#define mp make_pair
#define all(v) (v).begin(), (v).end()

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll inf = 1e9;
const ll INF = 1e18;

struct edge {
	ll l, r, L, R, w;
	ll s, e, S, E;

	edge(ll a, ll b, ll c, ll d, ll e) {
		l = a;
		r = b;
		L = c;
		R = d;
		w = e;
	}

	bool operator<(const edge &p) {
		return w > p.w;
	}
};

ll n;
ll a, b, c;
ll par[300010];
vector<edge> v;
set<pll> A, B;
map<pll, ll> m, M;
ll cnt;
ll ans;

ll Find(ll a) {
	return par[a] ? par[a] = Find(par[a]) : a;
}

void Union(ll a, ll b) {
	//cout << "uni " << a << " " << b << endl;
	if(Find(a) == Find(b)) return;
	par[Find(b)] = Find(a);
}

int main() {
	fast;

	cin >> a >> b >> c;
	cin >> n;

	for(ll i=1; i<=n; i++) {
		ll p, q, r, s, t;
		cin >> p >> q >> r >> s >> t;

		v.eb(p, q, r, s, t);
	}

	sort(all(v));

	for(auto i : v) {
		ll s = i.l, e = i.r;
		ll S = i.l, E = i.r;

		cnt++;
		ans -= i.w;
		
		while(1) {
			auto it = A.lower_bound(mp(i.r, inf+1));
			if(it == A.begin()) {
				ans += i.w * max(0LL, E - i.l + 1);
				m[mp(s, e)] = cnt;
				A.insert(mp(s, e));
				break;
			}


			pll x = *prev(it);
			ll k = m[x];

			if(x.fi <= i.l && i.r <= x.se) {
				Union(k, cnt);
				ans += i.w;
				break;
			}
				
			if(x.se < i.l) {
				ans += i.w * max(0LL, E - i.l + 1);
				m[mp(s, e)] = cnt;
				A.insert(mp(s, e));
				break;
			}

			S = x.se+1;

			ans += i.w * max(0LL, E - S + 1);

			E = x.fi-1;

			e = max(e, x.se);
			s = min(s, x.fi);
			A.erase(x);

			if(Find(cnt) != Find(k)) Union(k, cnt), ans += i.w;
		}

		s = i.L, e = i.R;
		S = i.L, E = i.R;

		cnt++;
		ans -= i.w;
		
		while(1) {
			auto it = B.lower_bound(mp(i.R, inf+1));
			if(it == B.begin()) {
				ans += i.w * max(0LL, E - i.L + 1);
				M[mp(s, e)] = cnt;
				B.insert(mp(s, e));
				break;
			}


			pll x = *prev(it);
			ll k = M[x];

			if(x.fi <= i.L && i.R <= x.se) {
				Union(k, cnt);
				ans += i.w;
				break;
			}
				
			if(x.se < i.L) {
				ans += i.w * max(0LL, E - i.L + 1);
				M[mp(s, e)] = cnt;
				B.insert(mp(s, e));
				break;
			}

			S = x.se+1;

			ans += i.w * max(0LL, E - S + 1);

			E = x.fi-1;

			e = max(e, x.se);
			s = min(s, x.fi);
			B.erase(x);

			if(Find(cnt) != Find(k)) Union(k, cnt), ans += i.w;
		}

		if(Find(cnt) != Find(cnt-1)) Union(cnt-1, cnt), ans += i.w;
	}

	for(ll i=1; i<=cnt; i++) {
		if(Find(i) != Find(1)) {
			cout << -1;
			return 0;
		}
	}

	ll l = 0;
	for(auto i : A) {
		if(i.fi != l+1) {
			cout << -1;
			return 0;
		}

		l = i.se;
	}

	if(l != a) {
		cout << -1;
		return 0;
	}

	l = 0;
	for(auto i : B) {
		if(i.fi != l+1) {
			cout << -1;
			return 0;
		}

		l = i.se;
	}

	if(l != b) {
		cout << -1;
		return 0;
	}

	cout << ans;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct
2 Correct 2 ms 624 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct
2 Correct 2 ms 624 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 624 KB Output is correct
2 Correct 3 ms 752 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 9716 KB Output is correct
2 Correct 125 ms 9716 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9716 KB Output is correct
2 Correct 180 ms 21476 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 9716 KB Output is correct
2 Correct 124 ms 9844 KB Output is correct
3 Correct 109 ms 9712 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 9716 KB Output is correct
2 Correct 177 ms 21480 KB Output is correct
3 Correct 114 ms 9712 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 9716 KB Output is correct
2 Correct 89 ms 9872 KB Output is correct
3 Correct 88 ms 9716 KB Output is correct