oj.uz

Submission #258555

# Submission time Handle Problem Language Result Execution time Memory
258555 2020-08-06T06:14:41 Z errorgorn Lucky Numbers (RMI19_lucky) C++14
100 / 100
 41 ms 8320 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

ll MAX(ll a){return a;}
ll MIN(ll a){return a;}
template<typename... Args>
ll MAX(ll a,Args... args){return max(a,MAX(args...));}
template<typename... Args>
ll MIN(ll a,Args... args){return min(a,MIN(args...));}

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

const int MOD=1000000007;

int n,q;
int arr[100005];

int memo[100005][2];

int dp(int i,int flag){ //prev is 1, flag=1, else flag=0
	if (i==0) return 1;
	if (memo[i][flag]!=-1) return memo[i][flag];
	
	int ans=0;
	rep(x,0,10){
		if (flag && x==3) continue;
		ans=(ans+dp(i-1,x==1))%MOD;
	}
	
	return memo[i][flag]=ans;
}

int get(int l,int r){
	int len=r-l;
	int ans=0;
	
	int flag=0;
	rep(x,l,r+1){
		rep(y,0,arr[x]){
			if (flag && y==3) continue;
			ans=(ans+dp(len,y==1))%MOD;
		}
		
		if (arr[x]==1) flag=1;
		else if (flag && arr[x]==3) return ans;
		else flag=0;
		len--;
	}
	
	return (ans+1)%MOD;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	memset(memo,-1,sizeof(memo));
	
	cin>>n>>q;
	
	string s;
	cin>>s;
	rep(x,0,n) arr[x]=s[x]-'0';
	
	cout<<get(0,n-1)<<endl;
	
	int a,b;
	while (q--){
		cin>>a;
		
		if (a==2){
			cin>>a>>b;
			arr[a-1]=b;
		}
		else{
			cin>>a>>b;
			cout<<get(a-1,b-1)<<endl;
		}
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1792 KB Output is correct
2 Correct 33 ms 2048 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 1792 KB Output is correct
2 Correct 33 ms 2048 KB Output is correct
3 Correct 38 ms 6832 KB Output is correct
4 Correct 33 ms 6912 KB Output is correct
5 Correct 38 ms 7680 KB Output is correct
6 Correct 41 ms 8320 KB Output is correct
7 Correct 41 ms 8312 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 21 ms 1792 KB Output is correct
8 Correct 33 ms 2048 KB Output is correct
9 Correct 14 ms 1848 KB Output is correct
10 Correct 17 ms 1920 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1152 KB Output is correct
2 Correct 1 ms 1152 KB Output is correct
3 Correct 1 ms 1152 KB Output is correct
4 Correct 1 ms 1152 KB Output is correct
5 Correct 1 ms 1152 KB Output is correct
6 Correct 1 ms 1152 KB Output is correct
7 Correct 21 ms 1792 KB Output is correct
8 Correct 33 ms 2048 KB Output is correct
9 Correct 38 ms 6832 KB Output is correct
10 Correct 33 ms 6912 KB Output is correct
11 Correct 38 ms 7680 KB Output is correct
12 Correct 41 ms 8320 KB Output is correct
13 Correct 41 ms 8312 KB Output is correct
14 Correct 14 ms 1848 KB Output is correct
15 Correct 17 ms 1920 KB Output is correct
16 Correct 28 ms 6912 KB Output is correct
17 Correct 33 ms 6912 KB Output is correct
18 Correct 26 ms 7552 KB Output is correct
19 Correct 30 ms 8312 KB Output is correct
20 Correct 31 ms 8320 KB Output is correct