oj.uz

Submission #865077

# Submission time Handle Problem Language Result Execution time Memory
865077 2023-10-24T05:20:18 Z tkhoi123 Lucky Numbers (RMI19_lucky) C++14
46 / 100
 200 ms 13472 KB 
#define TASK ""
#include <bits/stdc++.h>
using namespace std;
#define el cout << "\n"
#define sz(x) (ll)(x).size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for (ll i = a; i <= (b); ++i)
using ll = long long;
using pi = pair<ll, ll>;
const ll N=2e5+1;
const ll INF=1e9+7;
ll n,q;
ll dp[N*2][2];
char a[N];
ll calc(ll idx,bool cur,bool tight,string &digit)
{
    if(idx==-1)return 1;
    ll mx_dg=tight?digit[idx]-'0':9;
    if(!tight&&dp[idx][cur]!=-1)return dp[idx][cur];
    ll res=0;
    rep(i,0,mx_dg)
    {
        bool n_tight=tight&&i==mx_dg;
        bool n_cur=0;
        if(i==3&&cur)continue;
        if(i==1)n_cur=1;
        (res+=calc(idx-1,n_cur,n_tight,digit))%=INF;
    }
    if(!tight)dp[idx][cur]=res;
    return res;
}
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  if (fopen(TASK ".inp", "r")) {
    freopen(TASK ".inp", "r", stdin);
    freopen(TASK ".out", "w", stdout);
  }
  cin >> n>>q;
  memset(dp,-1,sizeof(dp));
  rep(i,1,n)cin>>a[i];
  string x;
  rep(i,1,n)x+=a[i];
  reverse(all(x));
  cout<<calc(n-1,0,1,x);el;
  while(q--)
  {
      ll type,l,r;cin>>type>>l>>r;
      if(type==1)
      {
          string x;
          rep(i,l,r)x+=a[i];
          reverse(all(x));
          cout<<calc(sz(x)-1,0,1,x);el;
      }
      else
      {
          a[l]=r+'0';
      }
  }
  return 0;
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:35:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     freopen(TASK ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lucky.cpp:36:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     freopen(TASK ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7524 KB Output is correct
2 Correct 122 ms 7764 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 7524 KB Output is correct
2 Correct 122 ms 7764 KB Output is correct
3 Execution timed out 534 ms 13472 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 78 ms 7524 KB Output is correct
8 Correct 122 ms 7764 KB Output is correct
9 Correct 39 ms 7512 KB Output is correct
10 Correct 62 ms 7708 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6744 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 78 ms 7524 KB Output is correct
8 Correct 122 ms 7764 KB Output is correct
9 Execution timed out 534 ms 13472 KB Time limit exceeded
10 Halted 0 ms 0 KB -