QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #22584 | #2849. 弗雷兹的玩具商店 | lindongli2004# | WA | 465ms | 22104kb | C++17 | 2.6kb | 2022-03-09 22:22:27 | 2022-04-30 01:24:39 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define int long long
const int M=63,N=1002021;
typedef pair<int,int> PII;
int n,m,blo;
int bl[N],val[N],c[N],tagw[N],tagc[N],f[N],q[N/20][M],_q[M];
bool cmp(const PII &x,const PII &y){return x>y;};
void remake(int x){
int L=(x-1)*blo+1,R=min(n,x*blo),top=0;
for(int i=1;i<=m;i++)q[x][i]=-2e9;
for(int i=L;i<=R;i++){
val[i]+=tagw[x],c[i]=(c[i]-1+tagc[x])%m+1;
q[x][c[i]]=max(q[x][c[i]],val[i]);
} tagw[x]=tagc[x]=0;
}
void changec(int l,int r,int ad){
for(int i=l;i<=min(r,bl[l]*blo);i++)
c[i]=(c[i]-1+ad)%m+1;
remake(bl[l]);
if(bl[l]!=bl[r]){
for(int i=(bl[r]-1)*blo+1;i<=r;i++)
c[i]=(c[i]-1+ad)%m+1;
remake(bl[r]);
}
for(int i=bl[l]+1;i<bl[r];i++)
tagc[i]+=ad;
}
void changew(int l,int r,int ad){
for(int i=l;i<=min(r,bl[l]*blo);i++)val[i]+=ad;
remake(bl[l]);
if(bl[l]!=bl[r]){
for(int i=(bl[r]-1)*blo+1;i<=r;i++)val[i]+=ad;
remake(bl[r]);
}
for(int i=bl[l]+1;i<bl[r];i++)
tagw[i]+=ad;
}
void print(int x){
if(x>9)print(x/10);
putchar(x%10+'0');
}
void push(int x,int c){
_q[c]=max(_q[c],x);
}
void solve(int l,int r){
for(int i=1;i<=m;i++)_q[i]=-2e9;
for(int i=l;i<=min(r,bl[l]*blo);i++)
push(val[i]+tagw[bl[l]],(c[i]+tagc[bl[l]]-1)%m+1);
if(bl[l]!=bl[r]){
for(int i=(bl[r]-1)*blo+1;i<=r;i++)
push(val[i]+tagw[bl[r]],(c[i]+tagc[bl[r]]-1)%m+1);
}
for(int i=bl[l]+1;i<bl[r];i++){
int ad=tagc[i];
for(int j=1;j<=m;j++)
push(q[i][j],(j+ad-1)%m+1);
}
for(int i=0;i<=m;i++)f[i]=0;
for(int i=1;i<=m;i++){
for(int j=i;j<=m;j++)
f[j]=max(f[j],f[j-i]+_q[i]);
}
int ans1=0,ans2=0;
for(int i=1;i<=m;i++){
// cout<<"f["<<i<<"]="<<f[i]<<endl;
ans1+=f[i],ans2^=f[i];
}
print(ans1); putchar(' ');
print(ans2); putchar('\n');
}
int read(){
int x=0,f=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#undef int
int main()
{
// freopen("std.in","r",stdin);
// freopen("J.out","w",stdout);
#define int long long
n=read(); m=read(); blo=1300;
for(int i=1;i<=n;i++)c[i]=read();
for(int i=1;i<=n;i++)val[i]=read();
for(int i=1;i<=n;i++)bl[i]=(i-1)/blo+1;
for(int i=1;i<=bl[n];i++)remake(i);
int aq=read();
while(aq--){
int op=read(),l=read(),r=read();
if(op==1)changec(l,r,read());
if(op==2)changew(l,r,read());
if(op==3)solve(l,r);
}
return 0;
}
/*
4 10
1 6 10 2
100 2333 666 300
7
3 1 4
3 1 3
1 2 4 1
3 1 4
2 2 3 -1000
2 2 3 -600
3 2 4
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 15880kb
input:
4 10 1 6 10 2 100 2333 666 300 7 3 1 4 3 1 3 1 2 4 1 3 1 4 2 2 3 -1000 2 2 3 -600 3 2 4
output:
15165 2865 14165 2169 36630 798 4899 1273
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 465ms
memory: 22104kb
input:
200000 60 21 16 58 5 26 44 30 40 31 27 50 21 59 50 37 39 26 9 15 14 9 59 40 29 32 5 2 25 57 18 4 9 25 1 13 42 36 34 21 6 53 2 18 51 51 55 29 17 3 36 22 11 26 1 40 58 57 33 22 53 42 26 1 6 18 6 47 54 31 59 51 23 60 1 13 43 55 34 59 49 9 12 51 34 4 22 31 1 47 45 45 28 10 38 34 19 35 12 4 5 11 47 28 2 ...
output:
304493141 5964069 302725180 6346266 263891804 12270170 206665590 7376160 224407908 12588660 302448165 6791651 298016030 8641780 187482000 7499280 276575975 13386421 302685395 8377169 304348641 5950973 296928490 9925716 273952510 11264178 185846328 1238664 276368626 13405014 200927082 49156 84257215 ...
result:
wrong answer 1st lines differ - expected: '304478979 5965183', found: '304493141 5964069'