QOJ.ac

QOJ

The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#393846	#8546. Min or Max 2	WrongAnswer_90	WA	176ms	11828kb	C++20	10.7kb	2024-04-19 14:56:44	2024-04-19 14:56:44

Judging History

This is the latest submission verdict.

[2024-04-19 14:56:44]
Judged

Verdict: WA
Time: 176ms
Memory: 11828kb

Show

[2024-04-19 14:56:44]
Submitted

answer

#include<bits/stdc++.h>
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define ll long long
#define lll __int128
#define fi first
#define se second
#define e emplace
#define eb emplace_back
#define db double
#define ef emplace_front
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi vector<int>
#define vp vector<pii>
#define mp make_pair

//#define LOCALJUDGE
//#define int ll
bool ST;
static const ll MOD=998244353,Phi=998244352,inv2=499122177,Root=3,iRoot=332748118;
static const ll inf=1073741823,INF=4557430888798830399;
static const double eps=1e-10,pi=3.1415926535;
char in[1<<20],*p1=in,*p2=in;
using namespace std;
//#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
struct tup{int x,y;ll z;tup(int X=0,int Y=0,ll Z=0){x=X,y=Y,z=Z;}};
namespace FastIO
{
	template<typename T> inline void write(T x,char ch=' ')
	{
		if(is_same<char,T>::value)putchar(x);
		else
		{
			if(x<0)x=-x,putchar('-');
			static char st[25];int top=0;
			do{st[top++]=x%10+'0',x/=10;}while(x);
			while(top)putchar(st[--top]);
		}
		ch!='~'?putchar(ch):0;
	}
	inline void write(const char*x,char ch=' ')
	{
		for(int i=0;x[i]!='\0';++i)putchar(x[i]);
		ch!='~'?putchar(ch):0;
	}
	inline void read(char&s){do s=getchar();while(s=='\n'||s==' ');}
	inline void read(char s[])
	{
		int len=0;char st;
		do st=getchar();while(st=='\n'||st==' ');
		s[++len]=st,st=getchar();
		while(st!='\n'&&st!=' ')s[++len]=st,st=getchar();
		s[++len]='\0';
	}
	template<typename T> inline void read(T &s)
	{
		s=0;char ch=getchar();
		while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
		bool tf=(ch=='-')&&(ch=getchar());
		while((ch>='0')&&(ch<='9'))s=(s<<1)+(s<<3)+ch-'0',ch=getchar();
		s=(tf?-s:s);
	}
	template<typename T1,typename T2> inline void read(pair<T1,T2> &s){read(s.fi),read(s.se);}
	template<typename T,typename...Args> inline void write(T x,Args...args){write(x,'~'),write(args...);}
	template<typename T,typename...Args> inline void read(T&x,Args&...args){read(x),read(args...);}
}
using namespace FastIO;
namespace MTool
{
	inline int Cadd(int a,int b){return a+b>=MOD?a+b-MOD:a+b;}
	inline int Cdel(int a,int b){return a-b<0?a-b+MOD:a-b;}
	inline int Cmul(int a,int b){return 1ll*a*b%MOD;}
	inline int sqr(int a){return 1ll*a*a%MOD;}
	inline void Madd(int&a,int b){a=(a+b>=MOD?a+b-MOD:a+b);}
	inline void Mdel(int&a,int b){a=(a-b<0?a-b+MOD:a-b);}
	inline void Mmul(int&a,int b){a=1ll*a*b%MOD;}
	template<typename T> inline bool Mmax(T&a,T b){return a<b?a=b,1:0;}
	template<typename T> inline bool Mmin(T&a,T b){return a>b?a=b,1:0;}
	template<typename...Args> inline void Madd(int&a,int b,Args...args){Madd(a,b),Madd(a,args...);}
	template<typename...Args> inline void Mmul(int&a,int b,Args...args){Mmul(a,b),Mmul(a,args...);}
	template<typename...Args> inline void Mdel(int&a,int b,Args...args){Mdel(a,b),Mdel(a,args...);}
	template<typename...Args> inline int Cadd(int a,int b,Args...args){return Cadd(Cadd(a,b),args...);}
	template<typename...Args> inline int Cmul(int a,int b,Args...args){return Cmul(Cmul(a,b),args...);}
	template<typename...Args> inline int Cdel(int a,int b,Args...args){return Cdel(Cdel(a,b),args...);}
	template<typename...Args,typename T> inline bool Mmax(T&a,T b,Args...args){return Mmax(a,b)|Mmax(a,args...);}
	template<typename...Args,typename T> inline bool Mmin(T&a,T b,Args...args){return Mmin(a,b)|Mmin(a,args...);}
	inline int power(int x,ll y){int s=1;for(;y;y>>=1,Mmul(x,x))if(y&1)Mmul(s,x);return s;}
}
using namespace MTool;
namespace WrongAnswer_90
{
	int T,n,maxa[500010],maxb[500010],mina[500010],minb[500010],pre1[500010],pre2[500010];
	int a1[500010],a2[500010],pre1ck[500010],pre2ck[500010],ans[500010];
	tup a[500010];
	inline bool cmp1(tup t1,tup t2){return t1.x>t2.x;}
	inline bool cmp2(tup t1,tup t2){return t1.z<t2.z;}
	namespace Segment
	{
		#define ls(p) (t[p].l+t[p].r)
		#define rs(p) (ls(p)^1)
		struct{int l,r,x,y,maxn,minn;}t[1000010];
		inline void update(int p)
		{
			t[p].x=min(t[ls(p)].x,t[rs(p)].x);
			t[p].y=max(t[ls(p)].y,t[rs(p)].y);
			t[p].maxn=max(t[ls(p)].maxn,t[rs(p)].maxn);
			t[p].minn=min(t[ls(p)].minn,t[rs(p)].minn);
		}
		void build(int p,int l,int r)
		{
			t[p].l=l,t[p].r=r;
			if(l==r)return t[p].x=inf,t[p].y=a[l].y,t[p].maxn=-inf,t[p].minn=inf,void();
			int mid=l+((r-l)>>1);
			build(ls(p),l,mid),build(rs(p),mid+1,r),update(p);
		}
		void change(int p,int x,int y)
		{
			if(t[p].l==t[p].r)return t[p].y=-inf,t[p].x=y,t[p].maxn=t[p].minn=y,void();
			if(x<=t[ls(p)].r)change(ls(p),x,y);
			else change(rs(p),x,y);
			update(p);
		}
		int find(int p,int maxn=-inf,int minn=inf)
		{
			if(t[p].l==t[p].r)
			return t[p].l;
			if(min(t[rs(p)].x,minn)<max(t[rs(p)].y,maxn))
			return find(rs(p),maxn,minn);
			return find(ls(p),max(t[rs(p)].y,maxn),min(t[rs(p)].x,minn));
		}
		pii ask(int p,int x)
		{
			if(x<=t[p].l)return mp(t[p].x,t[p].y);
			if(x>t[ls(p)].r)return ask(rs(p),x);
			pii v=ask(ls(p),x);
			return mp(min(v.fi,t[rs(p)].x),max(v.se,t[rs(p)].y));
		}
		pii query(int p,int x)
		{
			if(t[p].l==t[p].r)return mp(t[p].x,t[p].y);
			if(x<=t[ls(p)].r)return query(ls(p),x);
			return query(rs(p),x);
		}
		int find1(int p,int x,int lim)
		{
			if(x>=t[p].r)
			{
				if(t[p].maxn<lim)return 0;
				if(t[p].l==t[p].r)return t[p].l;
				if(t[rs(p)].maxn>lim)return find1(rs(p),x,lim);
				return find1(ls(p),x,lim);
			}
			if(x<=t[ls(p)].r)return find1(ls(p),x,lim);
			int v=find1(rs(p),x,lim);
			if(v)return v;
			return find1(ls(p),x,lim);
		}
		int find2(int p,int x,int lim)
		{
			if(x>=t[p].r)
			{
				if(t[p].minn>lim)return 0;
				if(t[p].l==t[p].r)return t[p].l;
				if(t[rs(p)].minn<lim)return find2(rs(p),x,lim);
				return find2(ls(p),x,lim);
			}
			if(x<=t[ls(p)].r)return find2(ls(p),x,lim);
			int v=find2(rs(p),x,lim);
			if(v)return v;
			return find2(ls(p),x,lim);
		}
		int asky(int p,int x)
		{
			if(x<=t[p].l)return t[p].y;
			if(x>t[ls(p)].r)return asky(rs(p),x);
			return max(asky(ls(p),x),t[rs(p)].y);
		}
		int askx(int p,int x)
		{
			if(x<=t[p].l)return t[p].x;
			if(x>t[ls(p)].r)return askx(rs(p),x);
			return min(askx(ls(p),x),t[rs(p)].x);
		}
	}
	using namespace Segment;
	inline void mian()
	{
		read(T),mina[0]=minb[0]=inf,maxa[0]=maxb[0]=-inf;
		while(T--)
		{
			read(n);
			for(int i=0;i<=n;++i)ans[i]=0;
			for(int i=1;i<=n;++i)read(a[i].x),maxa[i]=max(maxa[i-1],a[i].x),mina[i]=min(mina[i-1],a[i].x);
			for(int i=1;i<=n;++i)read(a[i].y),maxb[i]=max(maxb[i-1],a[i].y),minb[i]=min(minb[i-1],a[i].y),a[i].z=i;
			build(1,1,n),sort(a+1,a+1+n,cmp1);
			for(int i=1;i<=n;change(1,a[i].z,a[i].y),++i)
			{
				if(a[i].z==n){a1[a[i].z]=a2[a[i].z]=-1;continue;}
				pii p=ask(1,a[i].z+1);
				if(p.fi>p.se)
				{
					a1[a[i].z]=p.fi,a2[a[i].z]=p.se;
					if(a[i].z-1)
					pre2[a[i].z]=find2(1,a[i].z-1,a2[a[i].z]),
					pre1ck[a[i].z]=find2(1,a[i].z-1,a1[a[i].z]);
				}
				else
				{
					int v=find(1);
					p=query(1,v);
					a1[a[i].z]=-1;
					if(p.fi==inf)a2[a[i].z]=askx(1,v);
					else a2[a[i].z]=asky(1,v);
				}
			}
			build(1,1,n);
			for(int i=n;i>=1;change(1,a[i].z,a[i].y),--i)
			if(a1[a[i].z]!=-1&&a[i].z>1)
			pre1[a[i].z]=find1(1,a[i].z-1,a1[a[i].z]),
			pre2ck[a[i].z]=find2(1,a[i].z-1,a2[a[i].z]);
//			for(int i=1;i<=n;++i)write(a1[i],' ',a2[i],'\n');
//			for(int i=1;i<=n;++i)write(pre1[i]);puts("");
//			for(int i=1;i<=n;++i)write(pre2[i]);puts("");
			sort(a+1,a+1+n,cmp2),a1[n]=inf,a2[n]=-inf;
			for(int i=1;i<=n;++i)
			{
				if(a1[i]==-1&&i!=n){++ans[abs(a[i].x-a2[i])];continue;}
				if(a1[i]>a[i].y&&a[i].y>a2[i])
				{
					int flag=0;
					if(i==1||(mina[i-1]<a[i].x&&minb[i-1]<a[i].y))flag=1;
					if(i==1||(maxa[i-1]>a[i].x&&maxb[i-1]>a[i].y))flag=1;
					if(flag)++ans[abs(a[i].x-a[i].y)];
				}
				if(i==n)break;
				int flag1=0,flag2=0;
				if(a[i].y>a1[i])
				{
					if(i==1||mina[i-1]<a[i].x)flag1=1;
					if(i==1||(maxa[i-1]>a[i].x&&maxb[i-1]>a1[i]))flag1=1;
				}
				else
				{
					if(pre1ck[i]<pre1[i]&&(maxb[pre1[i]-1]>a1[i]||mina[pre1[i]-1]<a[i].x))flag1=1;
				}
				if(a[i].y<a2[i])
				{
					if(i==1||(mina[i-1]<a[i].x&&minb[i-1]<a2[i]))flag2=1;
					if(i==1||(maxa[i-1]>a[i].x))flag2=1;
				}
				else
				{
					if(pre2ck[i]<pre2[i]&&(maxa[pre2[i]-1]>a[i].x||minb[pre2[i]-1]<a2[i]))
					flag2=1;
				}
				if(flag1)++ans[abs(a[i].x-a1[i])];
				if(flag2)++ans[abs(a[i].x-a2[i])];
			}
//			for(int i=0;i<n;++i)write(ans[i]);puts("");
			
			for(int i=1;i<=n;++i)swap(a[i].x,a[i].y),maxa[i]=max(maxa[i-1],a[i].x),mina[i]=min(mina[i-1],a[i].x);
			for(int i=1;i<=n;++i)maxb[i]=max(maxb[i-1],a[i].y),minb[i]=min(minb[i-1],a[i].y),a[i].z=i;
			build(1,1,n),sort(a+1,a+1+n,cmp1);
			for(int i=1;i<=n;change(1,a[i].z,a[i].y),++i)
			{
				if(a[i].z==n){a1[a[i].z]=a2[a[i].z]=-1;continue;}
				pii p=ask(1,a[i].z+1);
				if(p.fi>p.se)
				{
					a1[a[i].z]=p.fi,a2[a[i].z]=p.se;
					if(a[i].z-1)
					pre2[a[i].z]=find2(1,a[i].z-1,a2[a[i].z]),
					pre1ck[a[i].z]=find2(1,a[i].z-1,a1[a[i].z]);
				}
				else
				{
					int v=find(1);
					p=query(1,v);
					a1[a[i].z]=-1;
					if(p.fi==inf)a2[a[i].z]=askx(1,v);
					else a2[a[i].z]=asky(1,v);
				}
			}
			build(1,1,n);
			for(int i=n;i>=1;change(1,a[i].z,a[i].y),--i)
			if(a1[a[i].z]!=-1&&a[i].z>1)
			pre1[a[i].z]=find1(1,a[i].z-1,a1[a[i].z]),
			pre2ck[a[i].z]=find2(1,a[i].z-1,a2[a[i].z]);
//			for(int i=1;i<=n;++i)write(a1[i],' ',a2[i],'\n');
//			for(int i=1;i<=n;++i)write(pre1[i]);puts("");
//			for(int i=1;i<=n;++i)write(pre2[i]);puts("");
			sort(a+1,a+1+n,cmp2);
			for(int i=1;i<n;++i)
			{
				if(a1[i]==-1){++ans[abs(a[i].x-a2[i])];continue;}
				int flag1=0,flag2=0;
				if(a[i].y>a1[i])
				{
					if(i==1||mina[i-1]<a[i].x)flag1=1;
					if(i==1||(maxa[i-1]>a[i].x&&maxb[i-1]>a1[i]))flag1=1;
				}
				else
				{
					if(pre1ck[i]<pre1[i]&&(maxb[pre1[i]-1]>a1[i]||mina[pre1[i]-1]<a[i].x))flag1=1;
				}
				if(a[i].y<a2[i])
				{
					if(i==1||(mina[i-1]<a[i].x&&minb[i-1]<a2[i]))flag2=1;
					if(i==1||maxa[i-1]>a[i].x)flag2=1;
				}
				else
				{
					if(pre2ck[i]<pre2[i]&&(maxa[pre2[i]-1]>a[i].x||minb[pre2[i]-1]<a2[i]))
					flag2=1;
				}
				if(flag1)++ans[abs(a[i].x-a1[i])];
				if(flag2)++ans[abs(a[i].x-a2[i])];
			}
			for(int i=0;i<n;++i)write(ans[i]);puts("");
		}
	}
}
bool ED;
signed main()
{
	#ifdef LOCALJUDGE
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	#endif 
	double st=clock();
	WrongAnswer_90::mian();
	double ed=clock();
	#ifndef LOCALJUDGE
 	cerr<<endl;
	#endif
 	cerr<<"Time: "<<ed-st<<" ms\n";
	#ifdef LOCALJUDGE
 	cerr<<"     ";
	#endif
 	cerr<<"Memory: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB\n";
	return 0;
}

Source code, Language: C++20

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 11828kb

input:

4
2
1 2
2 1
5
2 4 1 5 3
2 4 1 5 3
5
1 2 3 4 5
5 4 3 2 1
8
5 8 3 4 2 7 1 6
4 6 3 8 5 1 2 7

output:

2 0 
5 0 0 0 0 
2 2 2 2 0 
5 5 2 2 1 0 0 0

result:

ok 20 numbers

Test #2:

score: -100

Wrong Answer

time: 176ms

memory: 11788kb

input:

66664
7
4 2 6 5 7 1 3
6 5 3 1 4 7 2
10
6 8 10 7 5 1 4 3 9 2
5 10 3 8 6 7 2 9 1 4
9
3 2 4 8 7 6 9 1 5
8 1 2 9 6 7 4 3 5
10
4 3 9 6 7 2 10 1 8 5
3 5 4 1 2 7 10 9 6 8
5
3 4 1 2 5
5 1 3 2 4
5
2 4 3 5 1
2 3 1 4 5
6
2 6 1 3 4 5
6 4 5 1 3 2
10
10 1 2 7 5 8 4 3 9 6
9 4 2 3 6 1 7 8 5 10
5
1 2 4 5 3
4 1 2 5 3...

output:

4 4 2 2 1 0 0 
5 6 3 2 2 1 0 0 0 0 
4 6 3 2 1 0 0 0 0 
4 4 4 3 2 1 0 0 0 0 
4 3 0 0 0 
2 2 2 2 0 
3 3 3 1 0 0 
5 7 4 2 1 0 0 0 0 0 
4 2 0 0 0 
6 3 0 0 0 0 
3 3 2 0 0 
5 4 2 1 0 0 0 
3 2 3 1 0 0 
4 6 3 0 0 0 0 
3 4 3 2 1 0 0 
3 2 2 2 2 2 2 1 0 
4 5 3 1 0 0 0 
3 4 3 2 3 3 1 0 0 0 
7 5 0 0 0 0 0 0 
6 8...

result:

wrong answer 18th numbers differ - expected: '5', found: '4'