QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#351975#8049. Equal SumsNahidameowWA 1944ms19552kbC++1412.8kb2024-03-12 18:31:592024-03-12 18:31:59

Judging History

This is the latest submission verdict.

  • [2024-03-12 18:31:59]
  • Judged
  • Verdict: WA
  • Time: 1944ms
  • Memory: 19552kb
Show
  • [2024-03-12 18:31:59]
  • Submitted

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=x+y-(x+y>=mod?mod:0);}
const int N=6e2+50;
int f[2][N][N*2],g[2][N][N*2],h[N][N];
const int M=5e2+50;
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<=M*2+10;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,M*2+10);
				l=std::max(l,1);
				return (g[i&1][j][r]-g[i&1][j][l-1]+mod)%mod;};
			for(int S=1;S<=M*2+10;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(j<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: 17956kb

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: 1944ms
memory: 19552kb

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 79401 21505001 129611902 947988847 472117965 140478922 273529460 990533849 304927621 675236652 869085990 772646210 187160083 371765019 178777273 32415382 284847725 337743935 321515158 552537416 702848814 334179664 836862037 164115550 608706490 732103373 724612482 594590412 6594692 604170335 2822...

result:

wrong answer 3rd numbers differ - expected: '9145270', found: '21505001'
English 繁體中文 简体中文

Server Time: 2025-02-25 21:03:12 | OpenSource Project