oj.uz

Submission #289830

# Submission time Handle Problem Language Result Execution time Memory
289830 2020-09-03T06:24:19 Z 임성재(#5780) None (JOI12_invitation) C++17
80 / 100
 171 ms 17264 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 int inf = 1e9;
const ll INF = 1e18;

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

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

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

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

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

void Union(int a, int 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(int i=1; i<=n; i++) {
		int 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) {
		int 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;
			}


			pii x = *prev(it);
			int 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;
			}


			pii x = *prev(it);
			int 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;
		
		//cout << ans << " " << cnt << endl;
	}

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

	int 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 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 0 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 5112 KB Output is correct
2 Incorrect 117 ms 5108 KB Output isn't correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 5236 KB Output is correct
2 Correct 168 ms 17140 KB Output is correct

Subtask #8
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 5240 KB Output is correct
2 Incorrect 114 ms 5120 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 81 ms 5108 KB Output is correct
2 Correct 171 ms 17264 KB Output is correct
3 Correct 106 ms 5112 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 5108 KB Output is correct
2 Correct 81 ms 5112 KB Output is correct
3 Correct 81 ms 5112 KB Output is correct