oj.uz

Submission #270519

# Submission time Handle Problem Language Result Execution time Memory
270519 2020-08-17T17:20:09 Z eohomegrownapps Lucky Numbers (RMI19_lucky) C++14
100 / 100
 160 ms 35704 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> Data;

int arr[100000];
ll m = 1000000007;

void init(int ind, ll ans[4][4]){
	//Data ans = vector<vector<ll>>(4,vector<ll>(4,0));
	for (int x = 0; x<4; x++){
		for (int y = 0; y<4; y++){
			ans[x][y]=0;
		}
		bool isEq = x/2;
		bool was1 = x%2;
		for (int i = 0; i<=(isEq?arr[ind]:9); i++){
			if (was1 && i==3){continue;}
			ans[x][(i==arr[ind]&&isEq)*2+(i==1)]++;
		}
	}
	//return ans;
}

void combine(ll a[4][4], ll b[4][4], ll ans[4][4]){
	//Data ans = vector<vector<ll>>(4,vector<ll>(4,0));
	for (int r = 0; r<4; r++){
		for (int c = 0; c<4; c++){
			ans[r][c]=0;
			ans[r][c]+=a[r][0]*b[0][c];ans[r][c]%=m;
			ans[r][c]+=a[r][1]*b[1][c];ans[r][c]%=m;
			ans[r][c]+=a[r][2]*b[2][c];ans[r][c]%=m;
			ans[r][c]+=a[r][3]*b[3][c];ans[r][c]%=m;
			//cout<<ans[r][c]<<' ';
		}//cout<<'\n';
	}//cout<<'\n';
	//return ans;
}

struct Node{
	int s,e,m;
	ll v[4][4];
	Node *l, *r;
	Node(int _s, int _e){
		s=_s;e=_e;
		m=(s+e)/2;
		if (s==e){
			init(s,v);
			return;
		}
		l = new Node(s,m);
		r = new Node(m+1,e);
		combine(l->v, r->v, v);
	}

	void update(int ind, int val){
		if (s==e){
			arr[ind]=val;
			init(ind,v);
			return;
		}
		if (ind<=m){
			l->update(ind, val);
		} else {
			r->update(ind, val);
		}
		combine(l->v, r->v, v);
	}

	void query(int a, int b, ll ans[4][4]){
		if (s==a&&e==b){
			for (int x = 0; x<4; x++){
				for (int y = 0; y<4; y++){
					ans[x][y]=v[x][y];
				}
			}
			return;
			//return v;
		}
		if (b<=m){
			l->query(a,b,ans);
			return;
		} else if (m<a){
			r->query(a,b,ans);
			return;
		} else {
			ll av[4][4];
			ll bv[4][4];
			l->query(a,m,av);
			r->query(m+1,b,bv);
			combine(av,bv,ans);
		}
	}
};

Node *root;

ll ans(int a, int b){
	ll ad[4][4];
	root->query(a,b,ad);
	return (ad[2][0]+ad[2][1]+ad[2][2]+ad[2][3])%m;
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	int n,q;
	cin>>n>>q;
	string s;
	cin>>s;
	for (int i = 0; i<n; i++){
		arr[i]=s[i]-'0';
	}
	root = new Node(0,n-1);
	cout<<ans(0,n-1)<<'\n';
	for (int i = 0; i<q; i++){
		int t;
		cin>>t;
		if (t==1){
			int a,b;
			cin>>a>>b;
			a--;b--;
			cout<<ans(a,b)<<'\n';
		} else {
			int ind,val;
			cin>>ind>>val;
			ind--;
			root->update(ind,val);
		}
	}
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3200 KB Output is correct
2 Correct 59 ms 3960 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 3200 KB Output is correct
2 Correct 59 ms 3960 KB Output is correct
3 Correct 128 ms 28408 KB Output is correct
4 Correct 117 ms 28536 KB Output is correct
5 Correct 134 ms 31992 KB Output is correct
6 Correct 148 ms 35704 KB Output is correct
7 Correct 149 ms 35576 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 45 ms 3200 KB Output is correct
8 Correct 59 ms 3960 KB Output is correct
9 Correct 50 ms 3320 KB Output is correct
10 Correct 63 ms 3964 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 45 ms 3200 KB Output is correct
8 Correct 59 ms 3960 KB Output is correct
9 Correct 128 ms 28408 KB Output is correct
10 Correct 117 ms 28536 KB Output is correct
11 Correct 134 ms 31992 KB Output is correct
12 Correct 148 ms 35704 KB Output is correct
13 Correct 149 ms 35576 KB Output is correct
14 Correct 50 ms 3320 KB Output is correct
15 Correct 63 ms 3964 KB Output is correct
16 Correct 120 ms 28536 KB Output is correct
17 Correct 122 ms 28536 KB Output is correct
18 Correct 136 ms 31992 KB Output is correct
19 Correct 153 ms 35704 KB Output is correct
20 Correct 160 ms 35576 KB Output is correct