oj.uz

Submission #218012

# Submission time Handle Problem Language Result Execution time Memory
218012 2020-03-31T12:12:09 Z tincamatei Lucky Numbers (RMI19_lucky) C++14
100 / 100
 199 ms 10488 KB 
/**
* user:  tinca-6db
* fname: Matei
* lname: Tinca
* task:  lucky
* score: 100.0
* date:  2019-10-10 09:19:09.769672
*/
#include <bits/stdc++.h>

using namespace std;

const int MOD = 1000000007;
const int MAX_N = 100000;

struct IntMod {
	int val;

	IntMod():val(0) {}
	IntMod(int x):val(x % MOD) {}
	IntMod operator+(IntMod x) {
		if(x.val + val >= MOD)
			return x.val + val - MOD;
		return x.val + val;
	}
	IntMod operator*(IntMod x) {
		return (long long)x.val * val % MOD;
	}
	IntMod operator+(int x) {
		return (*this) + IntMod(x);
	}
	IntMod operator*(int x) {
		return (*this) * IntMod(x);
	}
	IntMod operator-(IntMod x) {
		return (*this) + (MOD - x.val);
	}
	IntMod operator-(int x) {
		return (*this) - IntMod(x);
	}
};

// cate numere bune de forma a1a2...aN exista?
IntMod _goodcnt[1+MAX_N+1], *goodcnt = _goodcnt + 1;

struct AintNode {
	int size;
	IntMod cntgood, cntgood1, cntgood3, cntgood31;
	bool isgood, isgood1, isgood3, isgood31;
};

// cntgood = numar chestii bune pe interval
// cntgood1 = numar chestii bune pe interval care se termina cu 1
// cntgood3 = numar chestii bune pe interval care incep cu 3
// cntgood31 = numar chestii bune pe interval care incep cu 3 si se termina cu 1

AintNode combine(AintNode a, AintNode b) {
	AintNode rez;

	rez.isgood = a.isgood && b.isgood && !(a.isgood1 && b.isgood3);
	rez.isgood1 = b.isgood1 && a.isgood && !(a.isgood1 && b.isgood3);
	rez.isgood3 = a.isgood3 && b.isgood && !(a.isgood1 && b.isgood3);
	rez.isgood31 = a.isgood3 && b.isgood1 && !(a.isgood1 && b.isgood3);

	rez.cntgood = (a.cntgood - a.isgood) * goodcnt[b.size] + b.cntgood * a.isgood -
	              (a.cntgood1 - a.isgood1) * goodcnt[b.size - 1] - b.cntgood3 * a.isgood1;
	rez.cntgood1 = (a.cntgood - a.isgood) * goodcnt[b.size - 1] + b.cntgood1 * a.isgood -
	               (a.cntgood1 - a.isgood1) * goodcnt[b.size - 2] - b.cntgood31 * a.isgood1;
	rez.cntgood3 = (a.cntgood3 - a.isgood3) * goodcnt[b.size] + b.cntgood * a.isgood3 -
	               (a.cntgood31 - a.isgood31) * goodcnt[b.size - 1] - b.cntgood3 * a.isgood31;
	rez.cntgood31 = (a.cntgood3 - a.isgood3) * goodcnt[b.size - 1] + b.cntgood1 * a.isgood3 -
	                (a.cntgood31 - a.isgood31) * goodcnt[b.size - 2] - b.cntgood31 * a.isgood31;
	rez.size = a.size + b.size;
	return rez;
}

AintNode aint[1+4*MAX_N];

void update(int poz, AintNode val, int l = 1, int r = MAX_N, int nod = 1) {
	if(r < poz || poz < l) return;

	if(l == r)
		aint[nod] = val;
	else {
		int mid = (l + r) / 2;
		update(poz, val, l, mid, 2 * nod);
		update(poz, val, mid + 1, r, 2 * nod + 1);
		aint[nod] = combine(aint[2 * nod], aint[2 * nod + 1]);
	}
}

AintNode query(int i, int j, int l = 1, int r = MAX_N, int nod = 1) {
	if(i <= l && r <= j)
		return aint[nod];
	else {
		int mid = (l + r) / 2;
		if(i > mid)
			return query(i, j, mid + 1, r, 2 * nod + 1);
		else if(j <= mid)
			return query(i, j, l, mid, 2 * nod);
		else
			return combine(query(i, j, l, mid, 2 * nod),
			               query(i, j, mid + 1, r, 2 * nod + 1));
	}
}

void dfs(int nod = 1, int l = 1, int r = MAX_N) {
	printf("RANGE: %d %d->%d\n", l, r, nod);
	printf("isgood: %d %d %d %d", aint[nod].isgood, aint[nod].isgood1, aint[nod].isgood3, aint[nod].isgood31);
	printf("cntgood: %d %d %d %d\n", aint[nod].cntgood.val, aint[nod].cntgood1.val, aint[nod].cntgood3.val, aint[nod].cntgood31.val);
	
	int mid = (l + r) / 2;
	if(l < r) {
		dfs(2 * nod, l, mid);
		dfs(2 * nod + 1, mid + 1, r);
	}
}

// AintNode = {size, cntgood, cntgood1, cntgood3, cntgood31, isgood, isgood1, isgood3, isgood31}
AintNode updDigit[10] = {
{1, IntMod(1), IntMod(0), IntMod(0), IntMod(0), true, false, false, false}, // 0
{1, IntMod(2), IntMod(1), IntMod(0), IntMod(0), true, true , false, false}, // 1
{1, IntMod(3), IntMod(1), IntMod(0), IntMod(0), true, false, false, false}, // 2
{1, IntMod(4), IntMod(1), IntMod(1), IntMod(0), true, false, true , false}, // 3
{1, IntMod(5), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 4
{1, IntMod(6), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 5
{1, IntMod(7), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 6
{1, IntMod(8), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 7
{1, IntMod(9), IntMod(1), IntMod(1), IntMod(0), true, false, false, false}, // 8
{1, IntMod(10),IntMod(1), IntMod(1), IntMod(0), true, false, false, false}  // 9
};

char getChar(FILE *fin) {
	char ch = fgetc(fin);
	while(!isdigit(ch))
		ch = fgetc(fin);
	return ch;
}

int main() {
	int N, Q;
	goodcnt[0] = 1;
	for(int i = 1; i <= MAX_N; ++i)
		goodcnt[i] = goodcnt[i - 1] * 10 - goodcnt[i - 2];

	scanf("%d%d", &N, &Q);
	for(int i = 1; i <= N; ++i)
		update(i, updDigit[getChar(stdin) - '0']);
	
	printf("%d\n", query(1, N).cntgood.val);
	for(int i = 0; i < Q; ++i) {
		int t, x, y;
		scanf("%d%d%d", &t, &x, &y);
		if(t == 2)
			update(x, updDigit[y]);
		else
			printf("%d\n", query(x, y).cntgood.val);
	}

	return 0;
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
lucky.cpp:153:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &t, &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10240 KB Output is correct
2 Correct 42 ms 10360 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 10240 KB Output is correct
2 Correct 42 ms 10360 KB Output is correct
3 Correct 169 ms 10384 KB Output is correct
4 Correct 154 ms 10360 KB Output is correct
5 Correct 168 ms 10384 KB Output is correct
6 Correct 196 ms 10488 KB Output is correct
7 Correct 199 ms 10488 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10112 KB Output is correct
2 Correct 11 ms 10112 KB Output is correct
3 Correct 11 ms 10112 KB Output is correct
4 Correct 10 ms 10112 KB Output is correct
5 Correct 11 ms 10112 KB Output is correct
6 Correct 11 ms 10112 KB Output is correct
7 Correct 36 ms 10240 KB Output is correct
8 Correct 42 ms 10360 KB Output is correct
9 Correct 37 ms 10240 KB Output is correct
10 Correct 46 ms 10232 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 10112 KB Output is correct
2 Correct 11 ms 10112 KB Output is correct
3 Correct 11 ms 10112 KB Output is correct
4 Correct 10 ms 10112 KB Output is correct
5 Correct 11 ms 10112 KB Output is correct
6 Correct 11 ms 10112 KB Output is correct
7 Correct 36 ms 10240 KB Output is correct
8 Correct 42 ms 10360 KB Output is correct
9 Correct 169 ms 10384 KB Output is correct
10 Correct 154 ms 10360 KB Output is correct
11 Correct 168 ms 10384 KB Output is correct
12 Correct 196 ms 10488 KB Output is correct
13 Correct 199 ms 10488 KB Output is correct
14 Correct 37 ms 10240 KB Output is correct
15 Correct 46 ms 10232 KB Output is correct
16 Correct 158 ms 10488 KB Output is correct
17 Correct 152 ms 10360 KB Output is correct
18 Correct 174 ms 10360 KB Output is correct
19 Correct 195 ms 10488 KB Output is correct
20 Correct 192 ms 10360 KB Output is correct