oj.uz

Submission #864373

# Submission time Handle Problem Language Result Execution time Memory
864373 2023-10-22T16:08:39 Z vidut_206_CNH Lucky Numbers (RMI19_lucky) C++14
46 / 100
 182 ms 50848 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define gcd(a,b) (__gcd(a,b))
#define lcm(a,b) (a/gcd(a,b)*b)
#define sz(x) (int)(x.size())
#define fast_cin() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define db(x) cerr << "[" << "Line " << __LINE__ << " : " << (#x) << " = " << x << "] "

typedef pair<int,int> pii;

const int MOD = 1e9 + 7;
const int MAXN1 = 3e4+5;
const int MAXN2 = 1e6+5;

mt19937_64 rng(time(0));

template<class T> 
void add(T &res, T val) {
	res = (res + val);
	if(res > MOD) res -= MOD;
}


template<class T>
void sub(T &res, T val) {
	res = (res - val + MOD);
	if(res > MOD) res -= MOD;
}

template<class T>
void maximize(T &res, T val) {
	res = max(res, val);
}

template <class T>
void minimize(T &res, T val) {
	res = min(res, val);
}

struct vidut{
	vector<vector<long long>> eqal, lower;
	int left, right;
	vidut() : eqal(), lower()  {
		eqal = lower = vector<vector<long long>> (3, vector<long long>(3, 0));
	}
} st[MAXN1 << 2];
int n,q;
int a[MAXN1];
long long M[3][MAXN1][3];

void pp(vidut &X) {
	X.eqal = X.lower = vector<vector<long long>> (3, vector<long long>(3, 0));
}

int bn(int x) {
	if(x == 1) return 1;
	if(x == 3) return 2;
	return 0;
}

long long haha(int x, int y, int l, int r) {
	return M[x][r - l + 1][y];
}

vidut merge(vidut L, vidut R) {
	vidut res;
	res.left = L.left;
	res.right = R.right;
	for(int u = 0; u < 3; ++u) {
		for(int v = 0; v < 3; ++v) {
			for(int x = 0; x < 3; ++x) {
				for(int y = 0; y < 3; ++y) {
					if(x == 1 && y == 2) continue;
					add(res.eqal[u][v], L.eqal[u][x]*R.eqal[y][v]%MOD);
					add(res.lower[u][v], L.eqal[u][x]*R.lower[y][v]%MOD);
					add(res.lower[u][v], L.lower[u][x]*haha(y, v, R.left, R.right)%MOD);
				}
			}
		}
	}
	
	return res;
}

void build(int id = 1, int l = 1, int r = n) {
	if(l == r) {
		pp(st[id]);
		st[id].left = st[id].right = l;
		
		for(int c = 0; c <= a[l]; ++c) {
			int g = bn(c);
			
			if(c == a[l]) {
				st[id].eqal[g][g]++;
			}
			else {
				st[id].lower[g][g]++;
			}
		}
		return;
	}
	
	int mid = (l + r) >> 1;
	build(id << 1, l, mid);
	build(id << 1|1, mid + 1, r);
	
	st[id] = merge(st[id << 1], st[id << 1|1]);
}


void update(int id, int l, int r, int pos, int val) {
	if(l == r) {
		pp(st[id]);
		for(int c = 0; c <= val; ++c) {
			int g = bn(c);
			
			if(c == val) {
				st[id].eqal[g][g]++;
			}
			
			else st[id].lower[g][g]++;
		}
		
		
		return; 
	}
	
	int mid = (l + r) >> 1;
	if(pos <= mid) update(id << 1, l, mid, pos, val);
	else update(id << 1|1, mid + 1, r , pos, val);
	
	st[id] = merge(st[id << 1], st[id << 1|1]);
}

vidut get(int id, int l, int r, int u, int v) {
	if(u <= l && r <= v) {
		return st[id];
	}
	
	int mid = (l + r) >> 1;
	
	if(u <= mid && mid < v) {
		return merge(get(id << 1, l, mid, u, v), get(id << 1|1, mid + 1, r, u, v));
	}
	
	if(u <= mid) return get(id << 1, l, mid, u, v);
	return get(id << 1|1, mid + 1, r, u, v);
}




int main() {
	fast_cin();
	
	
	if(ifstream("SMM.inp")) {
		freopen("SMM.inp", "r", stdin);
		freopen("SMM.out", "w", stdout);
	}
	
	cin >> n >> q;
	
	M[0][1][0] = 8;
	M[1][1][1] = 1;
	M[2][1][2] = 1;
	
	for(int f = 0; f < 3; ++f) {
		for(int len = 1; len < MAXN1; ++len) {
			for(int s = 0; s < 3; ++s) {
				long long val = M[f][len][s];
				
				for(int news = 0; news < 3; ++news) {
					if(s == 1 && news == 2) continue;
					
					add(M[f][len + 1][news], 1LL*(news == 0 ? 8 : 1)*val%MOD);
				}
			}
		}
	}
	
	for(int i = 1; i <= n; ++i) {
		char c;
		cin >> c;
		a[i] = c - '0';
	}
	
	build();
	
	vidut res = get(1, 1, n, 1, n);
	
	long long tot = 0;
	
	for(int x = 0; x < 3; ++x) {
		for(int y = 0; y < 3; ++y) {
			add(tot, res.eqal[x][y]);
			add(tot, res.lower[x][y]);
		}
	}
	
	cout << tot << "\n";
	
	for(int i = 1; i <= q; ++i) {
		int type;
		cin >> type;
		if(type == 1) {
			int u,v;
			cin >> u >> v;
			vidut res = get(1, 1, n, u, v);
			long long tot = 0;
			for(int x = 0; x < 3; ++x) {
				for(int y = 0; y < 3; ++y) {
					add(tot, res.eqal[x][y]);
					add(tot, res.lower[x][y]);
				}
			}
			
			cout << tot << "\n";
		}
		else {
			int pos,val;
			cin >> pos >> val;
			update(1, 1, n, pos, val);
		}
	}
	
	
	
	
	
	#ifndef LOCAL
    cerr << "\nTime elapsed: " << 1.0 * (double)clock() / CLOCKS_PER_SEC << " s.\n ";
    #endif
	
	return 0;
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:161:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |   freopen("SMM.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
lucky.cpp:162:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |   freopen("SMM.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 50768 KB Output is correct
2 Correct 50 ms 50516 KB Output is correct
3 Correct 58 ms 50532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 50768 KB Output is correct
2 Correct 50 ms 50516 KB Output is correct
3 Correct 58 ms 50532 KB Output is correct
4 Correct 51 ms 50332 KB Output is correct
5 Correct 51 ms 50512 KB Output is correct
6 Correct 50 ms 50516 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 50556 KB Output is correct
2 Correct 168 ms 50848 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 50556 KB Output is correct
2 Correct 168 ms 50848 KB Output is correct
3 Incorrect 57 ms 50516 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 50768 KB Output is correct
2 Correct 50 ms 50516 KB Output is correct
3 Correct 58 ms 50532 KB Output is correct
4 Correct 51 ms 50332 KB Output is correct
5 Correct 51 ms 50512 KB Output is correct
6 Correct 50 ms 50516 KB Output is correct
7 Correct 129 ms 50556 KB Output is correct
8 Correct 168 ms 50848 KB Output is correct
9 Correct 152 ms 50552 KB Output is correct
10 Correct 182 ms 50632 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 50768 KB Output is correct
2 Correct 50 ms 50516 KB Output is correct
3 Correct 58 ms 50532 KB Output is correct
4 Correct 51 ms 50332 KB Output is correct
5 Correct 51 ms 50512 KB Output is correct
6 Correct 50 ms 50516 KB Output is correct
7 Correct 129 ms 50556 KB Output is correct
8 Correct 168 ms 50848 KB Output is correct
9 Incorrect 57 ms 50516 KB Output isn't correct
10 Halted 0 ms 0 KB -