oj.uz

Submission #864385

# Submission time Handle Problem Language Result Execution time Memory
864385 2023-10-22T16:37:54 Z vidut_206_CNH Lucky Numbers (RMI19_lucky) C++14
28 / 100
 200 ms 163924 KB 
#pragma GCC optimize(3)
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC target("avx","sse2")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#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 = 1e5+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<int>> eqal, lower;
	int left, right;
	vidut() : eqal(), lower()  {
		eqal = lower = vector<vector<int>> (3, vector<int>(3, 0));
	}
} st[MAXN1 << 2];
int n,q;
int a[MAXN1];
int M[3][MAXN1][3];

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

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

int 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], int(1LL*L.eqal[u][x]*R.eqal[y][v]%MOD));
					add(res.lower[u][v], int(1LL*L.eqal[u][x]*R.lower[y][v]%MOD));
					add(res.lower[u][v], int(1LL*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],int(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);
	int 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);
			int 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:173:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |   freopen("SMM.inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
lucky.cpp:174:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  174 |   freopen("SMM.out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lucky.cpp:34:13: warning: iteration 100003 invokes undefined behavior [-Waggressive-loop-optimizations]
   34 |  res = (res + val);
      |        ~~~~~^~~~~~
lucky.cpp:184:24: note: within this loop
  184 |   for(int len = 1; len < MAXN1; ++len) {
      |                    ~~~~^~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 163924 KB Output is correct
2 Correct 174 ms 163920 KB Output is correct
3 Correct 179 ms 163924 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 163924 KB Output is correct
2 Correct 174 ms 163920 KB Output is correct
3 Correct 179 ms 163924 KB Output is correct
4 Correct 178 ms 163860 KB Output is correct
5 Correct 177 ms 163904 KB Output is correct
6 Correct 179 ms 163796 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 257 ms 163924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 257 ms 163924 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 163924 KB Output is correct
2 Correct 174 ms 163920 KB Output is correct
3 Correct 179 ms 163924 KB Output is correct
4 Correct 178 ms 163860 KB Output is correct
5 Correct 177 ms 163904 KB Output is correct
6 Correct 179 ms 163796 KB Output is correct
7 Execution timed out 257 ms 163924 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 163924 KB Output is correct
2 Correct 174 ms 163920 KB Output is correct
3 Correct 179 ms 163924 KB Output is correct
4 Correct 178 ms 163860 KB Output is correct
5 Correct 177 ms 163904 KB Output is correct
6 Correct 179 ms 163796 KB Output is correct
7 Execution timed out 257 ms 163924 KB Time limit exceeded
8 Halted 0 ms 0 KB -