Submission #35351

# Submission time Handle Problem Language Result Execution time Memory
35351 2017-11-20T14:05:41 Z DifferentHeaven 도로 건설 사업 (JOI13_construction) C++14
40 / 100
3126 ms 131072 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 = 5e5 + 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];
bool InBIT[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++)
		if (v[i].size()){
			Update(v[i][0]);
			for (int j = 1; j < v[i].size(); j++){
				Update(v[i][j]);
				if (!v[i][j].rec && !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();
	memset(p, -1, sizeof(p));
	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:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < vx.size(); i++)
                    ^
construction.cpp:75: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:129:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int j = 1; j < v[i].size(); j++){
                      ^
# Verdict Execution time Memory Grader output
1 Correct 23 ms 59140 KB Output is correct
2 Correct 593 ms 75164 KB Output is correct
3 Correct 573 ms 74768 KB Output is correct
4 Correct 253 ms 63944 KB Output is correct
5 Correct 586 ms 74768 KB Output is correct
6 Correct 599 ms 74768 KB Output is correct
7 Correct 153 ms 62632 KB Output is correct
8 Correct 456 ms 80484 KB Output is correct
# Verdict Execution time Memory Grader output
1 Runtime error 2259 ms 129356 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 913 ms 74768 KB Output is correct
2 Correct 833 ms 74772 KB Output is correct
3 Correct 836 ms 75164 KB Output is correct
4 Correct 369 ms 64340 KB Output is correct
5 Correct 829 ms 79124 KB Output is correct
6 Correct 1006 ms 76880 KB Output is correct
7 Correct 1026 ms 74768 KB Output is correct
8 Correct 936 ms 74768 KB Output is correct
9 Correct 333 ms 62500 KB Output is correct
10 Correct 716 ms 80484 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 3126 ms 131072 KB Output is correct
2 Correct 1706 ms 101896 KB Output is correct
3 Correct 2886 ms 131072 KB Output is correct
4 Correct 729 ms 75956 KB Output is correct
5 Runtime error 2619 ms 129360 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -