fork(1) download
copy 
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <stack>
  8. #include <bitset>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <utility>
  13. #include <sstream>
  14. #include <iostream>
  15. #include <iomanip>
  16. #include <cstdio>
  17. #include <cmath>
  18. #include <cstdlib>
  19. #include <cctype>
  20. #include <string>
  21. #include <cstring>
  22. #include <cstdio>
  23. #include <cmath>
  24. #include <cstdlib>
  25. #include <ctime>
  26. #include <string.h>
  27. #include <fstream>
  28. #include <cassert>
  29. using namespace std;
  30.  
  31.  
  32. typedef long long ll;
  33. const int M = 1e6;
  34. const ll mod = 1e9 + 7;
  35.  
  36. ll cr[M], cl[M], c[M];
  37.  
  38. struct node {/*{{{*/
  39. public:
  40.   ll m, ml, mr, mm;
  41.   int li, ri;
  42.   void merge(node& l, node& r) {
  43.     li = l.li;
  44.     ri = r.ri;
  45.     ll s = (cr[l.ri] * cl[r.li]) % mod;
  46.     m = (l.m*r.m) % mod;
  47.     m = (m + ((l.ml*r.mr) % mod)*s) % mod;
  48.     ml = (l.m*r.ml) % mod;
  49.     ml = (ml + ((l.ml*r.mm) % mod)*s) % mod;
  50.     mr = (r.m*l.mr) % mod;
  51.     mr = (mr + ((r.mr*l.mm) % mod)*s) % mod;
  52.     mm = (l.mr*r.ml) % mod;
  53.     mm = (mm + ((l.mm*r.mm) % mod)*s) % mod;
  54.   }
  55.   node() {
  56.     li = 0, ri = 0, ml = 1, mr = 1, mm = 0, m = 1;
  57.   }
  58.   void init() {
  59.     li = 0, ri = 0, ml = 1, mr = 1, mm = 0, m = 1;
  60.   }
  61. };/*}}}*/
  62. template<class node>
  63. class segtree {/*{{{*/
  64.   template<bool b>class param {};
  65.   inline void spltdwn(int idx, param<true>) { splt(idx); }
  66.   inline void splt(int idx) {/*{{{*/
  67.     idx >>= 1;
  68.     if (idx>0)splt(idx);
  69.     tree[idx].split(tree[idx << 1], tree[(idx << 1) | 1]);
  70.   }/*}}}*/
  71.   inline void spltdwn(int, param<false>) {};
  72.   inline void split(node& a, node& b, node& c, param<true>) { return a.split(b, c); }
  73.   inline void split(node&, node&, node&, param<false>) {}
  74.   template<typename t, void (t::*)(t&, t&)> class T {};
  75.   template<typename t> static char test(T<t, &t::split>*) { return 0; }
  76.   template<typename t> static long double test(...) { return 0; }
  77.   int u, v;
  78.   node query(int root, int left_range, int right_range) {/*{{{*/
  79.     if (u <= left_range && right_range <= v)
  80.       return tree[root];
  81.     int mid = (left_range + right_range) >> 1,
  82.       l = root << 1,
  83.       r = l | 1;
  84.     if (has_split)split(tree[root], tree[l], tree[r], param<has_split>());
  85.     node res;
  86.     if (u >= mid)res = query(r, mid, right_range);
  87.     else if (v <= mid)res = query(l, left_range, mid);
  88.     else {
  89.       node n1 = query(l, left_range, mid),
  90.         n2 = query(r, mid, right_range);
  91.       res.merge(n1, n2);
  92.     }
  93.     if (has_split) tree[root].merge(tree[l], tree[r]);
  94.     return res;
  95.   }/*}}}*/
  96.   template<void(*fn)(node&)>
  97.   void local_update(int root, int left_range, int right_range) {/*{{{*/
  98.     if (u <= left_range && right_range <= v) {
  99.       return fn(tree[root]);
  100.     }
  101.     int mid = (left_range + right_range) >> 1,
  102.       l = root << 1,
  103.       r = l | 1;
  104.     if (has_split)split(tree[root], tree[l], tree[r], param<has_split>());
  105.     if (v>mid)local_update<fn>(r, mid, right_range);
  106.     if (u<mid)local_update<fn>(l, left_range, mid);
  107.     tree[root].merge(tree[l], tree[r]);
  108.   }/*}}}*/
  109.   void mrgup(int idx) {/*{{{*/
  110.     idx >>= 1;
  111.     while (idx>0)
  112.       tree[idx].merge(tree[idx << 1], tree[(idx << 1) | 1]),
  113.       idx >>= 1;
  114.   }/*}}}*/
  115. public:
  116.   static bool const has_split = (sizeof(test<node>(0)) == sizeof(char));
  117.   int N;
  118.   int leftmost_leaf, rightmost_leaf;
  119.   node* tree;
  120.   node identity;
  121.   segtree() { tree = 0; }
  122.   ~segtree() {
  123.     if (tree) delete[] tree;
  124.   }
  125.   void init(int n, const node a[], const node& identity) {/*{{{*/
  126.     if (tree) delete[] tree;
  127.     this->identity = identity;
  128.     N = 0;
  129.     while ((1 << N)<n)N++;
  130.     leftmost_leaf = 1 << N;
  131.     rightmost_leaf = leftmost_leaf << 1;
  132.     tree = new node[rightmost_leaf];
  133.     for (int i = 0; i<n; i++)
  134.       tree[i + leftmost_leaf] = a[i];
  135.     for (int i = n + leftmost_leaf; i<rightmost_leaf; i++)
  136.       tree[i] = identity;
  137.     for (int i = leftmost_leaf - 1; i; i--)
  138.       tree[i].merge(tree[i << 1], tree[(i << 1) | 1]);
  139.   }/*}}}*/
  140.   node query(int u, int v) {//[u,v]/*{{{*/
  141.     this->u = u + leftmost_leaf;
  142.     this->v = v + leftmost_leaf + 1;
  143.     return query(1, leftmost_leaf, rightmost_leaf);
  144.   }/*}}}*/
  145.   node query(int u) {//faster version of query(u,u)/*{{{*/
  146.                      //indexing starts from 0
  147.     u += leftmost_leaf;
  148.     spltdwn(u, param<has_split>());
  149.     return tree[u];
  150.   }/*}}}*/
  151.   template<void(*fn)(node&)>
  152.   void update(int u, int v) {/*{{{*/
  153.                              //0-indexed
  154.     this->u = u + leftmost_leaf;
  155.     this->v = v + leftmost_leaf + 1;
  156.     return local_update<fn>(1, leftmost_leaf, rightmost_leaf);
  157.   }/*}}}*/
  158.   template<void(*fn)(node&)>
  159.   void update(int u) {//faster version of update(u,u)/*{{{*/
  160.                       //indexing starts from 0
  161.     u += leftmost_leaf;
  162.     spltdwn(u, param<has_split>());
  163.     fn(tree[u]);
  164.     mrgup(u);
  165.   }/*}}}*/
  166.   void split_down(int leaf_idx) {/*{{{*/
  167.     spltdwn(leaf_idx + leftmost_leaf, param<has_split>());
  168.   }/*}}}*/
  169.   void merge_up(int leaf_idx) {/*{{{*/
  170.     mrgup(leaf_idx + leftmost_leaf);
  171.   }/*}}}*/
  172.   bool is_leaf(int tree_idx) { return tree_idx >= leftmost_leaf; }
  173.   int binary_search(node k) {/*{{{*/
  174.                              //search the last place i, such that merge( everyting to the left of i(including i) ) compares less than k
  175.     int root = 1;
  176.     node n = identity;
  177.     //identity satisfies merge(identity,y) = merge(y,identity) = y for all y.
  178.     assert(!(k<identity));
  179.     while (!is_leaf(root)) {
  180.       int left_child = root << 1,
  181.         right_child = left_child | 1;
  182.       if (has_split)
  183.         split(tree[root], tree[left_child], tree[right_child], param<has_split>());
  184.       node m;
  185.       m.merge(n, tree[left_child]);
  186.       if (m<k) {//go to right side
  187.         n = m;
  188.         root = right_child;
  189.       }
  190.       else root = left_child;
  191.     }
  192.     node m;
  193.     m.merge(n, tree[root]);
  194.     mrgup(root);
  195.     if (m<k)return root - leftmost_leaf;
  196.     else return root - 1 - leftmost_leaf;
  197.   }/*}}}*/
  198. };/*}}}*/
  199.  
  200. #define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
  201. #define sz(a) int((a).size())
  202. #define rep(i, s, n)  for(int i = s; i <= (n); ++i)
  203. #define rev(i, n, s)  for(int i = (n); i >= s; --i)
  204. #define fore(x, a) for(auto &&x : a)
  205. const ll inf = mod-7;
  206.  
  207. ll w[M];
  208. ll d[M], zo[M], s[M];
  209.  
  210. node a[M];
  211.  
  212. void upd(node &cur) {
  213.   cur.m = c[cur.li];
  214. }
  215.  
  216. int main() {
  217. #ifdef loc
  218.   if(!freopen((string(FOLDER) + "inp.txt").c_str(), "r", stdin)) {
  219.     assert(0);
  220.   }
  221.   freopen((string(FOLDER) + "out.txt").c_str(), "w", stdout);
  222. #endif
  223.   boost;
  224.   int t;
  225.   cin >> t;
  226.   rep(z, 1, t) {
  227.     cout << "Case #" << z << ": ";
  228.     int n, m;
  229.     cin >> n >> m;
  230.     ll w1, aw, bw;
  231.     cin >> w1 >> aw >> bw;
  232.     w[1] = w1;
  233.     rep(i,2, m) {
  234.       w[i] = ((aw*w[i - 1] + bw) % n) + 1;
  235.     }
  236.     ll d1, ad, bd;
  237.     cin >> d1 >> ad >> bd;
  238.     d[1] = d1;
  239.     rep(i, 2, m) {
  240.       d[i] = (ad*d[i - 1] + bd) % 3;
  241.     }
  242.     rep(i, 1, m) {
  243.       zo[i] = max(1LL, min((ll)n, w[i] + d[i] - 1));
  244.     }
  245.     ll s1, as, bs;
  246.     cin >> s1 >> as >> bs;
  247.     s[1] = s1;
  248.     rep(i, 2, m) {
  249.       s[i] = ((as*s[i - 1] + bs) % inf) + 1;
  250.     }
  251.     rep(i, 0,n+1) {
  252.       a[i].init();
  253.       a[i].li = i;
  254.       a[i].ri = i;
  255.     }
  256.     memset(cl, 0, sizeof(cl));
  257.     memset(cr, 0, sizeof(cr));
  258.     memset(c, 0, sizeof(c));
  259.     rep(i, 1, n) c[i] = 1;
  260.     segtree<node> p;
  261.     p.init(n + 1, a, a[n + 1]);
  262.     int res = 0;
  263.    // cout << p.query(1, n).m << " ";
  264.     rep(i, 1, m) {
  265.       //cout << "(" << w[i] << " " << zo[i] << " " << s[i] << ") ";
  266.       if (w[i] == zo[i]) {
  267.         c[w[i]] += s[i];
  268.         if (c[w[i]] >= mod) c[w[i]] -= mod;
  269.       }
  270.       else if (w[i] == zo[i] - 1) {
  271.         cr[w[i]] += s[i];
  272.         if (cr[w[i]] >= mod) cr[w[i]] -= mod;
  273.       }
  274.       else {
  275.         cl[w[i]] += s[i];
  276.         if (cl[w[i]] >= mod) cl[w[i]] -= mod;
  277.       }
  278.       p.update<&upd>(w[i]);
  279.       res += p.query(1, n).m;
  280.     //  cout << p.query(1, n).m << " ";
  281.       if (res >= mod) res -= mod;
  282.     }
  283.     cout << res << endl;
  284.   }
  285.   return 0;
  286. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Traceback (most recent call last):
  File "<string>", line 1, in <module>
  File "/usr/lib/python2.7/py_compile.py", line 117, in compile
    raise py_exc
py_compile.PyCompileError:   File "prog.py", line 29
    using namespace std;
                  ^
SyntaxError: invalid syntax
stdout
copy 
Standard output is empty
https://ideone.com/Wdrr2g
language:
Python (cpython 2.7.16)
created:
7 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!