oj.uz

Submission #34023

# Submission time Handle Problem Language Result Execution time Memory
34023 2017-11-06T09:26:19 Z cheater2k 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 1899 ms 118200 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAX = 800010;

struct SegmentTree {
	int T[MAX * 4], lz[MAX * 4];
	SegmentTree() {}
	void reset(int sz) { for (int i = 0; i < 4 * sz + 5; ++i) T[i] = lz[i] = 0; }

	#define mid ((l + r) >> 1) 
	void push(int v, int l, int r) {
		if (l < r) lz[v << 1] += lz[v], lz[v << 1 | 1] += lz[v];
		T[v] += lz[v];
		lz[v] = 0;
	}
	void upd(int v, int l, int r, int L, int R, int val) {
		push(v, l, r);
		if (l > r || R < l || L > r) return;
		if (L <= l && r <= R) { lz[v] += val; push(v, l, r); return; }
		upd(v << 1, l, mid, L, R, val); upd(v << 1 | 1, mid + 1, r, L, R, val);
		T[v] = max(T[v << 1], T[v << 1 | 1]);
	}
	int get(int v, int l, int r, int L, int R) {
		push(v, l, r);
		if (l > r || R < l || L > r) return 0;
		if (L <= l && r <= R) return T[v];
		return max(get(v << 1, l, mid, L, R), get(v << 1 | 1, mid + 1, r, L, R));
	}
} seg;
struct Query {
	int x; int y; int _y; int type;
	bool operator < (const Query &rhs) const { 
		if (x != rhs.x) return x < rhs.x;
		if (type <= 0 || rhs.type <= 0) return type < rhs.type;
		return y < rhs.y;
	}
} a[MAX];

int N, M, C;
int mnx[MAX], mxx[MAX], mny[MAX], mxy[MAX];
int par[MAX];

typedef pair<int,int> ii;
typedef pair<int, ii> II;
vector <II> edges, span;
long long pre[MAX];

int dist(Query p, Query q) {
	return abs(p.x - q.x) + abs(p.y - q.y);
}

void build() {
	vector<int> z;
	vector<Query> qu;

	// compress
	for (int i = 1; i <= N; ++i) z.push_back(a[i].y);
	for (int i = 1; i <= M; ++i) z.push_back(mny[i]), z.push_back(mxy[i]);
	sort(z.begin(), z.end());
	z.resize(distance(z.begin(), unique(z.begin(), z.end())));

	for (int i = 1; i <= N; ++i) {
		qu.push_back({a[i].x, a[i].y, 0, i});
	}
	for (int i = 1; i <= M; ++i) {
		int _y1 = lower_bound(z.begin(), z.end(), mny[i]) - z.begin() + 1;
		int _y2 = lower_bound(z.begin(), z.end(), mxy[i]) - z.begin() + 1;
		qu.push_back({mnx[i]    , _y1, _y2, 0});
		qu.push_back({mxx[i] + 1, _y1, _y2, -2});
	}
	sort(qu.begin(), qu.end());
	seg.reset(z.size());

	// process queries
	for (int i = 0; i < qu.size(); ) {
		int val = qu[i].x;
		int j = i; while(i < qu.size() && qu[i].x == val) ++i;
		while(j < i) {
			if (qu[j].type <= 0) {
				int tp = qu[j].type + 1;
				seg.upd(1, 1, z.size(), qu[j].y, qu[j]._y, tp);
				++j;
			} else break;
		}
		++j;
		while(j < i) {
			int _y1 = lower_bound(z.begin(), z.end(), qu[j-1].y) - z.begin() + 1;
			int _y2 = lower_bound(z.begin(), z.end(), qu[j].y) - z.begin() + 1;

			int ok = seg.get(1, 1, z.size(), _y1, _y2);
			if (ok == 0) {
				edges.push_back({ dist(qu[j-1], qu[j]), {qu[j-1].type, qu[j].type} });
			}
			++j;
		}
	}
}

long long ans;
long long res[MAX];

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) { p = anc(p), q = anc(q); par[p] = q; }

struct Company {
	int b; int h; int id;
	bool operator < (const Company &rhs) {
		return b < rhs.b;
	}
} c[MAX];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	// init
	cin >> N >> M >> C;
	for (int i = 1; i <= N; ++i) cin >> a[i].x >> a[i].y, a[i].type = i;
	for (int i = 1; i <= M; ++i) {
		cin >> mnx[i] >> mny[i] >> mxx[i] >> mxy[i];
	}
	build();
	for (int i = 1; i <= N; ++i) swap(a[i].x, a[i].y);
	for (int i = 1; i <= M; ++i) swap(mnx[i], mny[i]), swap(mxx[i], mxy[i]);
	build();
	
	// solve
	for (int i = 1; i <= C; ++i) cin >> c[i].b >> c[i].h, c[i].id = i;
	sort(c + 1, c + C + 1);

	int ncc = N;
	for (int i = 1; i <= N; ++i) par[i] = i;

	sort(edges.begin(), edges.end());
	for (auto &it : edges) {
		int u = anc(it.second.first), v = anc(it.second.second);
		if (u != v) {
			join(u, v);
			span.push_back(it);
		}
	}
	for (int i = 0; i < span.size(); ++i) pre[i+1] = pre[i] + span[i].first;

	int ptr = 0;
	long long ans = 0;
	for (int i = 1; i <= C; ++i) {
		while(ptr < span.size() && span[ptr].first <= c[i].b) {
			ans += span[ptr].first, --ncc, ++ptr;
		}
		if (c[i].h >= ncc) res[c[i].id] = ans + 1LL * ncc * c[i].b;
		else {
			int p = ncc - c[i].h;
			if (ptr + p > span.size()) res[c[i].id] = -1;
			else {
				res[c[i].id] = ans + 1LL * c[i].h * c[i].b + pre[ptr + p] - pre[ptr];
			}	
		}
	}
	for (int i = 1; i <= C; ++i) printf("%lld\n", res[i]);
}

Compilation message

construction.cpp: In function 'void build()':
construction.cpp:76:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < qu.size(); ) {
                    ^
construction.cpp:78:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   int j = i; while(i < qu.size() && qu[i].x == val) ++i;
                      ^
construction.cpp: In function 'int main()':
construction.cpp:141:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < span.size(); ++i) pre[i+1] = pre[i] + span[i].first;
                    ^
construction.cpp:146:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr < span.size() && span[ptr].first <= c[i].b) {
             ^
construction.cpp:152:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (ptr + p > span.size()) res[c[i].id] = -1;
                ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 77820 KB Output is correct
2 Correct 373 ms 87480 KB Output is correct
3 Correct 399 ms 87480 KB Output is correct
4 Correct 436 ms 95680 KB Output is correct
5 Correct 363 ms 88504 KB Output is correct
6 Correct 359 ms 87480 KB Output is correct
7 Correct 279 ms 95680 KB Output is correct
8 Correct 243 ms 89528 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1526 ms 114112 KB Output is correct
2 Correct 1459 ms 114112 KB Output is correct
3 Correct 1579 ms 114108 KB Output is correct
4 Correct 1559 ms 114108 KB Output is correct
5 Correct 923 ms 114360 KB Output is correct
6 Correct 396 ms 88504 KB Output is correct
7 Correct 1676 ms 114112 KB Output is correct
8 Correct 639 ms 118200 KB Output is correct
9 Correct 696 ms 118200 KB Output is correct
10 Correct 849 ms 114104 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 659 ms 87480 KB Output is correct
2 Correct 639 ms 88504 KB Output is correct
3 Correct 676 ms 87480 KB Output is correct
4 Correct 673 ms 95680 KB Output is correct
5 Correct 466 ms 86968 KB Output is correct
6 Correct 573 ms 88504 KB Output is correct
7 Correct 576 ms 87480 KB Output is correct
8 Correct 576 ms 87480 KB Output is correct
9 Correct 466 ms 95680 KB Output is correct
10 Correct 439 ms 89528 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1893 ms 114112 KB Output is correct
2 Correct 1309 ms 95688 KB Output is correct
3 Correct 1749 ms 114120 KB Output is correct
4 Correct 573 ms 86584 KB Output is correct
5 Correct 1879 ms 114112 KB Output is correct
6 Correct 626 ms 86488 KB Output is correct
7 Correct 1599 ms 114104 KB Output is correct
8 Correct 1899 ms 114136 KB Output is correct
9 Correct 859 ms 118200 KB Output is correct
10 Correct 1029 ms 114104 KB Output is correct
11 Correct 469 ms 89528 KB Output is correct