oj.uz

Submission #861070

# Submission time Handle Problem Language Result Execution time Memory
861070 2023-10-15T08:47:05 Z MilosMilutinovic Lucky Numbers (RMI19_lucky) C++14
100 / 100
 142 ms 19788 KB 
#include<bits/stdc++.h>

#define pb push_back
#define fi first
#define se second
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;

template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}

int readint(){
	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;
}

const int cys=1000000007;

int mod(ll x){return x%cys;}
void chkadd(int& a,int b){a=mod(a+b);}
int mul(int a,int b){return mod(a*1ll*b);}

int n,q;
char s[100005];

struct info{
	int val[3][2][2];
	void init(){
		for(int i=0;i<3;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) val[i][j][k]=0;
	}
	info(){init();}
}dp[400005];

info operator+ (const info& a,const info& b){
	info ret;
	for(int ia=0;ia<3;ia++){
		for(int ja=0;ja<2;ja++){
			for(int ka=0;ka<2;ka++){
				for(int ib=0;ib<3;ib++){
					for(int jb=0;jb<2;jb++){
						for(int kb=0;kb<2;kb++){
							if(ja==1&&kb==1) continue;
							int i;
							if(ia==2||(ia==1&&ib==2)) i=2;
							else if(ia==1&&ib==1) i=1;
							else i=0;
							chkadd(ret.val[i][jb][ka],mul(a.val[ia][ja][ka],b.val[ib][jb][kb]));
						}
					}
				}
			}
		}
	}
	return ret;
}

void build(int id,int l,int r){
	if(l==r){
		int d=s[l]-'0';
		dp[id].init();
		for(int dig=0;dig<10;dig++){
			dp[id].val[dig<d?0:(dig==d?1:2)][dig==1][dig==3]+=1;
		}
		return;
	}
	int mid=(l+r)/2;
	build(id<<1,l,mid);
	build(id<<1|1,mid+1,r);
	dp[id]=dp[id<<1]+dp[id<<1|1];
}

void change(int id,int l,int r,int p){
	if(l==r){
		int d=s[l]-'0';
		dp[id].init();
		for(int dig=0;dig<10;dig++){
			dp[id].val[dig<d?0:(dig==d?1:2)][dig==1][dig==3]+=1;
		}
		return;
	}
	int mid=(l+r)/2;
	if(p<=mid) change(id<<1,l,mid,p);
	else change(id<<1|1,mid+1,r,p);
	dp[id]=dp[id<<1]+dp[id<<1|1];
}

info query(int id,int l,int r,int ql,int qr){
	if(ql<=l&&r<=qr) return dp[id];
	int mid=(l+r)/2;
	if(qr<=mid) return query(id<<1,l,mid,ql,qr);
	else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr);
	else return query(id<<1,l,mid,ql,qr)+query(id<<1|1,mid+1,r,ql,qr);
}

int solve(int l,int r){
	info nd=query(1,1,n,l,r);
	int res=0;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			for(int k=0;k<2;k++){
				chkadd(res,nd.val[i][j][k]);
			}
		}
	}
	return res;
}

int main(){
	n=readint(); q=readint();
	scanf("%s",s+1);
	build(1,1,n);
	printf("%d\n",solve(1,n));
	while(q--){
		int t=readint();
		if(t==1){
			int l=readint(),r=readint();
			printf("%d\n",solve(l,r));
		}else{
			int p=readint(),d=readint();
			s[p]=(char)(d+'0');
			change(1,1,n,p);
		}
	}
	return 0;
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:119:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |  scanf("%s",s+1);
      |  ~~~~~^~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 19356 KB Output is correct
2 Correct 65 ms 19380 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 19356 KB Output is correct
2 Correct 65 ms 19380 KB Output is correct
3 Correct 105 ms 19472 KB Output is correct
4 Correct 105 ms 19536 KB Output is correct
5 Correct 117 ms 19540 KB Output is correct
6 Correct 129 ms 19544 KB Output is correct
7 Correct 142 ms 19788 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 50 ms 19356 KB Output is correct
8 Correct 65 ms 19380 KB Output is correct
9 Correct 56 ms 19292 KB Output is correct
10 Correct 72 ms 19340 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 19036 KB Output is correct
2 Correct 4 ms 19032 KB Output is correct
3 Correct 5 ms 19036 KB Output is correct
4 Correct 4 ms 19036 KB Output is correct
5 Correct 4 ms 19032 KB Output is correct
6 Correct 4 ms 19036 KB Output is correct
7 Correct 50 ms 19356 KB Output is correct
8 Correct 65 ms 19380 KB Output is correct
9 Correct 105 ms 19472 KB Output is correct
10 Correct 105 ms 19536 KB Output is correct
11 Correct 117 ms 19540 KB Output is correct
12 Correct 129 ms 19544 KB Output is correct
13 Correct 142 ms 19788 KB Output is correct
14 Correct 56 ms 19292 KB Output is correct
15 Correct 72 ms 19340 KB Output is correct
16 Correct 109 ms 19544 KB Output is correct
17 Correct 114 ms 19488 KB Output is correct
18 Correct 122 ms 19548 KB Output is correct
19 Correct 138 ms 19560 KB Output is correct
20 Correct 136 ms 19512 KB Output is correct