神奇wa3求助
查看原帖
神奇wa3求助
32490
memory_frv楼主2021/8/3 17:58

wrong answer 3rd numbers differ - expected: '732131239', found: '1100243759015'

用cf的数据在本地跑就对,交上就不对,球球啦

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
#include<windows.h>
#define ll long long
using namespace std;
struct node{
	ll l,r;
	mutable ll v;
	node(ll a=-1,ll b=-1,ll c=0){
		l=a,r=b,v=c;
	}
	bool operator <(const node &a) const{
		return l<a.l;
	}
};
set<node> st;
inline set<node>::iterator split(ll pos){
	set<node>::iterator iter=st.lower_bound(node(pos));
	if(iter!=st.end()&&iter->l==pos) return iter;
	--iter;node temp=*iter;st.erase(iter);
	st.insert(node(temp.l,pos-1,temp.v));
	return st.insert(node(pos,temp.r,temp.v)).first;   
}
inline void assign(ll l,ll r,ll val){	
	set<node>::iterator itl=split(l),itr=split(r+1);
	st.erase(itl,itr);
	st.insert((node){l,r,val});  
}
inline void add(ll l,ll r,ll ad){
	set<node>::iterator itl=split(l),itr=split(r+1);
	for(set<node>::iterator iter=itl;iter!=itr;++iter){
		iter->v+=ad;
	}
}
inline int querykth(ll l,ll r,ll k){
	set<node>::iterator itl=split(l),itr=split(r+1);
	vector <pair<ll,ll> > v(0);
	for(set<node>::iterator iter=itl;iter!=itr;++iter){
		v.push_back(make_pair(iter->v,iter->r-iter->l+1));
	}
	sort(v.begin(),v.end());
	for(vector<pair<ll,ll> >::iterator iter=v.begin() ;iter!=v.end();++iter){
		k-=iter->second;
		if(k<=0) return iter->first;
	}
}
inline ll quick(ll a,ll b,ll mod){
	a%=mod;
	ll c=1;
	while(b){
		if(b&1) c=(c*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return c;
}
inline ll querypow(ll l,ll r,ll x,ll y){
	set<node>::iterator itl=split(l),itr=split(r+1);
	ll ans=0;
	for(set<node>::iterator iter=itl;iter!=itr;++iter){
		ll temp=quick(iter->v,x,y);
		ans=(ans+(temp*(iter->r-iter->l+1))%y)%y;
	}
	return ans;
}
ll n,m,seed,vmax;
inline ll rnd(){
	ll ret=seed;
	seed=(seed*7+13)%1000000007;
	return ret;
}
int main(){
	//freopen("1.out","w",stdout);
	cin>>n>>m>>seed>>vmax;
	for(ll i=1;i<=n;i++){
		ll x=(rnd()%vmax)+1;
		st.insert((node){i,i,x}); 
	}
	ll x,y;
	for(ll i=1;i<=m;i++){
		ll op=(rnd()%4)+1,l=(rnd()%n)+1,r=(rnd()%n)+1;
		if(l>r) swap(l,r);
		if(op==3){
			x=(rnd()%(r-l+1))+1;
		}else{
			x=(rnd()%vmax)+1;
		}
		if(op==4){
			y=(rnd()%vmax)+1;
		}
		if(op==1){
			add(l,r,x);
		}else if(op==2){
			assign(l,r,x);
		}else if(op==3){
			printf("%lld\n",querykth(l,r,x));
			//Sleep(100);
		}else{
			printf("%lld\n",querypow(l,r,x,y));
			//Sleep(100);
		}
		//Sleep(100);
	}
	return 0;
} ```
2021/8/3 17:58
加载中...