QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#137363#3300. Cactus Competitionc20231020WA 4ms19980kbC++2310.0kb2023-08-10 11:15:502023-08-10 11:15:51

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-10 11:15:51]
  • 评测
  • 测评结果：WA
  • 用时：4ms
  • 内存：19980kb
查看
  • [2023-08-10 11:15:50]
  • 提交

answer

/*
膜拜传奇特级宗师 Afterglow 大神儿
今天在 florr 首页称您为大夏尊贵的大名儿
一股敬佩之情油生然而
您在 florr 为国争光，扬我大夏威名
向您献上最真挚的膜拜！！！
膜拜传奇特级宗师 Afterglow 大神儿，今，一，您，扬。向！
膜拜传奇特级宗师 Afterglow 大神儿，今，一，您，扬。向！
膜拜传奇特级宗师 Afterglow 大神儿，今，一，您，扬。向！
*/
/*
          _____                    _____                     _____                    _____
         /\    \                  /\    \                   /\    \                  /\    \
        /  \    \                /  \    \                 /  \____\                /  \    \
        \   \    \              /    \    \               /   /    /                \   \    \
         \   \    \            /      \    \             /   /    /                  \   \    \
          \   \    \          /   /\   \    \           /   /____/                    \   \    \
           \   \    \        /   /  \   \    \         /    |    |                     \   \    \
            \   \    \      /   /    \   \    \       /     |    |                      \   \    \
             \   \    \    /   /    / \   \    \     /      |    |                       \   \    \
              \   \    \  /   /    /   \   \    \   /       |____|__ _____                \   \    \
_______________\   \____\/   /____/     \   \    \ /   /|            \    \ _______________\   \____\
\                  /    /\   \    \      \   \    \\  / |    _________\____\\                  /    /
 \    ____________/____/  \   \    \      \   \____\\/__|   |    |           \    ____________/____/
  \   \    \               \   \    \     |   |    |    |   |    |            \   \    \
   \   \    \               \   \    \    |   |    |    |   |    |             \   \    \
    \   \    \               \   \    \   |   |____|    |   |    |              \   \    \
     \   \    \               \   \    \  /   /    /    \   |    |               \   \    \
      \   \    \               \   \    \/   /    /      \  |    |                \   \    \
       \   \____\               \   \___/   /    /        \ |    |                 \   \____\
        \  /    /                \         /    /          \|    |                  \  /    /
         \/____/                  \_______/____/            \____|                   \/____/
*/
#define poj
#ifndef local
#define zcz
#endif
#ifdef poj
//C++
#include<iomanip>
#include<iostream>
//C
#include<cassert>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
//STL
#include<algorithm>
#include<bitset>
#include<functional>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<vector>
//C++11
#if __cplusplus>=201103L
#include<chrono>
#include<random>
#include<unordered_set>
#include<unordered_map>
#endif
#else
#include<bits/stdc++.h>
#endif
using namespace std;
#ifdef zcz
class fastin{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *inf;
	char *inbuf,*inst,*ined;
	inline char _getchar(){
		if(inst==ined)inst=inbuf,ined=inbuf+fread(inbuf,1,MAXBF,inf);
		return inst==ined?EOF:*inst++;
	}
	public:
	fastin(FILE*_inf=stdin){
		inbuf=new char[MAXBF],inf=_inf,inst=inbuf,ined=inbuf;
	}
	~fastin(){delete inbuf;}
	template<typename Int> fastin&operator>>(Int &n){
		static char c;
		Int t=1;
		while((c=_getchar())<'0'||c>'9')if(c=='-')t=-1;
		n=(c^48);
		while((c=_getchar())>='0'&&c<='9')n=n*10+(c^48);
		n*=t;
		return *this;
	}
	fastin&operator>>(char&c){
		while((c=_getchar())<'!'||c>'~');
		return *this;
	}
	fastin&operator>>(char*s){
		int t=0;
		static char c;
		while((c=_getchar())==' '||c=='\n');
		s[t++]=c;
		while((c=_getchar())>='!'&&c<='~')s[t++]=c;
		s[t]='\0';
		return *this;
	}
}fi;
class fastout{
	private:
#ifdef poj
	static const int MAXBF=1<<20;
#else
	const int MAXBF=1<<27;
#endif
	FILE *ouf;
	char *oubuf,*oust,*oued;
	inline void _flush(){fwrite(oubuf,1,oued-oust,ouf);oued=oust;}
	inline void _putchar(char c){
		if(oued==oust+MAXBF)_flush(),oued=oubuf;
		*oued++=c;
		#ifdef local
		_flush();
		#endif
	}
	public:
	fastout(FILE*_ouf=stdout){
		oubuf=new char[MAXBF],ouf=_ouf,oust=oubuf,oued=oubuf;
	}
	~fastout(){_flush();delete oubuf;}
	template<typename Int> fastout&operator<<(Int n){
		if(n<0)_putchar('-'),n=-n;
		static char S[20];
		int t=0;
		do{S[t++]='0'+n%10,n/=10;}while(n);
		for(int i=0;i<t;++i)_putchar(S[t-i-1]);
		return *this;
	}
	fastout&operator<<(char c){_putchar(c);return *this;}
	fastout&operator<<(char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
	fastout&operator<<(const char*s){
		for(int i=0;s[i];++i)_putchar(s[i]);
		return *this;
	}
}fo;
#define cin fi
#define cout fo
#else
#define czc ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#endif
#define mod7 1000000007
#define mod9 998244353
#define ll long long
#define int ll
#define isinf 0x3f3f3f3f
#define ilinf 0x7fffffff
#define lsinf 0x3f3f3f3f3f3f3f3f
#define llinf 0x7fffffffffffffff
#define pii pair<int,int>
#define fr first
#define sc second
#define next ___
#define pb push_back
#define N 500010
#define M 5000010
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b,c) for(ll i=(a);i<=(b);i+=c)
#define Per(i,a,b,c) for(ll i=(a);i>=(b);i-=c)
#define Gra(i) for(ll i=h[x];i;i=next[i])
typedef int arr[N];
typedef int arm[M];
typedef ll arl[N];
typedef ll alm[M];
typedef double ard[N];
typedef double adm[M];
namespace modint{
	template<typename Int,Int mod,Int m1>
	struct modint{
		Int v;
		modint(){v=0;}
		modint(Int a){v=a;}
		bool operator==(modint a){return v==a.v;}
		bool operator!=(modint a){return v!=a.v;}
		bool operator<(modint a){return v<a.v;}
		bool operator>(modint a){return v>a.v;}
		bool operator<=(modint a){return v<=a.v;}
		bool operator>=(modint a){return v>=a.v;}
		bool operator==(Int a){return v==a;}
		bool operator!=(Int a){return v!=a;}
		bool operator<(Int a){return v<a;}
		bool operator>(Int a){return v>a;}
		bool operator<=(Int a){return v<=a;}
		bool operator>=(Int a){return v>=a;}
		modint operator+(modint a){return v>=mod-a.v?v-mod+a.v:v+a.v;}
		modint operator-(modint a){return v>=a.v?v-a.v:v+mod-a.v;}
		modint modnum(modint a){
			return a-((__int128(a.v)*m1)>>80)*mod;
		}
		modint operator*(modint a){return modnum(v*a.v);}
		modint operator+=(modint a){*this=*this+a;return *this;}
		modint operator-=(modint a){*this=*this-a;return *this;}
		modint operator*=(modint a){*this=*this*a;return *this;}
		modint qpow(modint a,Int b){
			modint r(1);
			for(;b;b>>=1,a*=a)if(b&1)r*=a;
			return r;
		}
		modint operator/(modint a){return qpow(a,mod-2)*v;}
		modint operator/=(modint a){*this=*this/a;return *this;}
		modint&operator++(){*this=*this+1;return *this;}
		modint&operator--(){*this=*this-1;return *this;}
		const modint operator++(int){modint r=*this;++*this;return r;}
		const modint operator--(int){modint r=*this;--*this;return r;}
		#ifdef cout
		friend fastin&operator>>(fastin&in,modint&n){in>>n.v;return in;}
		friend fastout&operator<<(fastout&out,modint n){out<<n.v;return out;}
		#else
		friend istream&operator>>(istream&in,modint&n){in>>n.v;return in;}
		friend ostream&operator<<(ostream&out,modint n){out<<n.v;return out;}
		#endif
	};
	typedef modint<long long,1000000007,1208925811152148> int7;
	typedef modint<long long,998244353,1211051999424262> int9;
}
using namespace modint;
namespace st{
	int f[N][17];
	void build(int n,int*a){
		For(i,1,n){
			f[i][0]=a[i];
		};
		For(i,1,n){
			for(int j=1;(1<<j)<=n;++j){
				f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
			}
		};
	};
	int q(int l,int r){
		int t=log2(r-l+1);
		return max(f[l][t],f[r-(1<<t)+1][t]);
	};
}
namespace seg{
	#define ls p<<1
	#define rs p<<1|1
	#define mid ((l+r)>>1)
	int sum[N<<2],la[N<<2];
	void up(int p,int l,int r){
		sum[p]=la[p]?r-l+1:sum[ls]+sum[rs];
	};
	void ch(int p,int l,int r,int L,int R,int v){
		if(L<=l&&r<=R){
			la[p]+=v;
			up(p,l,r);
			return;
		}
		if(L<=mid)ch(ls,l,mid,L,R,v);
		if(R>mid)ch(rs,mid+1,r,L,R,v);
		up(p,l,r);
	};
	#undef mid
}
struct G{
	int x,l,r,v;
};
vector<G>op;
void add(int l,int r,int L,int R){
	if(l>r||L>R)return;
	op.pb({l,L,R,1});
	op.pb({r+1,L,R,-1});
}
int n,m;
arr a,b,pn,px,sn,sx;
void solve(){
	cin>>n>>m;
	For(i,1,n){
		cin>>a[i];
		add(i,i,1,i-1);
	};
	st::build(n,a);
	pn[0]=sn[m+1]=isinf;
	px[0]=sx[m+1]=-isinf;
	For(i,1,m){
		cin>>b[i];
		px[i]=max(px[i-1],b[i]);
		pn[i]=min(pn[i-1],b[i]);
	};
	Per(i,m,1,1){
		sx[i]=max(sx[i+1],b[i]);
		sn[i]=min(sn[i+1],b[i]);
	};
	For(i,1,n){
		if(a[i]+px[m]<0){
			add(1,i,i,n);
		}
	};
	For(i,1,m){
		if(b[i]==pn[m]){
			int l=1,r=1;
			while(l<=n){
				while(r<=n&&a[r]+b[i]<0)++r;
				add(l,r-1,l,r-1);
				l=++r;
			}
			break;
		}
	};
	For(i,1,n){
		int l=1,r=m,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(a[i]+px[mid]<0){
				ans=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		if(!ans)continue;
		l=1,r=i;
		int an=i;
		while(l<=r){
			int mid=(l+r)>>1;
			if(pn[ans]+st::q(mid,i)<0){
				an=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		add(an,i,an,n);
	};
	For(i,1,n){
		int l=1,r=m,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(a[i]+sx[mid]<0){
				ans=mid;
				r=mid-1;
			}else{
				l=mid+1;
			}
		}
		if(!ans)continue;
		l=i,r=n;
		int an=i;
		while(l<=r){
			int mid=(l+r)>>1;
			if(sn[ans]+st::q(i,mid)<0){
				an=mid;
				l=mid+1;
			}else{
				r=mid-1;
			}
		}
		add(1,an,i,an);
	};
	sort(op.begin(),op.end(),[](G x,G y){
		return x.x<y.x;
	});
	ll ans=0;
	For(i,0,(int)op.size()-1){
		if(i)ans+=1ll*(op[i].x-op[i-1].x)*seg::sum[1];
		seg::ch(1,1,n,op[i].l,op[i].r,op[i].v);
	};
	cout<<1ll*n*n-ans<<'\n';
	return;
}
#undef int
int main(){
	#ifndef zcz
	czc;
	#endif
	int t=1;
	while(t--)solve();
	return 0;
}
源文件, 语言: C++23

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 19896kb

input:

3 3
-1 0 1
-1 0 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 4ms
memory: 19868kb

input:

3 3
-1 0 1
1 0 1

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 1ms
memory: 19952kb

input:

10 10
145195799 312862766 143966779 -11056226 -503624929 636383890 -182650312 -382759112 -290767690 377894950
-845235881 -418232930 -600566938 -957917357 -181139226 125255273 -175406945 740226783 -750456842 325848662

output:

0

result:

ok single line: '0'

Test #4:

score: 0
Accepted
time: 1ms
memory: 19976kb

input:

10 10
923415743 -503391272 885740174 329644337 -693052351 -53764994 731859967 -834732760 -57751504 151969590
553689579 313784278 -12090771 921222379 -378313551 819586787 -373658045 559813071 671861309 268258615

output:

13

result:

ok single line: '13'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 19980kb

input:

10 10
-123276196 264891802 609485405 -980113903 152483893 57563748 -454135131 618686452 545983457 236619926
648896419 838269531 -380077537 536463844 89691984 38425645 759165084 325716532 330825142 -472414030

output:

3

result:

wrong answer 1st lines differ - expected: '12', found: '3'
English 繁體中文 简体中文

服务器时间: 2025-02-02 03:48:24 | 开源项目