Compare text

Find the difference between two text files

Real-time diff

Unified diff

Collapse lines

Highlight change

Syntax highlighting

Tools

Diffchecker Desktop The most secure way to run Diffchecker. Get the Diffchecker Desktop app: your diffs never leave your computer!Get Desktop

Comparing sensitive data, confidential files or internal emails?

Most legal and privacy policies prohibit uploading sensitive data online. Diffchecker Desktop ensures your confidential information never leaves your computer. Work offline and compare documents securely.

Download Diffchecker Desktop Learn more

【USACO 2022FEB P】Paint by Rectangles

Created 3 months agoDiff never expires

The two files are identical

There is no difference to show between these two files

0 removals

105 lines

0 additions

105 lines

#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;

}

Saved diffs

Original text

Open file

#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;
}

Changed text

Open file

#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];