pastebin

Paste Search Dynamic
Recent pastes
ordered set
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. #define all(v) v.begin(), v.end()
  6. #define ll long long
  7. #define el 'n'
  8. #define hanou2a ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  9. const int N = 2e5 + 10, mod2 = 998244353, I = 101, M = 1e8;
  10. using namespace std;
  11. using namespace __gnu_pbds;
  12. template<typename T>
  13. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  14.  
  15. void func() {
  16.     string s;
  17.     cin >> s;
  18.     int n = s.size();
  19.     ll cur = 0, pw = 1;
  20.     ll suf[N] = {0};
  21.     vector<int> v[2020];
  22.     v[0].push_back(n);
  23.     for (int i = n - 1; i >= 0; i--) {
  24.         cur = (cur + (pw * (s[i] - '0')));
  25.         pw = (pw * 10) % 2019;
  26.         suf[i] = cur % 2019;
  27.         v[cur % 2019].push_back(i);
  28.     }
  29.     ll ans = 0;
  30.     for (int i = 0; i < 2020; i++) {
  31.         if (v[i].empty())continue;
  32.         int l = v[i].size();
  33.         for (int j = 0; j < v[i].size(); j++) {
  34.             ans += (v[i].size() - (j + 1));
  35.         }
  36.     }
  37.     cout << ans << el;
  38. }
  39.  
  40. int main() {
  41.     int T;
  42.     T = 1;
  43.     //cin >> T;
  44.     for (int tt = 1; tt <= T; tt++) {
  45.         //  cout << "Case #" << tt << ": ";
  46.         func();
  47.     }
  48.     return 0;
  49. }
Parsed in 0.008 seconds