QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#608268#6836. A Plus B ProblemDixiky_215TL 484ms16028kbC++144.3kb2024-10-03 20:17:212024-10-03 20:17:22

Judging History

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

  • [2024-10-03 20:17:22]
  • 评测
  • 测评结果：TL
  • 用时：484ms
  • 内存：16028kb
查看
  • [2024-10-03 20:17:21]
  • 提交

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;
}
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 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 l=2,r=id-1,loc=-1,mid;
    		while(l<=r)
    		{
    			mid=(l+r)>>1;
    			int maxk=ask_max(1,mid,id-1);
    			int mink=ask_min(1,mid,id-1);
    			if(maxk==0&&mink==0) loc=mid,r=mid-1;
    			else l=mid+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);
			modify(1,loc-1,loc-1,sk-1);
		}
		else if(nowl+cha>=10)
		{
			int aim=nowl+cha-10;
    		modify(1,id,id,aim);
    		ans++;
    		
    		int l=2,r=id-1,loc=-1,mid;
    		while(l<=r)
    		{
    			mid=(l+r)>>1;
    			int maxk=ask_max(1,mid,id-1);
    			int mink=ask_min(1,mid,id-1);
    			if(maxk==9&&mink==9) loc=mid,r=mid-1;
    			else l=mid+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);
			modify(1,loc-1,loc-1,sk+1);
		}
		else
		{
//			if(kkk==3) cerr<<"  asd"<<endl;
			int aim=nowl+cha;
    		modify(1,id,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

*/
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 15872kb

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: 0ms
memory: 15940kb

input:

1 1
1
1
1 1 9

output:

0 2

result:

ok single line: '0 2'

Test #3:

score: 0
Accepted
time: 268ms
memory: 16028kb

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: 292ms
memory: 15956kb

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: 284ms
memory: 15900kb

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: 484ms
memory: 15956kb

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: -100
Time Limit Exceeded

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:
English 繁體中文 简体中文

服务器时间: 2024-12-03 00:36:51 | 开源项目