fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. int32_t main() {
  6.  
  7.     ios_base::sync_with_stdio(false);
  8.  
  9.     cin.tie(0);
  10.  
  11.     long long n;
  12.  
  13.     cin >> n;
  14.  
  15.     long long k;
  16.  
  17.     cin >> k;
  18.  
  19.     long long diff[4*200005];
  20.  
  21.     memset(diff,0,sizeof diff);
  22.  
  23.     vector<pair<long long,long long> > v;
  24.  
  25.     for(long long i = 0 ; i < k ; i++) {
  26.  
  27.         long long x;
  28.  
  29.         cin >> x;
  30.  
  31.         long long y;
  32.  
  33.         cin >> y;
  34.  
  35.         v.push_back({x,y});
  36.  
  37.     }
  38.  
  39.     diff[0]=0;
  40.  
  41.     diff[1]=1;
  42.  
  43.     long long last=0;
  44.  
  45.     for(long long i=1; i<=n+5; i++) {
  46.  
  47.         if(i>2) {
  48.  
  49.             diff[i]+=diff[i-1];
  50.  
  51.         }
  52.  
  53.         long long cur = diff[i]%998244353;
  54.  
  55.         for(long long j=0; j<v.size(); j++) {
  56.  
  57.             diff[i+v[j].first]+=cur;
  58.  
  59.             diff[i+v[j].second+1]-=cur;
  60.  
  61.         }
  62.  
  63.     }
  64.  
  65.     cout << diff[n]%998244353 << '\n';
  66.  
  67.     return 0;
  68.  
  69. }
  70.  
  71.  
Success #stdin #stdout 0s 9728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/diy5rn
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!