Advertisement
savrasov

problem_F

Jun 26th, 2017
353
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. ll u;
  2.  
  3. struct DSU
  4. {
  5.     vector<int> par, rank;
  6.     int m;
  7.     void build()
  8.     {
  9.         par.resize(m);
  10.         rank.resize(m);
  11.         for (int i = 0; i < m; i++)
  12.             make(i);
  13.     }
  14.     int find(int v) { return ((v == par[v]) ? v : par[v] = find(par[v])); }
  15.     void paint(int l, int r, int col)
  16.     {
  17.         for (int i = l;;)
  18.         {
  19.             i = find(i);
  20.             if (i >= r) return;
  21.             u += col;
  22.             par[i] = i + 1;
  23.         }
  24.     }
  25. };
  26.  
  27. DSU b;
  28. int a[20000000], c[10000000];
  29.  
  30. int main()
  31. {
  32.     ios_base::sync_with_stdio(0);
  33.     cin.tie();
  34.     cout.tie();
  35.     //freopen("input.txt", "r", stdin);
  36.     //freopen("output.txt", "w", stdout);
  37.     int n, m, k, x, y, z;
  38.     cin >> n >> m >> a[1] >> a[2] >> c[1] >> x >> y >> z;
  39.     b.m = n + 9;
  40.     b.build();
  41.     for (int i = 3; i <= 2 * m; i++)
  42.         a[i] = (x * 1ll * a[i - 2] + y * 1ll * a[i - 1] + z) % n + 1;
  43.     for (int i = 2; i <= m; i++)
  44.         c[i] = (x * 1ll * c[i - 1] + z * 1ll * y) % n + 1;
  45.     for (int i = m; i > 0; i--)
  46.         b.paint(min(a[i * 2 - 1], a[i * 2]), max(a[i * 2 - 1], a[i * 2]) + 1, c[i]);
  47.     cout << u;
  48.     return 0;
  49. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement