Comparar texto

Encuentra la diferencia entre dos archivos de texto

Editor live

Ocultar sin cambios

Sin ajuste de línea

Vista

Nivel de detalle

Resaltado de sintaxis

Diffchecker Desktop La forma más segura de usar Diffchecker. ¡Obtén la app de Diffchecker Desktop: tus diffs nunca salen de tu computadora!Obtener Desktop

【USACO 2022FEB P】Paint by Rectangles

Creado hace 2 añosEl diff nunca expira

Los dos textos son idénticos

No hay diferencia entre estos dos textos

0 eliminaciones

Líneas
Total
Eliminado

Caracteres
Total
Eliminado

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

105 líneas

0 adiciones

Líneas
Total
Añadido

Caracteres
Total
Añadido

Para continuar usando esta función, actualice a Diffchecker Pro Ver precios

105 líneas

#include<bits/stdc++.h>

using namespace std;

#define F(i,a,b) for(int i=a;i<=b;i++)

#define Fd(i,a,b) for(int i=a;i>=b;i--)

#define LL long long

#define N 200010

LL X,C,F,B;

int n,T,L[N],R[N],op[N],f[N],col[N];

struct node{int lx,ly,rx,ry;}a[N];

int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}

void merge(int x,int y){int A=find(x),B=find(y);if(A!=B)f[A]=B;}

struct tree{

#define ls x<<1

#define rs (x<<1)|1

int tag[N*4],sum[N*4];

void pushdown(int x){

if(!tag[x])return;

if(sum[ls]){

if(!tag[ls])tag[ls]=tag[x];

else merge(tag[ls],tag[x]);

}

if(sum[rs]){

if(!tag[rs])tag[rs]=tag[x];

else merge(tag[rs],tag[x]);

}

tag[x]=0;

}

void pushup(int x){sum[x]=sum[ls]+sum[rs];}

void modify(int x,int l,int r,int ll,int rr,int pos){

if(r<ll||l>rr)return;

if(l>=ll&&r<=rr){

if(!sum[x])return;

if(!tag[x])tag[x]=pos;

else merge(tag[x],pos);

return;

}

int mid=l+r>>1;

pushdown(x);

modify(ls,l,mid,ll,rr,pos);modify(rs,mid+1,r,ll,rr,pos);

pushup(x);

}

void change(int x,int l,int r,int k,int pos){

if(l==r){

if(k==1)sum[x]++;

else sum[x]--,tag[x]=0;

return;

}

int mid=l+r>>1;

pushdown(x);

pos<=mid?change(ls,l,mid,k,pos):change(rs,mid+1,r,k,pos);

pushup(x);

}

int query(int x,int l,int r,int ll,int rr){

if(r<ll||l>rr)return 0;

if(l>=ll&&r<=rr)return sum[x];

int mid=l+r>>1;

return query(ls,l,mid,ll,rr)+query(rs,mid+1,r,ll,rr);

}

}t;

vector<int>S[N];

int main(){

scanf("%d%d",&n,&T);

F(i,1,n){

f[i]=i;

scanf("%d%d%d%d",&a[i].lx,&a[i].ly,&a[i].rx,&a[i].ry);

op[a[i].lx]=i;op[a[i].rx]=-i;

L[a[i].lx]=L[a[i].rx]=a[i].ly;R[a[i].lx]=R[a[i].rx]=a[i].ry;

}

F(i,1,2*n){

if(op[i]>0){

t.change(1,1,n*2,1,L[i]);t.change(1,1,n*2,1,R[i]);

t.modify(1,1,n*2,L[i],R[i],op[i]);

int q=t.query(1,1,n*2,L[i]+1,R[i]-1),d=t.query(1,1,n*2,1,L[i]-1)+1;

d&1?B+=(q>>1)+1:B+=q+1>>1;

X+=q;

col[i]=d&1;

}else{

t.change(1,1,n*2,-1,L[i]);t.change(1,1,n*2,-1,R[i]);

t.modify(1,1,n*2,L[i],R[i],-op[i]);

int q=t.query(1,1,n*2,L[i]+1,R[i]-1);

int u=t.query(1,1,n*2,R[i]+1,n*2)+1,d=t.query(1,1,n*2,1,L[i]-1)+1;

// Black 1,White 0

if((d&1)&&(u&1))B+=q>>1;

else if(!(d&1)&&!(u&1))B+=(q>>1)-1;

else B+=(q+1>>1)-1;

X+=q;

}

F(i,1,n){if(find(i)==i)C++;S[find(i)].push_back(a[i].lx);}

F(i,1,n)if(find(i)==i){

int tx=n*2+1,pos;

for(auto d:S[i])if(d<tx)tx=d,pos=d;

if(!col[pos])B++;

}

F=X+C+1;

if(T==1)printf("%lld",F);

else printf("%lld %lld",F-B,B);

return 0;

}

Diferencias guardadas

Texto original

Abrir archivo

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 200010

LL X,C,F,B;
int n,T,L[N],R[N],op[N],f[N],col[N];
struct node{int lx,ly,rx,ry;}a[N];

int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}

void merge(int x,int y){int A=find(x),B=find(y);if(A!=B)f[A]=B;}

struct tree{
	#define ls x<<1
	#define rs (x<<1)|1
	int tag[N*4],sum[N*4];
	void pushdown(int x){
		if(!tag[x])return;
		if(sum[ls]){
			if(!tag[ls])tag[ls]=tag[x];
			else merge(tag[ls],tag[x]);
		}
		if(sum[rs]){
			if(!tag[rs])tag[rs]=tag[x];
			else merge(tag[rs],tag[x]);
		}
		tag[x]=0;
	}
	void pushup(int x){sum[x]=sum[ls]+sum[rs];}
	void modify(int x,int l,int r,int ll,int rr,int pos){
		if(r<ll||l>rr)return;
		if(l>=ll&&r<=rr){
			if(!sum[x])return;
			if(!tag[x])tag[x]=pos;
			else merge(tag[x],pos);
			return;
		}
		int mid=l+r>>1;
		pushdown(x);
		modify(ls,l,mid,ll,rr,pos);modify(rs,mid+1,r,ll,rr,pos);
		pushup(x);
	}
	void change(int x,int l,int r,int k,int pos){
		if(l==r){
			if(k==1)sum[x]++;
			else sum[x]--,tag[x]=0;
			return;
		}
		int mid=l+r>>1;
		pushdown(x);
		pos<=mid?change(ls,l,mid,k,pos):change(rs,mid+1,r,k,pos);
		pushup(x);
	}
	int query(int x,int l,int r,int ll,int rr){
		if(r<ll||l>rr)return 0;
		if(l>=ll&&r<=rr)return sum[x];
		int mid=l+r>>1;
		return query(ls,l,mid,ll,rr)+query(rs,mid+1,r,ll,rr);
	}
}t;

vector<int>S[N];

int main(){
	scanf("%d%d",&n,&T);
	F(i,1,n){
		f[i]=i;
		scanf("%d%d%d%d",&a[i].lx,&a[i].ly,&a[i].rx,&a[i].ry);
		op[a[i].lx]=i;op[a[i].rx]=-i;
		L[a[i].lx]=L[a[i].rx]=a[i].ly;R[a[i].lx]=R[a[i].rx]=a[i].ry;
	}
	F(i,1,2*n){
		if(op[i]>0){
			t.change(1,1,n*2,1,L[i]);t.change(1,1,n*2,1,R[i]);
			t.modify(1,1,n*2,L[i],R[i],op[i]);
			int q=t.query(1,1,n*2,L[i]+1,R[i]-1),d=t.query(1,1,n*2,1,L[i]-1)+1;
			d&1?B+=(q>>1)+1:B+=q+1>>1;
			X+=q;
			col[i]=d&1;
		}else{
			t.change(1,1,n*2,-1,L[i]);t.change(1,1,n*2,-1,R[i]);
			t.modify(1,1,n*2,L[i],R[i],-op[i]);
			int q=t.query(1,1,n*2,L[i]+1,R[i]-1);
			int u=t.query(1,1,n*2,R[i]+1,n*2)+1,d=t.query(1,1,n*2,1,L[i]-1)+1;
			// Black 1,White 0
			if((d&1)&&(u&1))B+=q>>1;
			else if(!(d&1)&&!(u&1))B+=(q>>1)-1;
			else B+=(q+1>>1)-1;
			X+=q;
		}
	}
	F(i,1,n){if(find(i)==i)C++;S[find(i)].push_back(a[i].lx);}
	F(i,1,n)if(find(i)==i){
		int tx=n*2+1,pos;
		for(auto d:S[i])if(d<tx)tx=d,pos=d;
		if(!col[pos])B++;
	}
	F=X+C+1;
	if(T==1)printf("%lld",F);
	else printf("%lld %lld",F-B,B);
	return 0;
}

Texto modificado

Abrir archivo

#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define LL long long
#define N 200010

LL X,C,F,B;
int n,T,L[N],R[N],op[N],f[N],col[N];
struct node{int lx,ly,rx,ry;}a[N];

int find(int x){return f[x]==x?x:(f[x]=find(f[x]));}

void merge(int x,int y){int A=find(x),B=find(y);if(A!=B)f[A]=B;}

vector<int>S[N];