Submission #218012

#	Time	Username	Problem	Language	Result	Execution time	Memory
218012		tincamatei	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	199 ms	10488 KiB

lucky

/**
* 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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27