Submission #476189

#TimeUsernameProblemLanguageResultExecution timeMemory
476189iulia13Lucky Numbers (RMI19_lucky)C++14
0 / 100
110 ms262148 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e5 + 5; const int mod = 1e9 + 7; int n, q; char s[N]; int dp[N]; struct ura{ int cnt, cnt1, cnt3, cnt31, are1, are3, are31, eok, nr; ///cnt -> cate cu prop aia } seg[N * 4]; ura join(ura a, ura b) { ura rez; rez.are1 = rez.are31 = rez.are3 = rez.cnt1 = rez.cnt31 = rez.cnt3 = rez.cnt = rez.eok = rez.nr = 0; if (!(a.are1 && b.are3)) { if (a.eok && b.eok) rez.eok = 1; if (a.are3 && b.are1) rez.are31 = 1; if (a.are3 && b.eok) rez.are3 = 1; if (b.are1 && a.eok) rez.are1 = 1; } rez.cnt = (a.cnt - a.eok) * dp[b.nr] + a.eok * b.cnt - (a.cnt1 - a.are1) * dp[b.nr - 1] - b.cnt3 * a.are1; rez.cnt1 = (a.cnt - a.eok) * dp[b.nr - 1] + b.cnt1 * a.eok - (a.cnt1 - a.are1) * dp[b.nr - 2] - b.cnt31 * a.are1; rez.cnt3 = (a.cnt3 - a.are3) * dp[b.nr] + b.cnt * a.are3 - (a.cnt31 - a.are31) * dp[b.nr - 1] - b.cnt3 * a.are31; rez.cnt31 = (a.cnt3 - a.are3) * dp[b.nr - 1] + b.cnt1 * a.are3 - (a.cnt31 - a.are31) * dp[b.nr - 2] - b.cnt31 * a.are31; rez.nr = a.nr + b.nr; return rez; } int adun(int a, int b) { int c = a + b; if (c >= mod) c -= mod; return c; } int inm(int a, int b) { ll aa = a; ll bb = b; ll c = aa * bb; c = c % mod; return c; } int scad(int a, int b) { int c = a - b; if (c < 0) c += mod; return c; } void leaf(int nod, int val) { seg[nod].are1 = seg[nod].are31 = seg[nod].are3 = seg[nod].cnt1 = seg[nod].cnt3 = seg[nod].cnt31 = 0; seg[nod].nr = 1; seg[nod].eok = 1; if (val == 1) seg[nod].are1 = 1; if (val == 3) seg[nod].are3 = 1; if (1 <= val) seg[nod].cnt1 = 1; if (3 <= val) seg[nod].cnt3 = 1; seg[nod].cnt = val + 1; return; } void upd(int nod, int l, int r, int poz, int val) { if (l == r) { leaf(nod, val); return; } int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1; if (poz <= mid) upd(ls, l, mid, poz, val); else upd(rs, 1 + mid, r, poz, val); seg[nod] = join(seg[ls], seg[rs]); } ura qry(int nod, int l, int r, int ql, int qr) { if (ql <= l && r <= qr) return seg[nod]; int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1; if (mid < ql) return qry(rs, mid + 1, r, ql, qr); else if (qr <= mid) return qry(ls, l, mid, ql, qr); else return join(qry(ls, l, mid, ql, qr), qry(rs, mid + 1, r, ql, qr)); } void build(int nod, int l, int r) { if (l == r) { leaf(nod, s[l] - '0'); return; } int mid = (l + r) / 2, ls = 2 * nod, rs = ls + 1; build(ls, l, mid); build(rs, mid + 1, r); seg[nod] = join(seg[ls], seg[rs]); } int main() { freopen("x.in", "r", stdin); freopen("x.out", "w", stdout); cin >> n >> q; cin >> s + 1; dp[0] = 1; dp[1] = 10; for (int i = 2; i <= n; i++) dp[i] = scad(inm(dp[i - 1], 10) , dp[i - 2]); build(1, 1, n); cout << qry(1, 1, n, 1, n).cnt << '\n'; while (q--) { int t, a, b; cin >> t >> a >> b; if (t == 1) { cout << qry(1, 1, n, a, b).cnt << '\n'; continue; } upd(1, 1, n, a, b); } return 0; }

Compilation message (stderr)

lucky.cpp: In function 'int main()':
lucky.cpp:121:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  121 |     cin >> s + 1;
      |            ~~^~~
lucky.cpp:118:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |     freopen("x.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
lucky.cpp:119:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |     freopen("x.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...