oj.uz

Submission #35353

# Submission time Handle Problem Language Result Execution time Memory
35353 2017-11-20T14:12:21 Z DifferentHeaven 도로 건설 사업 (JOI13_construction) C++14
100 / 100
 3276 ms 151024 KB 
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;

using namespace std;

inline void read(int &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void read(long long &x){register int c = getchar();x = 0; int neg = 0;for (;((c<48 || c>57) && c != '-') ;c = getchar());if(c=='-') {neg=1;c=getchar();}for(;c>47 && c<58;c = getchar()) {x = (x<<1) + (x<<3) + c - 48;}if(neg) x=-x;}
inline void writeln(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar('\n');}
inline void write(long long x){char buffor[21];register int i=0;int neg=0; if (x<0) {neg=1; x= -x;}do{buffor[i++]=(x%10)+'0';x/=10;} while(x);i--;if (neg) putchar('-');while(i>=0) putchar(buffor[i--]);putchar(' ');}

const int N = 6e5 + 7;

int n, m, c, gx, gy, nEdge, cnt, q;
long long revx[N], revy[N];
int p[N];
long long pre[N], Edge[N];
vector <int> vx, vy;
map <int, int> mpx, mpy;
ii a[N];

struct edge{
	int u, v, c;
	edge() {}
	edge(int u, int v, int c): u(u), v(v), c(c) {}
	bool operator < (const edge& b) const{
		return c < b.c || (c == b.c && (u < b.u || (u == b.u && (v < b.v))));
	}
}e[N];

struct rect{
	int p, q, r, s;
}rec[N];

struct Point{
	int y, rec, id;
	Point() {}
	Point(int y, int rec, int id): y(y), rec(rec), id(id) {}
	bool operator < (const Point &b) const {
		return y < b.y;
	}
};

vector <Point> v[N];

struct bit{
	int tree[4 * N];

	inline void Update(int x, int val){
		for (int i = x; i < N; i += (i & (-i)))
			tree[i] += val;
	}

	int Query(int x){
		int res = 0;
		for (int i = x; i > 0; i -= (i & (-i)))
			res += tree[i];
		return res;
	}
}BIT;

inline void Compress(){
	sort(vx.begin(), vx.end());
	sort(vy.begin(), vy.end());
	mpx[vx[0]] = gx = 1; revx[1] = vx[0];
	mpy[vy[0]] = gy = 1; revy[1] = vy[0];
	for (int i = 1; i < vx.size(); i++)
		if (vx[i] != vx[i - 1]){
			mpx[vx[i]] = ++gx;
			revx[gx] = vx[i];
		}
	for (int i = 1; i < vy.size(); i++)
		if (vy[i] != vy[i - 1]){
			mpy[vy[i]] = ++gy;
			revy[gy] = vy[i];
		}
	for (int i = 1; i <= n; i++){
		a[i].x = mpx[a[i].x]; a[i].y = mpy[a[i].y];
	}
	for (int i = 1; i <= m; i++){
		rec[i].p = mpx[rec[i].p]; rec[i].q = mpy[rec[i].q];
		rec[i].r = mpx[rec[i].r]; rec[i].s = mpy[rec[i].s];
	}
}

inline void Flip(){
	for (int i = 1; i <= n; i++) 
		swap(a[i].x, a[i].y);
	for (int i = 1; i <= m; i++){
		swap(rec[i].p, rec[i].q);
		swap(rec[i].r, rec[i].s);
	}
	swap(gx, gy);
}

inline void Update(Point x){
	if (!x.rec)
		return;
	if (x.id == 1)
		BIT.Update(x.y, 1);
	else
		BIT.Update(x.y, -1);
}

inline void AddEdge(int u, int v, long long revy[]){
	e[++nEdge] = edge(u, v, abs(revy[a[u].y] - revy[a[v].y]));
}

inline void SweepLine(long long revy[]){
	for (int i = 1; i <= gx; i++)
		v[i].clear();
	for (int i = 1; i <= n; i++){
		v[a[i].x].push_back(Point(a[i].y, 0, i));
	}
	for (int i = 1; i <= m; i++){
		v[rec[i].p].push_back(Point(rec[i].q, 1, 1));
		v[rec[i].r].push_back(Point(rec[i].s, 1, -1));
		v[rec[i].p].push_back(Point(rec[i].s, 1, 1));
		v[rec[i].r].push_back(Point(rec[i].q, 1, -1));
	}
	for (int i = 1; i <= gx; i++)
		sort(v[i].begin(), v[i].end());
	for (int i = 1; i <= gx; i++){
			Update(v[i][0]);
			for (int j = 1; j < v[i].size(); j++){
				if (v[i][j].rec)
					Update(v[i][j]);
				else
					if (!v[i][j - 1].rec)
						if (BIT.Query(v[i][j].y) == BIT.Query(v[i][j - 1].y))
							AddEdge(v[i][j].id, v[i][j - 1].id, revy);
			}
		}
}

int Find(int u){
	if (p[u] < 0) return u;
	return p[u] = Find(p[u]);
}

inline void Union(int u, int v){
	int x = p[u] + p[v];
	if (p[u] < p[v]){
		p[v] = u;
		p[u] = x;
	}
	else{
		p[u] = v;
		p[v] = x;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	// freopen("test.inp", "r", stdin);
	// freopen("test.out", "w", stdout);
	read(n); read(m); read(q);
	for (int i = 1; i <= n; i++){
		read(a[i].x); read(a[i].y);
		vx.push_back(a[i].x);
		vy.push_back(a[i].y);
	}	
	for (int i = 1; i <= m; i++){
		read(rec[i].p); read(rec[i].q); read(rec[i].r); read(rec[i].s);
		vx.push_back(rec[i].p); vx.push_back(rec[i].r);
		vy.push_back(rec[i].q); vy.push_back(rec[i].s);
	}
	Compress();
	SweepLine(revy); Flip();
	SweepLine(revx); Flip();
	for (int i = 1; i <= n; i++)
		p[i] = -1;
	sort(e + 1, e + nEdge + 1);
	int CC = n;
	for (int i = 1; i <= nEdge; i++){
		int u = Find(e[i].u);
		int v = Find(e[i].v);
		int c = e[i].c;
		if (u != v){
			Union(u, v);
			Edge[++cnt] = c;
			CC--;
			if (cnt == n - 1)
				break;
		}
	}
	for (int i = 1; i <= cnt; i++)
		pre[i] = pre[i - 1] + Edge[i];
	int Cost, Num;
	for (int i = 1; i <= q; i++){
		read(Cost); read(Num);
		if (Num < CC){
			writeln(-1);
			continue;
		}
		int l = 1;
		int r = cnt;
		while (l <= r){
			int mid = (l + r) / 2;
			if (Edge[mid] <= Cost)
				l = mid + 1;
			else
				r = mid - 1;
		}
		int pos = l;
		int Add = min(Num - CC, cnt - pos + 1);
		writeln(pre[max(0, cnt - Add)] + 1LL * (Add + CC) * Cost);
	}
}

Compilation message

construction.cpp: In function 'void Compress()':
construction.cpp:69:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < vx.size(); i++)
                    ^
construction.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < vy.size(); i++)
                    ^
construction.cpp: In function 'void SweepLine(long long int*)':
construction.cpp:127:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 1; j < v[i].size(); j++){
                      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 69588 KB Output is correct
2 Correct 673 ms 85612 KB Output is correct
3 Correct 579 ms 85216 KB Output is correct
4 Correct 276 ms 74392 KB Output is correct
5 Correct 679 ms 85216 KB Output is correct
6 Correct 643 ms 85216 KB Output is correct
7 Correct 163 ms 73080 KB Output is correct
8 Correct 459 ms 90932 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3273 ms 141520 KB Output is correct
2 Correct 2939 ms 141520 KB Output is correct
3 Correct 2919 ms 141652 KB Output is correct
4 Correct 2889 ms 141652 KB Output is correct
5 Correct 703 ms 93208 KB Output is correct
6 Correct 576 ms 85216 KB Output is correct
7 Correct 2983 ms 141520 KB Output is correct
8 Correct 413 ms 101708 KB Output is correct
9 Correct 353 ms 101016 KB Output is correct
10 Correct 1483 ms 143416 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 833 ms 85216 KB Output is correct
2 Correct 803 ms 85220 KB Output is correct
3 Correct 833 ms 85612 KB Output is correct
4 Correct 453 ms 74788 KB Output is correct
5 Correct 776 ms 89572 KB Output is correct
6 Correct 963 ms 87328 KB Output is correct
7 Correct 953 ms 85216 KB Output is correct
8 Correct 799 ms 85216 KB Output is correct
9 Correct 336 ms 72948 KB Output is correct
10 Correct 779 ms 90932 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3086 ms 141520 KB Output is correct
2 Correct 1816 ms 112344 KB Output is correct
3 Correct 3143 ms 141520 KB Output is correct
4 Correct 659 ms 86404 KB Output is correct
5 Correct 2976 ms 141524 KB Output is correct
6 Correct 736 ms 88120 KB Output is correct
7 Correct 3276 ms 151024 KB Output is correct
8 Correct 3229 ms 141524 KB Output is correct
9 Correct 579 ms 100436 KB Output is correct
10 Correct 1656 ms 143416 KB Output is correct
11 Correct 776 ms 92480 KB Output is correct