oj.uz

Submission #271890

# Submission time Handle Problem Language Result Execution time Memory
271890 2020-08-18T07:55:39 Z egekabas Lucky Numbers (RMI19_lucky) C++14
28 / 100
 73 ms 41216 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
ll mod = 1e9+7;
struct node{
    ll small = 0, small1 = 0, small3 = 0, small13 = 0;
    ll big = 0, big1 = 0, big3 = 0, big13 = 0;
    ll eq = 0, eq1 = 0, eq3 = 0, eq13 = 0;
    ll empty = 0;
    node(){
        empty = 1;
    }
    node(ll val){
        small = val;
        if(val > 1) small1 = 1;
        if(val > 3) small3 = 1;
        
        big = 9-val;
        if(val < 1) big1 = 1;
        if(val < 3) big3 = 1;

        eq = 1;
        if(val == 1) eq1 = 1;
        if(val == 3) eq3 = 1;
    }
};
node merge(node a, node b){
    if(a.empty) return b;
    if(b.empty) return a;
    node ret;
    ret.empty = 0;
    ret.small = a.small*(b.small+b.big+b.eq)%mod-a.small1*(b.small3+b.big3+b.eq3)%mod;
    ret.small1 = a.small*(b.small1+b.big1+b.eq1)%mod-a.small1*(b.small13+b.big13+b.eq13)%mod;
    ret.small3 = a.small3*(b.small+b.big+b.eq)%mod-a.small13*(b.small3+b.big3+b.eq3)%mod;
    ret.small13 = a.small3*(b.small1+b.big1+b.eq1)%mod-a.small13*(b.small13+b.big13+b.eq13)%mod;
    
    ret.small += a.eq*b.small%mod-a.eq1*b.small3%mod;
    ret.small1 += a.eq*b.small1%mod-a.eq1*b.small13%mod;
    ret.small3 += a.eq3*b.small%mod-a.eq13*b.small3%mod;
    ret.small13 += a.eq3*b.small1%mod-a.eq13*b.small13%mod;

    ret.big = a.big*(b.small+b.big+b.eq)%mod-a.big1*(b.small3+b.big3+b.eq3)%mod;
    ret.big1 = a.big*(b.small1+b.big1+b.eq1)%mod-a.big1*(b.small13+b.big13+b.eq13)%mod;
    ret.big3 = a.big3*(b.small+b.big+b.eq)%mod-a.big13*(b.small3+b.big3+b.eq3)%mod;
    ret.big13 = a.big3*(b.small1+b.big1+b.eq1)%mod-a.big13*(b.small13+b.big13+b.eq13)%mod;
    
    ret.big += a.eq*b.big%mod-a.eq1*b.big3%mod;
    ret.big1 += a.eq*b.big1%mod-a.eq1*b.big13%mod;
    ret.big3 += a.eq3*b.big%mod-a.eq13*b.big3%mod;
    ret.big13 += a.eq3*b.big1%mod-a.eq13*b.big13%mod;
    
    ret.eq = a.eq*b.eq%mod-a.eq1*b.eq3%mod;
    ret.eq1 = a.eq*b.eq1%mod-a.eq1*b.eq13%mod;
    ret.eq3 = a.eq3*b.eq%mod-a.eq13*b.eq3%mod;
    ret.eq13 = a.eq3*b.eq1%mod-a.eq13*b.eq13%mod;
    
    ret.small += mod;
    ret.small1 += mod;
    ret.small3 += mod;
    ret.small13 += mod;
    ret.big += mod;
    ret.big1 += mod;
    ret.big3 += mod;
    ret.big13 += mod;
    ret.eq += mod;
    ret.eq1 += mod;
    ret.eq3 += mod;
    ret.eq13 += mod;
    
    ret.small %= mod;
    ret.small1 %= mod;
    ret.small3 %= mod;
    ret.small13 %= mod;
    ret.big %= mod;
    ret.big1 %= mod;
    ret.big3 %= mod;
    ret.big13 %= mod;
    ret.eq %= mod;
    ret.eq1 %= mod;
    ret.eq3 %= mod;
    ret.eq13 %= mod;   
    return ret; 
}
node seg[400009];
string s;
void build(ll v, ll tl, ll tr){
    if(tl == tr){
        seg[v] = node(s[tl]-'0');
        //cout << tl << ' ' << s[tl]-'0' << '\n';
        return;
    }
    build(2*v, tl, (tl+tr)/2);
    build(2*v+1, (tl+tr)/2+1, tr);
    seg[v] = merge(seg[2*v], seg[2*v+1]);
}
void upd(ll v, ll tl, ll tr, ll idx, ll val){
    if(idx < tl || idx > tr) return;
    if(idx == tl && idx == tr)
        seg[v] = node(val);
    else{
        upd(2*v, tl, (tl+tr)/2, idx, val);
        upd(2*v+1, (tl+tr)/2+1, tr, idx, val);
        seg[v] = merge(seg[2*v], seg[2*v+1]);
    }
}
node get(ll v, ll tl, ll tr, ll l, ll r){
    if(r < tl || tr < l) return node();
    if(l <= tl && tr <= r){
        return seg[v];
    }
    else{
        return merge(
            get(2*v, tl, (tl+tr)/2, l, r),
            get(2*v+1, (tl+tr)/2+1, tr, l, r)  
        );
    }
}

ll n, q;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> q;
    cin >> s;
    build(1, 0, n-1);
    cout << (seg[1].small+seg[1].eq)%mod << '\n';  
    while(q--){
        ll t, x, y;
        cin >> t >> x >> y;
        if(t == 1){
            --x;
            --y;
            //cout << x << ' ' << y << '\n';
            node cur = get(1, 0, n-1, x, y);
            cout << (cur.small+cur.eq)%mod << '\n';
        }
        else{
            --x;
            upd(1, 0, n-1, x, y);
        }
    }  
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41088 KB Output is correct
2 Correct 24 ms 41088 KB Output is correct
3 Correct 29 ms 41080 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41088 KB Output is correct
2 Correct 24 ms 41088 KB Output is correct
3 Correct 29 ms 41080 KB Output is correct
4 Correct 23 ms 41088 KB Output is correct
5 Correct 31 ms 41080 KB Output is correct
6 Correct 26 ms 41080 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 41216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 73 ms 41216 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41088 KB Output is correct
2 Correct 24 ms 41088 KB Output is correct
3 Correct 29 ms 41080 KB Output is correct
4 Correct 23 ms 41088 KB Output is correct
5 Correct 31 ms 41080 KB Output is correct
6 Correct 26 ms 41080 KB Output is correct
7 Incorrect 73 ms 41216 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 41088 KB Output is correct
2 Correct 24 ms 41088 KB Output is correct
3 Correct 29 ms 41080 KB Output is correct
4 Correct 23 ms 41088 KB Output is correct
5 Correct 31 ms 41080 KB Output is correct
6 Correct 26 ms 41080 KB Output is correct
7 Incorrect 73 ms 41216 KB Output isn't correct
8 Halted 0 ms 0 KB -