QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#608328 | #6836. A Plus B Problem | Dixiky_215 | AC ✓ | 1873ms | 73816kb | C++20 | 4.9kb | 2024-10-03 20:42:20 | 2024-10-03 20:42:20 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN=3e6+7;
int n,q;
int l[MAXN*4],r[MAXN*4],maxl[MAXN*4],minl[MAXN*4];
int lazy[MAXN*4];
int a[MAXN][3];
string bb;
int s[MAXN];
void push_down(int x)
{
if(lazy[x]!=-1)
{
lazy[x*2]=lazy[x];
lazy[2*x+1]=lazy[x];
lazy[x]=-1;
}
return;
}
void push_up(int x)
{
int s1,s2;
if(lazy[x*2]!=-1) s1=lazy[x*2];
else s1=maxl[x*2];
if(lazy[2*x+1]!=-1) s2=lazy[2*x+1];
else s2=maxl[2*x+1];
maxl[x]=max(s1,s2);
if(lazy[x*2]!=-1) s1=lazy[x*2];
else s1=minl[x*2];
if(lazy[2*x+1]!=-1) s2=lazy[2*x+1];
else s2=minl[2*x+1];
minl[x]=min(s1,s2);
}
void build(int x,int li,int ri)
{
int mid=(li+ri)>>1;
l[x]=li;r[x]=ri;
maxl[x]=-1e9;minl[x]=1e9;
lazy[x]=-1;
if(li==ri)
{
maxl[x]=s[li];
minl[x]=s[li];
return;
}
build(2*x,li,mid);
build(2*x+1,mid+1,ri);
push_up(x);
return;
}
void modify(int x,int li,int ri,int y)
{
int mid=(l[x]+r[x])>>1;
if(l[x]==li&&r[x]==ri)
{
lazy[x]=y;
return;
}
push_down(x);
push_up(x);
if(ri<=mid) modify(2*x,li,ri,y);
else if(li>mid) modify(2*x+1,li,ri,y);
else modify(2*x,li,mid,y),modify(2*x+1,mid+1,ri,y);
push_up(x);
return;
}
void modifyk(int x,int loc,int y)
{
int mid=(l[x]+r[x])>>1;
if(l[x]==r[x])
{
lazy[x]=y;
return;
}
push_down(x);
push_up(x);
if(loc<=mid) modifyk(2*x,loc,y);
else modifyk(2*x+1,loc,y);
push_up(x);
return;
}
int ask_val(int x,int loc)
{
int mid=(l[x]+r[x])>>1;
if(l[x]==r[x])
{
if(lazy[x]!=-1) return lazy[x];
return maxl[x];
}
push_down(x);
push_up(x);
if(loc<=mid) return ask_val(2*x,loc);
else return ask_val(2*x+1,loc);
}
int ask_max(int x,int li,int ri)
{
int mid=(l[x]+r[x])>>1;
if(l[x]==li&&r[x]==ri)
{
if(lazy[x]!=-1) return lazy[x];
return maxl[x];
}
push_down(x);
push_up(x);
if(ri<=mid) return ask_max(2*x,li,ri);
else if(li>mid) return ask_max(2*x+1,li,ri);
else return max(ask_max(2*x,li,mid),ask_max(2*x+1,mid+1,ri));
}
int ask_min(int x,int li,int ri)
{
int mid=(l[x]+r[x])>>1;
if(l[x]==li&&r[x]==ri)
{
if(lazy[x]!=-1) return lazy[x];
return minl[x];
}
push_down(x);
push_up(x);
if(ri<=mid) return ask_min(2*x,li,ri);
else if(li>mid) return ask_min(2*x+1,li,ri);
else return min(ask_min(2*x,li,mid),ask_min(2*x+1,mid+1,ri));
}
int ask(int x,int li,int ri,int y)
{
int mid=(l[x]+r[x])>>1;
if(l[x]==li&&r[x]==ri)
{
int s1=maxl[x],s2=minl[x];
if(lazy[x]!=-1) s1=lazy[x],s2=lazy[x];
if(s1==y&&s2==y) return l[x];
if(l[x]==r[x]) return 1e9;
int loc1=1e9,loc2=1e9;
loc1=ask(2*x+1,mid+1,ri,y);
if(loc1==mid+1) loc2=ask(2*x,li,mid,y);
return min(loc1,loc2);
}
push_down(x);
push_up(x);
if(ri<=mid) return ask(2*x,li,ri,y);
else if(li>mid) return ask(2*x+1,li,ri,y);
else
{
int loc1=1e9,loc2=1e9;
loc1=ask(2*x+1,mid+1,ri,y);
if(loc1==mid+1) loc2=ask(2*x,li,mid,y);
return min(loc1,loc2);
}
}
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
cin>>n>>q;
cin>>bb;
for(int i=2;i<=n+1;i++) a[i][1]=bb[i-2]-'0';
cin>>bb;
for(int i=2;i<=n+1;i++) a[i][2]=bb[i-2]-'0';
for(int i=n+1;i>=2;i--)
{
s[i-1]+=(s[i]+a[i][1]+a[i][2])/10;
s[i]=(s[i]+a[i][1]+a[i][2])%10;
}
build(1,1,n+1);
int kkk=0;
while(q--)
{
kkk++;
int opt,id,sss;
cin>>opt>>id>>sss;
id++;
int nowl=ask_val(1,id);
int cha=sss-a[id][opt];
// cerr<<nowl<<" "<<cha<<" asd"<<endl;
if(cha==0)
{
cout<<ask_val(1,id)<<" 0\n";
continue;
}
int ans=1;
if(nowl+cha<0)
{
int aim=nowl+cha+10;
modify(1,id,id,aim);
ans++;
int loc=-1;
int lk=2,rk=id-1;
if(lk<=rk) loc=ask(1,lk,rk,0);
if(loc==1e9) loc=-1;
if(loc!=-1)
{
ans+=id-loc;
modify(1,loc,id-1,9);
}
else loc=id;
if(loc>2) ans++;
int sk=ask_val(1,loc-1);
modifyk(1,loc-1,sk-1);
}
else if(nowl+cha>=10)
{
int aim=nowl+cha-10;
modify(1,id,id,aim);
ans++;
int loc=-1;
int lk=2,rk=id-1;
if(lk<=rk) loc=ask(1,lk,rk,9);
if(loc==1e9) loc=-1;
if(loc!=-1)
{
ans+=id-loc;
modify(1,loc,id-1,0);
}
else loc=id;
if(loc>2) ans++;
int sk=ask_val(1,loc-1);
modifyk(1,loc-1,sk+1);
}
else
{
// if(kkk==3) cerr<<" asd"<<endl;
int aim=nowl+cha;
modifyk(1,id,aim);
ans++;
}
cout<<ask_val(1,id)<<' '<<ans<<'\n';
a[id][opt]=sss;
}
return 0;
}
/*
5 5
01234
56789
2 1 0
2 2 1
2 3 2
2 4 3
2 5 4
1 1
1
1
1 1 9
*/
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 15860kb
input:
5 5 01234 56789 2 1 0 2 2 1 2 3 2 2 4 3 2 5 4
output:
0 2 3 2 5 3 7 3 8 3
result:
ok 5 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 15884kb
input:
1 1 1 1 1 1 9
output:
0 2
result:
ok single line: '0 2'
Test #3:
score: 0
Accepted
time: 236ms
memory: 15952kb
input:
10 1000000 6869373857 3130626142 1 9 2 1 10 0 2 7 6 1 1 0 1 7 6 2 10 4 2 3 9 2 4 2 2 4 4 2 7 0 1 2 4 1 9 8 1 3 7 1 7 1 1 1 5 2 1 6 1 3 5 2 5 8 2 6 5 1 6 3 1 3 8 2 4 2 2 6 3 2 2 6 1 10 9 2 1 1 2 5 4 1 1 8 2 4 0 1 9 1 1 1 8 2 4 2 2 9 2 1 10 3 1 8 9 1 4 6 2 3 0 1 1 6 1 7 1 1 10 9 2 4 4 2 5 9 2 1 8 1 9 ...
output:
6 2 2 2 9 0 3 2 2 8 4 2 6 2 2 2 4 2 6 5 6 3 2 4 7 2 2 2 8 2 1 2 5 2 1 3 2 3 8 3 8 2 2 2 6 2 1 3 3 3 7 2 7 3 0 2 9 3 6 4 0 0 1 3 4 2 7 3 0 3 8 3 8 3 8 2 2 0 3 3 0 3 2 3 5 2 9 2 4 2 8 2 3 3 5 3 3 2 5 0 4 2 3 2 1 2 4 2 7 3 0 2 5 2 6 2 0 3 4 2 4 2 3 2 5 3 6 3 3 0 8 2 9 3 9 3 1 2 1 4 7 2 5 2 5 2 4 0 0 2 ...
result:
ok 1000000 lines
Test #4:
score: 0
Accepted
time: 236ms
memory: 15932kb
input:
10 1000000 8702774998 9088637390 1 3 3 2 4 7 1 4 0 1 6 7 1 1 1 1 4 0 2 3 8 1 7 7 2 4 5 2 4 2 1 8 2 2 6 7 1 1 2 1 1 4 1 10 3 1 2 3 1 2 5 1 4 8 1 6 5 1 9 8 1 1 9 1 2 1 1 8 5 1 8 3 1 7 1 1 9 7 1 10 7 1 8 5 1 5 1 2 6 4 1 6 1 2 10 2 1 10 5 2 10 1 1 9 3 2 2 0 1 1 0 1 6 6 2 2 5 2 4 4 2 5 6 2 7 4 1 2 5 2 4 ...
output:
2 3 0 2 8 3 1 0 0 2 8 0 1 0 5 2 6 2 3 2 6 3 5 2 1 2 3 2 3 2 4 2 6 2 1 3 3 2 7 2 8 2 2 2 9 2 7 2 8 3 6 2 7 2 9 2 8 3 9 3 5 2 9 2 7 2 6 2 2 2 2 0 9 2 0 3 7 2 2 2 8 0 5 2 1 3 0 2 2 3 3 2 0 2 3 3 2 2 0 2 2 0 5 2 1 2 3 2 4 3 6 0 6 2 2 2 1 2 6 3 0 2 7 2 7 3 4 0 3 2 8 2 3 2 4 0 8 3 8 2 4 2 5 2 5 2 5 2 7 2 ...
result:
ok 1000000 lines
Test #5:
score: 0
Accepted
time: 239ms
memory: 15856kb
input:
10 1000000 6869373857 3130626142 1 3 2 1 8 6 1 8 8 1 3 6 1 1 6 1 1 6 2 5 3 2 5 6 2 4 2 2 5 7 2 5 6 2 4 0 2 5 0 2 5 6 1 3 7 1 3 6 2 7 0 2 1 6 2 1 3 2 7 6 2 5 8 2 6 6 2 5 2 2 5 8 2 3 3 2 2 1 2 2 1 2 3 3 2 4 0 2 5 4 2 5 8 2 4 0 2 6 2 2 1 2 2 1 3 1 1 8 2 3 9 2 3 3 1 1 6 2 5 6 2 7 7 1 4 6 1 1 2 1 1 6 1 4...
output:
5 2 7 2 9 2 9 2 9 0 9 0 6 2 9 2 1 5 0 3 9 3 9 5 3 2 9 2 0 4 9 4 3 2 2 2 9 2 9 2 1 6 3 3 6 6 2 6 0 0 0 0 0 0 0 0 0 0 8 6 2 6 0 0 9 3 9 2 0 2 2 2 6 2 0 2 0 2 9 6 0 8 7 5 5 2 9 2 0 5 9 8 5 2 3 5 5 2 9 2 9 5 9 2 8 2 9 2 7 2 9 2 3 10 8 3 0 3 9 10 8 2 5 2 2 4 6 2 4 4 6 3 3 3 9 3 3 2 5 4 7 2 6 2 8 2 1 3 9 ...
result:
ok 1000000 lines
Test #6:
score: 0
Accepted
time: 356ms
memory: 15936kb
input:
10 1000000 6869373857 3130626142 1 9 6 1 9 5 1 10 8 1 10 7 2 7 8 2 7 6 1 6 8 1 6 7 1 7 8 1 7 3 2 10 4 2 10 2 2 8 3 2 8 1 2 9 7 2 9 4 2 9 9 2 9 4 2 7 7 2 7 6 1 7 4 1 7 3 1 9 6 1 9 5 1 8 9 1 8 8 1 7 5 1 7 3 1 6 9 1 6 7 2 6 8 2 6 2 1 8 9 1 8 8 2 10 6 2 10 2 2 6 9 2 6 2 1 6 9 1 6 7 1 8 9 1 8 8 2 9 7 2 9...
output:
0 10 9 10 0 11 9 11 1 8 9 8 0 7 9 7 4 8 9 8 1 11 9 11 1 9 9 9 2 10 9 10 4 10 9 10 0 8 9 8 0 8 9 8 0 10 9 10 0 9 9 9 1 8 9 8 1 7 9 7 5 7 9 7 0 9 9 9 3 11 9 11 6 7 9 7 1 7 9 7 0 9 9 9 2 10 9 10 2 7 9 7 1 8 9 8 1 11 9 11 4 7 9 7 5 11 9 11 0 7 9 7 0 10 9 10 1 10 9 10 0 7 9 7 2 10 9 10 2 10 9 10 1 11 9 1...
result:
ok 1000000 lines
Test #7:
score: 0
Accepted
time: 1392ms
memory: 73812kb
input:
1000000 1000000 68693738574822907668000669943297325347608140886272616051068251483556534289323531160993017440087302814083329820936792365202060610991343493080865626095241885616863256382251749215319751373247876361270911203617554820406029584474249635378527788208607403822974202545637490373196507887743784...
output:
4 2 6 2 4 2 5 2 7 97772 8 2 0 140233 6 2 5 2 1 2 1 70008 8 2 1 987 0 138405 5 2 6 138113 1 121002 2 35285 4 2 0 2 3 25467 5 2 8 2 4 5543 6 2 1 3862 8 2 3 107304 6 81700 0 0 2 2 0 0 0 15551 5 14120 3 4872 7 2 0 0 6 58933 6 2 9 7954 4 2 4 2 3 63166 0 0 8 38562 1 349 6 10624 3 2 3 2 4 2 8 65159 4 21435...
result:
ok 1000000 lines
Test #8:
score: 0
Accepted
time: 1371ms
memory: 73816kb
input:
1000000 1000000 61693798575862907668150369943297325385708140884272416052068257423550554279326571150943024493087202814853321120702792765522060610138341594081829639894344885616853227782222149213319781393275876306231911209117574815406667384452247691376587753208747407802994802745837490373194507888042646...
output:
9 6 6 4 0 3 0 2 6 2 4 2 9 3 2 3 1 6 3 2 2 2 9 4 0 5 4 2 9 4 0 2 9 3 9 2 6 2 8 0 7 3 8 5 0 0 4 4 9 3 9 3 0 3 4 3 9 2 5 2 9 3 0 0 6 3 1 7 0 3 9 0 0 0 9 2 3 2 0 2 9 3 5 2 6 0 1 2 5 2 9 3 2 0 1 2 9 9 0 3 3 6 9 0 9 3 1 5 0 0 9 2 8 3 0 3 0 2 0 3 1 2 9 2 9 3 0 2 6 3 0 3 9 2 9 2 0 3 3 2 0 3 0 4 6 2 0 2 6 3 ...
result:
ok 1000000 lines
Test #9:
score: 0
Accepted
time: 1470ms
memory: 71752kb
input:
1000000 1000000 68693738574822907668000669943297325347608140886272616051068251483556534289323531160993017440087302814083329820936792365202060610991343493080865626095241885616863256382251749215319751373247876361270911203617554820406029584474249635378527788208607403822974202545637490373196507887743784...
output:
3 958194 6 349300 6 259789 4 2 1 77093 6 2 9 2 8 2 9 2 5 133811 5 2 0 8254 9 0 9 0 9 8254 9 2 4 5608 4 2 3 328452 6 97720 7 8629 0 0 7 13938 9 113207 0 113207 4 2 0 0 4 2 9 2 1 2 6 2 9 2 0 2 0 0 1 2 0 2 0 2 4 2808 9 2808 0 13938 2 206652 0 206652 9 115835 0 115835 0 0 2 2 9 2 2 2 3 2 0 2 0 2 9 8629 ...
result:
ok 1000000 lines
Test #10:
score: 0
Accepted
time: 1873ms
memory: 71748kb
input:
1000000 1000000 68693738574822907668000669943297325347608140886272616051068251483556534289323531160993017440087302814083329820936792365202060610991343493080865626095241885616863256382251749215319751373247876361270911203617554820406029584474249635378527788208607403822974202545637490373196507887743784...
output:
0 832279 9 832279 9 0 9 0 0 754544 9 754544 1 609087 9 609087 4 930049 9 930049 0 809411 9 809411 0 749318 9 749318 0 582458 9 582458 9 0 9 0 0 868657 9 868657 9 0 9 0 2 707359 9 707359 1 869642 9 869642 0 568452 9 568452 0 735732 9 735732 2 568160 9 568160 0 551049 9 551049 1 535285 9 535285 0 8651...
result:
ok 1000000 lines