Submission #95353

#	Time	Username	Problem	Language	Result	Execution time	Memory
95353		Retro3014	절취선 (JOI14_ho_t5)	C++17	100 / 100	628 ms	64748 KiB

2014_ho_t5

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>

using namespace std;
typedef long long ll;
#define MAX_N 100000

int W, H, N;
struct LINE{
	LINE (int idx, int x, int y1, int y2) : idx(idx), x(x), y1(y1), y2(y2) {}
	int idx, x;
	int y1, y2;
	bool operator <(const LINE &a)const{
		return x<a.x;
	}};
vector<LINE> line;
struct POINT{
	POINT (int idx, int x, int y, int z) : idx(idx), x(x), y(y), z(z) {}
	int idx, x, y, z;
	bool operator <(const POINT &a)const{
		if(x==a.x){
			return z<a.z;
		}
		return x<a.x;
	}};
vector<POINT> p;

struct SEG{
	SEG (int l, int r, int sum) : l(l), r(r), sum(sum) {}
	int l, r;
	int sum;
};
vector<SEG> seg1;


ll ans = 0;

int sum11(int idx, int s, int e, int x, int y){
	if(idx==-1)	return 0;
	if(x<=s && e<=y)	return seg1[idx].sum;
	if(x>e || y<s)	return 0;
	return sum11(seg1[idx].l, s, (s+e)/2, x, y) + sum11(seg1[idx].r, (s+e)/2+1, e, x, y);
}

void update11(int idx, int s, int e, int x, int y){
	seg1[idx].sum+=y;
	if(s==e)	return;
	if(x<=(s+e)/2){
		if(seg1[idx].l==-1){
			seg1[idx].l = seg1.size(); seg1.push_back({-1, -1, 0});
		}
		update11(seg1[idx].l, s, (s+e)/2, x, y);
	}else{
		if(seg1[idx].r==-1){
			seg1[idx].r = seg1.size(); seg1.push_back({-1, -1, 0});
		}
		update11(seg1[idx].r, (s+e)/2+1, e, x, y);
	}
}

struct SEG2{
	SEG2(int l, int r, int group, int sum, int lazy) : l(l), r(r), sum(sum), lazy(lazy) {}
	int l, r;
	int group, sum, lazy;
};

vector<SEG2> seg2;


int group[MAX_N+50];
int g[MAX_N+50];

int find_g(int x){
	if(x==group[x])	return x;
	return group[x] = find_g(group[x]);
}

void union_g(int x, int y){
	x = find_g(x); y = find_g(y);
	group[x] = y;
}

void calc(int idx){
	if(idx==-1)	return;
	if(seg2[idx].sum==0){
		seg2[idx].lazy = seg2[idx].group = -1;
		return;
	}
	if(seg2[idx].lazy!=-1){
		if(seg2[idx].l!=-1){
			if(seg2[seg2[idx].l].sum==0){
				seg2[seg2[idx].l].lazy = seg2[seg2[idx].l].group = -1;
			}else if(seg2[seg2[idx].l].group==-1){
				seg2[seg2[idx].l].group = seg2[idx].lazy;
				seg2[seg2[idx].l].lazy = seg2[idx].lazy;
			}else{
				union_g(seg2[seg2[idx].l].group, seg2[idx].lazy);
				seg2[seg2[idx].l].group = seg2[idx].lazy;
				seg2[seg2[idx].l].lazy = seg2[idx].lazy;
			}
		}if(seg2[idx].r!=-1){
			if(seg2[seg2[idx].r].sum==0){
				seg2[seg2[idx].r].lazy = seg2[seg2[idx].r].group = -1;
			}else if(seg2[seg2[idx].r].group==-1){
				seg2[seg2[idx].r].group = seg2[idx].lazy;
				seg2[seg2[idx].r].lazy = seg2[idx].lazy;
			}else{
				union_g(seg2[seg2[idx].r].group, seg2[idx].lazy);
				seg2[seg2[idx].r].group = seg2[idx].lazy;
				seg2[seg2[idx].r].lazy = seg2[idx].lazy;
			}
		}
		seg2[idx].lazy = -1;
	}
}


void lazy22(int idx, int s, int e, int x, int y, int z){
	if(idx==-1)		return;
	if(seg2[idx].sum==0)	return;
	calc(idx);
	if(x<=s && e<=y)	{
		seg2[idx].lazy = z;
		if(seg2[idx].group!=-1)	union_g(seg2[idx].group, z);
		seg2[idx].group = z;
		return;
	}
	if(x>e || y<s)	return;
	lazy22(seg2[idx].l, s, (s+e)/2, x, y, z);
	lazy22(seg2[idx].r, (s+e)/2+1, e, x, y, z);
}

void update22(int idx, int s, int e, int x, int y){
	calc(idx);
	seg2[idx].sum++;
	seg2[idx].group = -1;
	if(s==e){
		seg2[idx].group = y;
		return;
	}
	if(x<=(s+e)/2){
		if(seg2[idx].l==-1){
			seg2[idx].l = seg2.size(); seg2.push_back({-1, -1, -1, 0, -1});
		}
		update22(seg2[idx].l, s, (s+e)/2, x, y);
	}else{
		if(seg2[idx].r==-1){
			seg2[idx].r = seg2.size(); seg2.push_back({-1, -1, -1, 0, -1});
		}
		update22(seg2[idx].r, (s+e)/2+1, e, x, y);
	}
}

int find22(int idx, int s, int e, int k){
	calc(idx);
	seg2[idx].sum--;
	if(s==e){
		int ret = seg2[idx].group;
		return seg2[idx].group;
	}
	if(k<=(s+e)/2){
		return find22(seg2[idx].l, s, (s+e)/2, k);
	}else{
		return find22(seg2[idx].r, (s+e)/2+1, e, k);
	}
}

int sum1(int x, int y)	{return sum11(0, 0, H, x, y);}
void update1(int x, int y)	{update11(0, 0, H, x, y);}
void lazy2(int x, int y, int z)	{lazy22(0, 0, H, x, y, z);}
void update2(int x, int y)	{update22(0, 0, H, x, y);}
int find2(int x)	{return find22(0, 0, H, x);}

int main(){
	scanf("%d%d%d", &W, &H, &N);
	for(int i=0; i<N+4; i++)	group[i] = i;
	seg1.push_back({-1, -1, 0});
	seg2.push_back({-1, -1, -1, 0, -1});
	for(int i=0; i<N; i++){
		int a, b, c, d;
		scanf("%d%d%d%d", &a, &b, &c, &d);
		if(a==c){
			line.push_back({i, a, b, d});
		}else{
			p.push_back({i, a, b, 1}); p.push_back({i, c+1, b, -1});
		}
	}
	ans-=(N+4);
	p.push_back({N, 0, 0, 1}); p.push_back({N+1, 0, H, 1});
	p.push_back({N, W+1, 0, -1}); p.push_back({N+1, W+1, H, -1});
	line.push_back({N+2, 0, 0, H}); line.push_back({N+3, W, 0, H});
	sort(p.begin(), p.end()); sort(line.begin(), line.end());
	int idx = 0;
	for(int i=0; i<line.size(); i++){
		while(idx<p.size() && p[idx].x<=line[i].x){
			POINT now = p[idx]; idx++;
			//cout<<'*'<<now.x<<' '<<now.y<<' '<<now.z<<endl;
			update1(now.y, now.z);
			if(now.z==1)	update2(now.y, now.idx);
			else {
				g[now.idx] = find2(now.y);
				//cout<<now.idx<<' '<<g[now.idx]<<endl;
			}
		}
		int tmp = sum1(line[i].y1, line[i].y2);
		lazy2(line[i].y1, line[i].y2, line[i].idx);
		//cout<<'&'<<line[i].x<<' '<<line[i].y1<<' '<<line[i].y2<<' '<<tmp<<endl;
		ans+=(ll)tmp;
	}
	while(idx<p.size()){
		POINT now = p[idx]; idx++;
		//cout<<'*'<<now.x<<' '<<now.y<<' '<<now.z<<endl;
		update1(now.y, now.z);
		if(now.z==1)	update2(now.y, now.idx);
		else {
			g[now.idx] = find2(now.y);
			//cout<<now.idx<<' '<<g[now.idx]<<endl;
		}
	}
	//cout<<ans;
	for(int i=0; i<N+4; i++){
		//cout<<find_g(i)<<endl;
		if(find_g(i)==i){
			ans++;
		}
	}
	printf("%lld", ans);
}

Compilation message (stderr)

2014_ho_t5.cpp: In function 'int find22(int, int, int, int)':
2014_ho_t5.cpp:160:7: warning: unused variable 'ret' [-Wunused-variable]
   int ret = seg2[idx].group;
       ^~~
2014_ho_t5.cpp: In function 'int main()':
2014_ho_t5.cpp:196:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<line.size(); i++){
               ~^~~~~~~~~~~~
2014_ho_t5.cpp:197:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(idx<p.size() && p[idx].x<=line[i].x){
         ~~~^~~~~~~~~
2014_ho_t5.cpp:212:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(idx<p.size()){
        ~~~^~~~~~~~~
2014_ho_t5.cpp:177:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &W, &H, &N);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
2014_ho_t5.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &a, &b, &c, &d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 50 / 50