Compare text

Find the difference between two text files

Real-time editor

Hide unchanged lines

Disable line wrap

Layout

Diff precision

Syntax highlighting

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

【USACO 2022FEB P】Paint by Rectangles

Created 2 years agoDiff never expires

The two texts are identical

There is no difference to show between these two texts

0 removals

Lines
Total
Removed

Characters
Total
Removed

To continue using this feature, upgrade to Diffchecker Pro View Pricing

105 lines

0 additions

Lines
Total
Added

Characters
Total
Added

To continue using this feature, upgrade to Diffchecker Pro View Pricing

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