oj.uz

Submission #24905

# Submission time Handle Problem Language Result Execution time Memory
24905 2017-06-17T05:40:56 Z khsoo01 도로 건설 사업 (JOI13_construction) C++11
100 / 100
 1303 ms 74032 KB 
#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<ll,pll> plll;

ll n, m, q, par[200005];
pll a[200005];
vector<ll> xcp, ycp, wgt, sum;
vector<plll> edg;

struct world {
	ll mx, idx[200005];
	vector<ll> xl[200005];
	vector<pll> c, swp[200005];
	set<ll> exi;
	void solve (vector<ll> &B) {
		for(ll i=0;i<c.size();i++) {
			xl[c[i].X].push_back(i);
			mx = max(mx, c[i].X);
		}
		for(ll i=0;i<=mx;i++) {
			for(auto &T : swp[i]) {
				ll S = T.X, E = T.Y;
				while(true) {
					auto it = exi.lower_bound(S);
					if(it == exi.end() || (*it) >= E) break;
					exi.erase(it);
				}
			}
			for(auto &T : xl[i]) {
				if(exi.find(c[T].Y) != exi.end()) {
					ll L = B[c[T].X] - B[c[idx[c[T].Y]].X];
					edg.push_back({L, {T, idx[c[T].Y]}});
				}
				exi.insert(c[T].Y);
				idx[c[T].Y] = T;
			}
		}
	}
} w1, w2;

void compr (ll &X, vector<ll> &V) {
	X = lower_bound(V.begin(), V.end(), X) - V.begin();
}

ll Find (ll X) {
	if(par[X] == X) return X;
	return par[X] = Find(par[X]);
}

int main()
{
	scanf("%lld%lld%lld",&n,&m,&q);
	for(ll i=1;i<=n;i++) {
		scanf("%lld%lld",&a[i].X,&a[i].Y);
		xcp.push_back(a[i].X);
		ycp.push_back(a[i].Y);
	}
	sort(xcp.begin(), xcp.end());
	xcp.erase(unique(xcp.begin(), xcp.end()), xcp.end());
	sort(ycp.begin(), ycp.end());
	ycp.erase(unique(ycp.begin(), ycp.end()), ycp.end());
	for(ll i=1;i<=n;i++) {
		compr(a[i].X, xcp);
		compr(a[i].Y, ycp);
		w1.c.push_back({a[i].X, a[i].Y});
		w2.c.push_back({a[i].Y, a[i].X});
	}
	for(ll i=1;i<=m;i++) {
		ll xs, xe, ys, ye;
		scanf("%lld%lld%lld%lld",&xs,&ys,&xe,&ye);
		xe++; ye++;
		compr(xs, xcp); compr(xe, xcp);
		compr(ys, ycp); compr(ye, ycp);
		w1.swp[xs].push_back({ys, ye});
		w2.swp[ys].push_back({xs, xe});
	}
	w1.solve(xcp);
	w2.solve(ycp);
	sort(edg.begin(), edg.end());
	for(ll i=0;i<n;i++) par[i] = i;
	for(auto &T : edg) {
		ll A = T.Y.X, B = T.Y.Y, C = T.X;
		A = Find(A); B = Find(B);
		if(A != B) {
			par[A] = B;
			wgt.push_back(C);
		}
	}
	sort(wgt.begin(), wgt.end());
	for(auto &T : wgt) {
		sum.push_back((sum.empty()?0:sum.back()) + T);
	}
	for(ll i=1;i<=q;i++) {
		ll A, B;
		scanf("%lld%lld",&A,&B); B--;
		if(wgt.size() + B < n-1) {puts("-1"); continue;}
		ll I = A; compr(I, wgt);
		ll C = max(n-1-B, I);
		printf("%lld\n",(C?sum[C-1]:0)+(n-C)*A);
	}
}

Compilation message

construction.cpp: In member function 'void world::solve(std::vector<long long int>&)':
construction.cpp:20:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(ll i=0;i<c.size();i++) {
               ^
construction.cpp: In function 'int main()':
construction.cpp:100:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(wgt.size() + B < n-1) {puts("-1"); continue;}
                     ^
construction.cpp:56:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld%lld",&n,&m,&q);
                                ^
construction.cpp:58:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a[i].X,&a[i].Y);
                                    ^
construction.cpp:74:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld%lld%lld",&xs,&ys,&xe,&ye);
                                            ^
construction.cpp:99:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B); B--;
                          ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 29412 KB Output is correct
2 Correct 619 ms 58928 KB Output is correct
3 Correct 643 ms 58420 KB Output is correct
4 Correct 396 ms 64948 KB Output is correct
5 Correct 743 ms 70408 KB Output is correct
6 Correct 653 ms 58368 KB Output is correct
7 Correct 186 ms 64312 KB Output is correct
8 Correct 459 ms 70948 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 973 ms 58652 KB Output is correct
2 Correct 976 ms 58644 KB Output is correct
3 Correct 906 ms 58512 KB Output is correct
4 Correct 886 ms 58516 KB Output is correct
5 Correct 626 ms 57076 KB Output is correct
6 Correct 739 ms 70452 KB Output is correct
7 Correct 946 ms 58648 KB Output is correct
8 Correct 306 ms 72712 KB Output is correct
9 Correct 339 ms 72568 KB Output is correct
10 Correct 793 ms 74032 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 976 ms 58116 KB Output is correct
2 Correct 949 ms 65088 KB Output is correct
3 Correct 916 ms 57888 KB Output is correct
4 Correct 696 ms 65040 KB Output is correct
5 Correct 959 ms 58816 KB Output is correct
6 Correct 1133 ms 73484 KB Output is correct
7 Correct 949 ms 58004 KB Output is correct
8 Correct 919 ms 57896 KB Output is correct
9 Correct 429 ms 64312 KB Output is correct
10 Correct 863 ms 70948 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 58512 KB Output is correct
2 Correct 846 ms 54024 KB Output is correct
3 Correct 1036 ms 58648 KB Output is correct
4 Correct 706 ms 50116 KB Output is correct
5 Correct 1119 ms 58516 KB Output is correct
6 Correct 646 ms 49752 KB Output is correct
7 Correct 1303 ms 63660 KB Output is correct
8 Correct 1156 ms 58672 KB Output is correct
9 Correct 603 ms 72312 KB Output is correct
10 Correct 1073 ms 74024 KB Output is correct
11 Correct 836 ms 71504 KB Output is correct