oj.uz

Submission #289836

# Submission time Handle Problem Language Result Execution time Memory
289836 2020-09-03T06:31:52 Z 임성재(#5780) None (JOI12_invitation) C++17
80 / 100
 170 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;
ll cnt;
ll ans;

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

void Union(ll a, ll b) {
	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()) {
				//cout << "!" << i.l << " " << E << endl;
				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) {
				//cout << "?" << i.l << " " << E << endl;
				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;

		//cout << ans << " " << cnt << endl;

		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];

			//cout << "***" << k << " " << cnt << endl;

			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 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 416 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 3 ms 752 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 3 ms 624 KB Output is correct
2 Correct 3 ms 752 KB Output is correct

Subtask #6
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 9716 KB Output is correct
2 Incorrect 120 ms 9716 KB Output isn't correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 9716 KB Output is correct
2 Correct 166 ms 21480 KB Output is correct

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 9824 KB Output is correct
2 Incorrect 121 ms 9728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 9716 KB Output is correct
2 Correct 170 ms 21480 KB Output is correct
3 Correct 109 ms 9716 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 9716 KB Output is correct
2 Correct 88 ms 9712 KB Output is correct
3 Correct 87 ms 9868 KB Output is correct