oj.uz

Submission #258146

# Submission time Handle Problem Language Result Execution time Memory
258146 2020-08-05T12:36:43 Z lyc Lucky Numbers (RMI19_lucky) C++14
28 / 100
 21 ms 1792 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;

const int mxN = 1e5+5;
const int mod = 1e9+7;

int N, Q;
string X;

int f[mxN][2][2];

using Data = array<array<array<int,2>,2>,2>; // bound, start 3, end 1;
struct node {
	int s, e, m;
	Data v;
	node *l, *r;
	
	void setLeaf(char c) {
		X[s] = c;
		v[1][0][0] = (c != '3' && c != '1');
		v[1][0][1] = (c == '1');
		v[1][1][0] = (c == '3');
		v[1][1][1] = 0;
		int u = c-'0';
		v[0][0][0] = u - (c > '3') - (c > '1');
		v[0][0][1] = (c > '1');
		v[0][1][0] = (c > '3');
		v[0][1][1] = 0;
		
		//~ cout << "SET" _ s _ c << " :: ";
		//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << v[x][y][z] << ' ';
		//~ cout << endl;
	}
	
	inline Data merge(int L, int R, Data a, Data b) {
		Data u;
		int lenb = R-m;
		FOR(i,0,1){
			FOR(j,0,1){				
				u[1][i][j]  = (ll) a[1][i][0] * b[1][0][j] % mod;
				u[1][i][j] += (ll) a[1][i][0] * b[1][1][j] % mod;
				u[1][i][j] %= mod;
				u[1][i][j] += (ll) a[1][i][1] * b[1][0][j] % mod;
				u[1][i][j] %= mod;
			}
		}
		FOR(i,0,1){
			FOR(j,0,1){				
				u[0][i][j]  = (ll) a[0][i][0] * f[lenb][0][j] % mod;
				u[0][i][j] += (ll) a[0][i][0] * f[lenb][1][j] % mod;
				u[0][i][j] %= mod;
				u[0][i][j] += (ll) a[0][i][1] * f[lenb][0][j] % mod;
				u[0][i][j] %= mod;
				
				u[0][i][j] += (ll) a[1][i][0] * b[0][0][j] % mod;
				u[0][i][j] %= mod;
				u[0][i][j] += (ll) a[1][i][0] * b[0][1][j] % mod;
				u[0][i][j] %= mod;
				u[0][i][j] += (ll) a[1][i][1] * b[0][0][j] % mod;
				u[0][i][j] %= mod;
			}
		}
		
		//~ cout << "MERGE" _ L _ R << " :: ";
		//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << u[x][y][z] << ' ';
		//~ cout << endl;
		return u;
	}
		
	node(int s, int e): s(s), e(e), m((s+e)/2) {
		if (s == e) setLeaf(X[s]);
		else {
			l = new node(s,m), r = new node(m+1,e);
			v = merge(s,e,l->v,r->v);
		}
		
		//~ cout << s _ e << " :: ";
		//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << v[x][y][z] << ' ';
		//~ cout << endl;
	}
	
	void update(int a, char b) {
		if (s == e) { setLeaf(b); return; }
		else if (a <= m) l->update(a,b);
		else r->update(a,b);
		v = merge(s,e,l->v,r->v);
	}
	
	Data query(int a, int b) {
		if (s == a && e == b) return v;
		if (b <= m) return l->query(a,b);
		if (a > m) return r->query(a,b);
		return merge(s, e, l->query(a,m), r->query(m+1,b));
	}
} *root;

void answer(int L, int R) {
	Data res = root->query(L,R);
	int ans = 0;
	//~ FOR(x,0,1) FOR(y,0,1) FOR(z,0,1) cout << res[x][y][z] << ' ';
	//~ cout << " :: ";
	FOR(a,0,1) FOR(b,0,1) FOR(c,0,1) ans = (ans+res[a][b][c])%mod;
	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	cin >> N >> Q >> X;
	X = '^' + X;
	
	f[0][0][0] = 1;
	f[0][0][1] = f[0][1][0] = f[0][1][1] = 0;
	f[1][0][0] = 8;
	f[1][0][1] = f[1][1][0] = 1;
	f[1][1][1] = 0;
	FOR(i,2,N){
		f[i][0][0]  = (ll) f[i-1][0][0] * 9 % mod;
		f[i][0][0] += (ll) f[i-1][0][1] * 8 % mod;
		f[i][0][0] %= mod;
		f[i][0][1]  = (f[i-1][0][0] + f[i-1][0][1]) % mod;
		
		f[i][1][0]  = (ll) f[i-1][1][0] * 9 % mod;
		f[i][1][0] += (ll) f[i-1][1][1] * 8 % mod;
		f[i][1][0] %= mod;
		f[i][1][1]  = (f[i-1][1][0] + f[i-1][1][1]) % mod;
	}
	root = new node(1,N);
	
	//~ int ans = 0;
	//~ FOR(x,0,1) FOR(y,0,1) {
		//~ ans += f[N][x][y];
		//~ cout << f[N][x][y] << ' ';
	//~ }
	//~ cout << " :: " << ans << endl;
	
	answer(1,N);
	FOR(i,1,Q){
		int T; cin >> T;
		if (T == 1) {
			int L, R; cin >> L >> R;
			//~ TRACE(T _ L _ R);
			answer(L,R);
		} else {
			int P; char D; cin >> P >> D;
			root->update(P,D);
		}
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 1792 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 21 ms 1792 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Incorrect 21 ms 1792 KB Output isn't correct
8 Halted 0 ms 0 KB -