QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351775#8049. Equal SumsNahidameowWA 1814ms16016kbC++1412.8kb2024-03-12 14:51:172024-03-12 14:51:18

Judging History

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

  • [2024-03-12 14:51:18]
  • 评测
  • 测评结果：WA
  • 用时：1814ms
  • 内存：16016kb
查看
  • [2024-03-12 14:51:17]
  • 提交

answer

#include<bits/stdc++.h>
//=========================================================
typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ul;
typedef long double LD;
#define pd push_back
#define all(x) x.begin(),x.end()
#define allA(x,l,r) x+l,x+r+1
#define mpr std::make_pair
#define ve std::vector
#define mpre(v) v.insert(v.begin(),0)
#define lb lower_bound
//=========================================================
namespace Balance_tree{
	struct Mes{
		Mes(){}
		friend Mes operator + (Mes A,Mes B){
			Mes ans;
			return ans;
		}
	};
	const int N=2e5+10;
	std::mt19937 rnd(time(NULL));
	struct Mes_BLT{
		struct node{int l,r;ll val;int key,sz;Mes rv,v;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;
			if(tr[rt].l&&tr[rt].r)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v+tr[tr[rt].r].rv;
			else if(tr[rt].l)tr[rt].rv=tr[tr[rt].l].rv+tr[rt].v;
			else if(tr[rt].r)tr[rt].rv=tr[rt].v+tr[tr[rt].r].v;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,ll val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(int val,Mes P){int id=newid();return tr[id]={0,0,val,int(rnd()),1,P,P},id;}
		void insert(ll val,Mes P){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val,P)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}Mes query(ll l,ll r){
			int x,y,z;split(rot,r,x,z);
			split(x,l-1,x,y);
			Mes ans=tr[y].rv;
			rot=merge(merge(x,y),z);
			return ans;
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0,Mes(),Mes()};cnt=rot=0;bin.clear();}
	};
	struct Basic_BLT{
		struct node{int l,r;ll val;int key,sz;}tr[5];//don't forget to promote it
		int rot,cnt=0;
		std::vector<int> bin;
		void pushup(int rt){tr[rt].sz=tr[tr[rt].l].sz+tr[tr[rt].r].sz+1;}
		int newid(){
			if(bin.empty())return ++cnt;
			int x=bin.back();bin.pop_back();
			return x;
		}void split(int rt,int val,int &x,int &y){
			if(!rt)return x=y=0,void();
			if(tr[rt].val<=val)x=rt,split(tr[rt].r,val,tr[rt].r,y);
			else y=rt,split(tr[rt].l,val,x,tr[rt].l);
			pushup(rt);
		}int merge(int x,int y){
			if(!x||!y)return x|y;
			if(tr[x].key<=tr[y].key)
				return tr[x].r=merge(tr[x].r,y),pushup(x),x;
			else return tr[y].l=merge(x,tr[y].l),pushup(y),y;
		}int build(ll val){int id=newid();return tr[id]={0,0,val,int(rnd()),1},id;}
		void insert(ll val){
			int x,y;split(rot,val,x,y);
			rot=merge(merge(x,build(val)),y);
		}void del(ll val){
			int x,y,z;split(rot,val,x,z);
			split(x,val-1,x,y);bin.pd(y);
			rot=merge(merge(x,merge(tr[y].l,tr[y].r)),z);
		}int Get_rank(int rt,int k){
			if(k<=tr[tr[rt].l].sz)return Get_rank(tr[rt].l,k);
			if(k==tr[tr[rt].l].sz+1)return rt;
			return Get_rank(tr[rt].r,k-tr[tr[rt].l].sz-1);
		}
		void clear(){for(int i=1;i<=cnt;i++)tr[i]={0,0,0,0,0};cnt=rot=0;bin.clear();}
	};
}
namespace segment_tree{
	const int N=2e5+10;
	template<typename M,typename T> struct sg_tree{
		struct node{M Mes;T Tag;int l,r;}tr[5];
		int rot;int cnt;
		void init(){for(int i=1;i<=cnt;i++)tr[i].Mes=M(),tr[i].Tag=T();rot=cnt=0;}
		void pushup(int rt){
			tr[rt].Mes=M();
			if(tr[rt].l&&tr[rt].r)tr[rt].Mes=tr[tr[rt].l].Mes+tr[tr[rt].r].Mes;
			else if(tr[rt].l)tr[rt].Mes=tr[tr[rt].l].Mes;
			else if(tr[rt].r)tr[rt].Mes=tr[tr[rt].r].Mes;
		}
		void addson(int rt,T x){tr[rt].Mes=tr[rt].Mes+x;tr[rt].Tag=tr[rt].Tag+x;}
		void pushdown(int rt){
			if(tr[rt].Tag==T())return;
			if(tr[rt].l)addson(tr[rt].l,tr[rt].Tag);
			if(tr[rt].r)addson(tr[rt].r,tr[rt].Tag);
			tr[rt].Tag=T();
		}
		void build(int &rt,int l,int r,std::vector<M> &A){
			if(!rt)rt=++cnt;
			if(l==r)return tr[rt].Mes=A[l],void();
			auto mid=l+r>>1;
			build(tr[rt].l,l,mid,A);build(tr[rt].r,mid+1,r,A);
			pushup(rt);
		}
		void change_Seq(int &rt,int l,int r,int x,int y,T P){
			if(x>y)return;
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(x<=l&&r<=y)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid)change_Seq(tr[rt].l,l,mid,x,y,P);
			if(y>mid)change_Seq(tr[rt].r,mid+1,r,x,y,P);
			pushup(rt);
		}
		void change_p(int &rt,int l,int r,int x,T P){
			if(!rt)rt=++cnt,tr[rt].Mes=M(),tr[rt].Tag=T();
			if(l==r)return addson(rt,P);
			auto mid=l+r>>1;pushdown(rt);
			(x<=mid)?change_p(tr[rt].l,l,mid,x,P):change_p(tr[rt].r,mid+1,r,x,P);
			pushup(rt);
		}
		M query(int rt,int l,int r,int x,int y){
			if(!rt||x>y)return M();
			if(x<=l&&r<=y)return tr[rt].Mes;
			auto mid=l+r>>1;pushdown(rt);
			if(x<=mid&&y>mid)return query(tr[rt].l,l,mid,x,y)+query(tr[rt].r,mid+1,r,x,y);
			if(x<=mid)return query(tr[rt].l,l,mid,x,y);
			if(y>mid)return query(tr[rt].r,mid+1,r,x,y);
			assert(false);
		}
		void build(int l,int r,std::vector<M> &A){build(rot,l,r,A);}
		void change_Seq(int l,int r,int x,int y,T P){
			change_Seq(rot,l,r,x,y,P);}
		void change_p(int l,int r,int x,T P){
			change_p(rot,l,r,x,P);}
		M query(int l,int r,int x,int y){
			return query(rot,l,r,x,y);}
	};
	struct Mes{
		Mes(){}
		Mes(ll _S,int _l,int _r){}
		Mes operator + (Mes P){
			Mes ans=Mes();
			return ans;
		}
	};
	struct Tag{
		Tag(){}
		Tag operator + (Tag P){
			Tag ans=Tag();
			return ans;
		}
		bool operator == (Tag P){return true!=false;}
	};
	Mes operator + (Mes A,Tag B){return A;}
}
namespace Fenwick_Tree{
	const int N=2e5+10;
	struct FwT{
		ll tr[5];int u;
		void init(int _u){
			u=_u;
			for(int i=0;i<=u;i++)tr[i]=0;}
		void add(int x,ll y){for(;x<=u;x+=(x&-x))tr[x]+=y;}
		ll query(int x){ll ans=0;for(;x;x^=(x&-x))ans+=tr[x];return ans;}
		ll query(int l,int r){if(l>r)return 0;return query(r)-query(l-1);}
	};
}
//=========================================================
namespace Math{
	ll QP(ll x,ll y,ll mod){ll ans=1;for(;y;y>>=1,x=x*x%mod)if(y&1)ans=ans*x%mod;return ans;}
	ll QA(ll x,ll y,ll mod){ll ans=0;for(;y;y>>=1,x=(x<<1)%mod)if(y&1)ans=(ans+x)%mod;return ans;}
	ll inv(ll x,ll mod){return QP(x,mod-2,mod);}
}
typedef unsigned U;
//=========================================================
namespace IO{
	const double eps=1e-8;
	const int BUFSIZE=1<<20;
	char ibuf[BUFSIZE],*is=ibuf,*it=ibuf;
	char tmp[BUFSIZE];int cnt=0;
	inline char getch(){if(is==it)it=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);return is==it?EOF:*is++;}
	int readInt(){int x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	ll readLL(){ll x=0,y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	Int readInt128(){Int x=0;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return !y?x:-x;}
	char readChar(){char c=0;while(!c||c==' '||c=='\n')c=getch();return c;}
	std::string readString(){std::string S;char c=0;while(!c||c==' '||c=='\n')c=getch();while(c!=' '&&c!='\n')S.pd(c),c=getch();return S;}
	LD readDouble(){LD x=0,d=1;int y=0;char c=0;while(!isdigit(c))y|=c=='-',c=getch();int cnt=0;bool flg=false;while(isdigit(c)){
		x=x*10+(c^48),flg|=(c^48),cnt+=flg,c=getch();if(cnt>=12)goto flg;}if(c=='.'){c=getch();while(isdigit(c)){d*=10,x+=(c^48)/d;flg|=(c^48),cnt+=flg;
		if(cnt>=12)goto flg;c=getch();}}flg:;return !y?x:-x;}
	ul readUll(){ul x=0;char c=0;while(!isdigit(c))c=getch();while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getch();return x;}

	void flush(){fwrite(tmp,1,cnt,stdout);cnt=0;}
	void putch(char c){tmp[cnt++]=c;if(cnt==BUFSIZE)flush();}
	void putint(int x){char Q[10];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putInt128(Int x){char Q[45];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putLL(ll x){char Q[20];int tp=0;if(x<0)putch('-'),x=-x;if(x==0)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}
	void putString(std::string x){for(auto p:x)putch(p);}
	void putDouble(LD x){if(x<0)x=-x,putch('-');if(fabs(x)<=eps)return putch(0);bool flg=false;LD d=1e10;LD l=std::min(LD(1e-10),1.0/std::max(LD(1),x));
		while(d>=l){if(d<=1){if(ll(x/d+d*1e-2)%10>0||flg)putch(ll(x/d+d*1e-2)%10+'0'),flg=true;}else{if(ll(x/d)%10>0||flg)putch(ll(x/d)%10+'0'),flg=true;
		}x-=ll(x/d+eps)*d; if(d==1){if(!flg)putch('0');putch('.');}d/=10;}}
	void putUll(ul x){char Q[25];int tp=0;if(!x)putch('0');while(x)Q[tp++]=(x%10+'0'),x/=10;while(tp--)putch(Q[tp]);}

	struct Basic{
		Basic &operator>>(int &A){A=IO::readInt();return (*this);}
		Basic &operator>>(ll &A){A=IO::readLL();return (*this);}
		Basic &operator>>(Int &A){A=IO::readInt128();return (*this);}
		Basic &operator>>(char &A){A=IO::readChar();return (*this);}
		Basic &operator>>(std::string &A){A=IO::readString();return (*this);}
		Basic &operator>>(double &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(LD &A){A=IO::readDouble();return (*this);}
		Basic &operator>>(float &A){A=IO::readDouble();return (*this);}
		template<typename T1,typename T2>
		Basic &operator>>(std::pair<T1,T2>&v){(*this)>>v.first>>v.second;return (*this);}
		template<typename T,int d>
		Basic &operator>>(std::array<T,d> &v){for(auto &p:v)(*this)>>p;return (*this);}
		template<typename T>
		Basic &operator>>(std::vector<T> &v){for(auto &p:v)(*this)>>p;return (*this);}
		Basic &operator>>(ul &v){v=readUll();return (*this);}

		Basic &operator<<(const int &A){putint(A);return (*this);}
		Basic &operator<<(const char &A){putch(A);return (*this);}
		Basic &operator<<(const ll &A){putLL(A);return (*this);}
		Basic &operator<<(const Int &A){putInt128(A);return (*this);}
		Basic &operator<<(const std::string &A){putString(A);return (*this);}
		Basic &operator<<(const LD &A){putDouble(A);return (*this);}
		Basic &operator<<(const double &A){putDouble(A);return (*this);}
		Basic &operator<<(const float &A){putDouble(A);return (*this);}
		template<typename T>
		Basic &operator<<(const std::vector<T> &v){for(int i=0;i<v.size();i++)(*this)<<v[i]<<(v.size()==i+1?'\n':' ');return (*this);}
		Basic &operator<<(const ul &A){putUll(A);return (*this);}

		void Flush(){flush();}
	}cin,cout;
}
//=========================================================
namespace Grader{
	std::vector<int>S;
	void Get(std::vector<int>v){
		assert(S.empty());

		reverse(all(S));
	}
	int readInt(){
		assert(!S.empty());
		int x=S.back();
		S.pop_back();
		return x;
	}
	void putInt(int x){
		std::vector<int>P;
		P.pd(x);Get(P);
	}void putVec(std::vector<int>v){Get(v);}
}
//=========================================================
bool FileIfstream(std::string name){
	std::ifstream f(name.c_str());
	return f.good();
}
//=========================================================
const int mod=998244353;
//int add(int x,int y){x+=y;if(x>=mod)x-=mod;if(x<0)x+=mod;return x;}
//int mul(int x,int y){return 1ll*x*y%mod;}
#define add(x,y) {x+=y;if(x>=mod)x-=mod;}
const int N=5e2+50;
int f[2][N][N*2],g[2][N][N*2],h[N][N];
const int M=5e2+1;
void solve(){
	//don't forget to open long long
	int n,m;IO::cin>>n>>m;
	ve<std::pair<int,int>>v1(n+1),v2(m+1);
	for(int i=1;i<=n;i++)IO::cin>>v1[i].first>>v1[i].second;
	for(int i=1;i<=m;i++)IO::cin>>v2[i].first>>v2[i].second;
	f[0][0][M]=1;
	for(int i=0;i<=n;i++){
		memset(f[i&1^1],0,sizeof(f[i&1^1]));
		for(int j=0;j<=m;j++){
			memset(g[i&1][j],0,sizeof(g[i&1][j]));
			h[i][j]=f[i&1][j][M];
			for(int S=1;S<=1003;S++){
				add(g[i&1][j][S],g[i&1][j][S-1]);
				add(g[i&1][j][S],f[i&1][j][S]);
			}
				
		//	for(int S=M-10;S<=M+10;S++)
		//		IO::cout<<g[i&1][j][S]<<' ';
		//	IO::cout<<'\n';
		//	for(int S=M-10;S<=M+10;S++)
		//		IO::cout<<g[i&1][j+1][S]<<' ';
		//	IO::cout<<'\n'; 
			auto get=[&](int l,int r)->int{
				if(l>r)return 0;
				r=std::min(r,1003);
				l=std::max(l,1);
				return (g[i&1][j][r]-g[i&1][j][l-1])%mod;};
			for(int S=1;S<=1003;S++){
				if(i<n)
					add(f[i&1^1][j][S],get(S-v1[i+1].second,std::min(S-v1[i+1].first,M)));
				if(i<m)
					add(f[i&1][j+1][S],get(std::max(M+1,S+v2[j+1].first),S+v2[j+1].second));
			}
		}
	} 
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)
			IO::cout<<(h[i][j]+mod)%mod<<' ';
		IO::cout<<'\n';
	}
}
int main(){
#ifndef ONLINE_JUDGE
	if(!FileIfstream("IO.in")){
		freopen("IO.in","w",stdout);
		return 0;
	}
	freopen("IO.in","r",stdin);
	freopen("IO.out","w",stdout);
#endif
	//std::ios::sync_with_stdio(false);
	//std::cin.tie(0);
	//std::cout.tie(0);
	int T=1;
	while(T--)solve();

	IO::cout.Flush();
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 13916kb

input:

2 3
1 2
2 3
1 4
2 2
1 3

output:

2 0 0 
3 4 4

result:

ok 6 numbers

Test #2:

score: -100
Wrong Answer
time: 1814ms
memory: 16016kb

input:

500 500
19 458
1 480
7 485
50 461
12 476
15 461
48 466
40 453
46 467
9 458
27 478
26 472
46 459
29 490
6 500
17 487
48 484
28 472
28 459
25 480
4 491
29 481
36 460
2 491
44 499
22 473
20 458
4 483
27 471
2 496
11 461
43 450
2 478
37 466
15 459
42 482
7 451
19 455
2 453
47 475
48 450
1 474
46 471
9 4...

output:

411 86001 23249175 45264309 990983213 997957696 157998831 947028244 3745191 403611459 669778190 159857301 303822152 131039430 343891540 743332563 516103721 897481013 845167590 472472000 619096841 482940289 101842492 506495924 98265374 332953934 391681701 609364284 201419189 332235016 624091056 30564...

result:

wrong answer 2nd numbers differ - expected: '79401', found: '86001'
English 繁體中文 简体中文

Server Time: 2024-12-01 00:25:33 | OpenSource Project