QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#194434#7522. Sequence Shiftucup-team191#WA 19ms9764kbC++234.3kb2023-09-30 20:42:282023-09-30 20:42:29

Judging History

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

  • [2023-09-30 20:42:29]
  • 评测
  • 测评结果:WA
  • 用时:19ms
  • 内存:9764kb
  • [2023-09-30 20:42:28]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define x first
#define y second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define eb emplace_back
#pragma GCC optimize("unroll-loops")
#define shandom_ruffle(a, b) shuffle(a, b, rng)
#define vi vector<int>
#define vl vector<ll>
#define popcnt __builtin_popcountll
#define all(a) begin(a),end(a)
//for kactl
#define sz(x) (int)(x).size()
#define rep(i, a, b) for(int i = a; i < (b); ++i)

using namespace std;
using namespace __gnu_pbds;

using ll=long long;
using ull=unsigned long long;
using ld=long double;
int MOD=1000000007;
int MOD2=998244353;
vector<int> bases;
const ll LLINF=1ll<<60;
const char en='\n';

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void yes() {cout<<"YES"<<en; exit(0);}
void no() {cout<<"NO"<<en; exit(0);}
inline int rund() {int x576363482791fuweh=rng();return abs(x576363482791fuweh)%RAND_MAX;}
template<class T>
void prVec(vector<T> w,bool fl=false)
{
	cout<<w.size()<<en;
	for (int i=0;i<int(w.size())-1;++i) cout<<w[i]<<' ';
	if (w.size()) cout<<w[w.size()-1]<<en;
	if (fl) cout<<flush;
}

void M998()
{
	swap(MOD,MOD2);
}

ll raand()
{
	ll a=rund();
	a*=RAND_MAX;
	a+=rund();
    return a;
}

#define rand raand

ll raaand()
{
	return raand()*(MOD-7)+raand();
}

template<class T>
vi compress(vector<T>&v)
{
	set<T> s;
	for (auto a: v) s.insert(a);
	vector<T> o(all(s));
	vi nv;
	for (int i=0;i<(int)v.size();++i) nv.pb(lower_bound(all(o),v[i])-o.begin());
	return nv;
}

string to_upper(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='a' && a[i]<='z') a[i]-='a'-'A';
	return a;
}

string to_lower(string a)
{
	for (int i=0;i<(int)a.size();++i) if (a[i]>='A' && a[i]<='Z') a[i]+='a'-'A';
	return a;
}

ll sti(string a,int base=10)
{
	ll k=0;
	for (int i=0;i<(int)a.size();++i)
	{
		k*=base;
		k+=a[i]-'0';
	}
	return k;
}

template<class T>
void eras(vector<T>& a,T b)
{
	a.erase(find(a.begin(),a.end(),b));
}

string its(ll k,int base=10)
{
	if (k==0) return "0";
	string a;
	while (k)
	{
		a.push_back((k%base)+'0');
		k/=base;
	}
	reverse(a.begin(),a.end());
	return a;
}

ll min(ll a,int b)
{
	if (a<b) return a;
	return b;
}

ll min(int a,ll b)
{
	if (a<b) return a;
	return b;
}

ll max(ll a,int b)
{
	if (a>b) return a;
	return b;
}

ll max(int a,ll b)
{
	if (a>b) return a;
	return b;
}

ll gcd(ll a,ll b)
{
	if (b==0) return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
	return a/gcd(a,b)*b;
}

template<class T,class K>
pair<T,K> mp(T a,K b)
{
	return make_pair(a,b);
}

inline int mult(ll a,ll b)
{
	return (a*b)%MOD;
}

inline int pot(int n,int k)
{
	if (k==0) return 1;
	ll a=pot(n,k/2);
	a=mult(a,a);
	if (k%2) return mult(a,n);
	else return a;
}

int divide(int a,int b)
{
	return mult(a,pot(b,MOD-2));
}

inline int sub(int a,int b)
{
	if (a-b>=0) return a-b;
	return a-b+MOD;
}

inline int add(int a,int b)
{
	if (a+b>=MOD) return a+b-MOD;
	return a+b;
}

void ad(int&a,int b)
{
	a+=b;
	if (a>=MOD) a-=MOD;
}

void su(int&a,int b)
{
	a-=b;
	if (a<0) a+=MOD;
}

bool prime(ll a)
{
	if (a==1) return 0;
	for (int i=2;i<=round(sqrt(a));++i)
	{
		if (a%i==0) return 0;
	}
	return 1;
}

int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
const int N=2000010,K=10;
int q,n,a[N],b[N],an[N];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	for (int i=0;i<10;++i) bases.push_back(rand()%(MOD-13893829*2)+13893829);
	cin>>n>>q;
	for (int i=0;i<n;++i) cin>>a[i];
	for (int i=0;i<n;++i) cin>>b[i];
	if (n*q<=1e8)
	{
		int ma=0;
		for (int i=0;i<n;++i) ma=max(ma,a[i]+b[i]);
		cout<<ma<<en;
		for (int i=n;i<n+q;++i)
		{
			int w;
			cin>>w;
			w^=ma;
			b[i]=w;
			ma=0;
			for (int j=0;j<n;++j) ma=max(ma,a[j]+b[j+(i-n+1)]);
			cout<<ma<<en;
		}
	}
	else
	{
		vi dob;
		const int POT=MOD-MOD/K/sqrt(n);
		for (int i=0;i<n;++i) if (a[i]>=POT) dob.pb(i);
		for (int i=0;i<n;++i) if (b[i]>=POT)
		{
			for (auto x: dob) if (x<=i) an[i-x]=max(an[i-x],a[x]+b[i]);
		}
		cout<<an[0]<<en;
		for (int i=1;i<=q;++i)
		{
			int w;
			cin>>w;
			w^=an[i-1];
			if (w>=POT) for (auto x: dob) an[i+(n-1)-x]=max(an[i+(n-1)-x],a[x]+w);
			cout<<an[i]<<en;
		}
	}
}




Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

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

output:

11
13
16
25

result:

ok 4 lines

Test #2:

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

input:

1 0
103509429
823330096

output:

926839525

result:

ok single line: '926839525'

Test #3:

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

input:

1 1
576560149
691846236
1156187222

output:

1268406385
835582012

result:

ok 2 lines

Test #4:

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

input:

1 10
700282491
332230980
90825676
1630266999
644973380
262379760
2122877054
1851957134
1370195232
110993724
1319359505
1883523208

output:

1032513471
1654684398
759763732
888538827
1695749302
1163465539
1425605448
789576931
1397740634
1202288326
1638577353

result:

ok 11 lines

Test #5:

score: 0
Accepted
time: 19ms
memory: 9764kb

input:

1000 100000
438001359 929744877 710148392 323984311 727016267 323629255 495752276 309120511 312675195 717795522 937464489 624952229 444774478 829169766 707441777 609125148 25459976 849166512 716162953 882416779 189669312 135698832 632796131 592794700 569746403 231058028 389412868 824283503 801480367...

output:

1962871590
1986083253
1967509108
1973351244
1974354421
1956371849
1976394149
1995721753
1946870160
1984280254
1961237540
1955903880
1944520591
1937726835
1993563403
1927000559
1951483558
1979133252
1979156812
1941301401
1922284543
1980597785
1963663583
1946961524
1933606347
1953947075
1953071855
194...

result:

ok 100001 lines

Test #6:

score: 0
Accepted
time: 13ms
memory: 7804kb

input:

10000 10000
760845880 236665988 765352292 817854026 789863420 399953246 270535243 932350041 48814223 670950468 456660682 416165008 999681497 666880584 56581573 134567049 403285848 144814129 973325555 23519957 518449311 738687225 345716065 2309498 477743569 555951695 911860717 920761968 569179690 349...

output:

1990514380
1974843876
1992500750
1994731468
1983411218
1986646709
1979643361
1990060423
1988174297
1983373232
1995134632
1989936349
1993187026
1988927807
1971595730
1988272839
1990590966
1981928791
1987819156
1987483957
1979800700
1986611531
1973877196
1995735988
1985734454
1987573480
1988935268
199...

result:

ok 10001 lines

Test #7:

score: -100
Wrong Answer
time: 15ms
memory: 8156kb

input:

10000 100000
682604470 430466819 955519058 186918998 587587373 201134122 473675328 586747694 132807628 255672373 504315038 137082392 753499284 586570202 133549919 570424589 87103369 2142325 895908281 852456682 239920694 443878018 717067433 437134318 39426086 82137124 698018668 518394430 430778732 56...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
...

result:

wrong answer 1st lines differ - expected: '1984544998', found: '0'