oj.uz

Submission #86671

# Submission time Handle Problem Language Result Execution time Memory
86671 2018-11-27T05:15:24 Z DifferentHeaven 도로 건설 사업 (JOI13_construction) C++17
70 / 100
 2900 ms 263168 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 read(int&)':
construction.cpp:9:39: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 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;}
                                       ^
construction.cpp: In function 'void read(long long int&)':
construction.cpp:10:45: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 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;}
                                             ^
construction.cpp: In function 'void writeln(long long int)':
construction.cpp:11:63: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 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');}
                                                               ^
construction.cpp: In function 'void write(long long int)':
construction.cpp:12:61: warning: ISO C++1z does not allow 'register' storage class specifier [-Wregister]
 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(' ');}
                                                             ^
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 39 ms 16760 KB Output is correct
2 Correct 492 ms 38992 KB Output is correct
3 Correct 498 ms 42560 KB Output is correct
4 Correct 243 ms 42560 KB Output is correct
5 Correct 495 ms 50692 KB Output is correct
6 Correct 538 ms 52452 KB Output is correct
7 Correct 143 ms 52452 KB Output is correct
8 Correct 379 ms 65544 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2590 ms 121044 KB Output is correct
2 Correct 2541 ms 132656 KB Output is correct
3 Correct 2420 ms 144240 KB Output is correct
4 Correct 2369 ms 155912 KB Output is correct
5 Correct 630 ms 155912 KB Output is correct
6 Correct 488 ms 155912 KB Output is correct
7 Correct 2482 ms 162388 KB Output is correct
8 Correct 390 ms 162388 KB Output is correct
9 Correct 397 ms 162388 KB Output is correct
10 Correct 1339 ms 162388 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 723 ms 162388 KB Output is correct
2 Correct 734 ms 162388 KB Output is correct
3 Correct 653 ms 162388 KB Output is correct
4 Correct 381 ms 162388 KB Output is correct
5 Correct 684 ms 162388 KB Output is correct
6 Correct 877 ms 162388 KB Output is correct
7 Correct 731 ms 162388 KB Output is correct
8 Correct 691 ms 162388 KB Output is correct
9 Correct 309 ms 162388 KB Output is correct
10 Correct 647 ms 162388 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2649 ms 169984 KB Output is correct
2 Correct 1518 ms 169984 KB Output is correct
3 Correct 2754 ms 197808 KB Output is correct
4 Correct 671 ms 197808 KB Output is correct
5 Correct 2691 ms 228684 KB Output is correct
6 Correct 681 ms 228684 KB Output is correct
7 Runtime error 2900 ms 263168 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
8 Halted 0 ms 0 KB -