fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef long long ll;
  6. typedef pair < int, int > ii;
  7.  
  8. const int N = 1e6 + 5;
  9.  
  10. int n, s, m, k;
  11. int p[N], d[N];
  12. ii a[N];
  13. ll dp[N];
  14. map < int, int > M;
  15.  
  16. ll tree[N << 2], lazy[N << 2];
  17.  
  18. void doit(int x, ll v) {
  19.   lazy[x] += v;
  20.   tree[x] += v;
  21. }
  22.  
  23. void push(int x) {
  24.   doit(x + x, lazy[x]);
  25.   doit(x + x + 1, lazy[x]);
  26.   lazy[x] = 0;
  27. }
  28.  
  29. void init(int x, int l, int r) {
  30.   lazy[x] = 0;
  31.   tree[x] = 1e18;
  32.   if(l == r)
  33.     return;
  34.   int m = (l + r) >> 1;
  35.   init(x + x, l, m);
  36.   init(x + x + 1, m + 1, r);
  37. }
  38.  
  39. void update(int x, int l, int r, int x1, ll d) {
  40.   if(x1 <= l and r <= x1) {
  41.     tree[x] = d;
  42.     return;
  43.   }
  44.   push(x);
  45.   int m = (l + r) >> 1;
  46.   if(x1 <= m)
  47.     update(x + x, l, m, x1, d);
  48.   else
  49.     update(x + x + 1, m + 1, r, x1, d);
  50.   tree[x] = min(tree[x + x], tree[x + x + 1]);
  51. }
  52.  
  53. void update(int x, int l, int r, int x1, int x2, ll d) {
  54.   if(x2 < l or r < x1)
  55.     return;
  56.   if(x1 <= l and r <= x2) {
  57.     doit(x, d);
  58.     return;
  59.   }
  60.   push(x);
  61.   int m = (l + r) >> 1;
  62.   update(x + x, l, m, x1, x2, d);
  63.   update(x + x + 1, m + 1, r, x1, x2, d);
  64.   tree[x] = min(tree[x + x], tree[x + x + 1]);
  65. }
  66.  
  67. ll query(int x, int l, int r, int x1, int x2) {
  68.   if(x1 <= l and r <= x2)
  69.     return tree[x];
  70.   int m = (l + r) >> 1;
  71.   push(x);
  72.   if(x1 <= m) {
  73.     if(x2 > m)
  74.       return min(query(x + x, l, m, x1, x2), query(x + x + 1, m + 1, r, x1, x2));
  75.     return query(x + x, l, m, x1, x2);
  76.   }
  77.   return query(x + x + 1, m + 1, r, x1, x2);
  78. }
  79.  
  80. void solve() {
  81.   M.clear();
  82.   scanf("%d %d %d %d", &n, &s, &m, &k);
  83.   n = 0;
  84.   for(int i = 1; i <= k; i++) {
  85.     int l, a1, x, y, z;
  86.     scanf("%d %d %d %d %d", &l, &a1, &x, &y, &z);
  87.     p[++n] = a1;
  88.     for(int it = 0; it < l - 1; it++) {
  89.       p[n + 1] = ((ll) p[n] * x + y) % z + 1;
  90.       n++;
  91.     }
  92.   }
  93.   n = 0;
  94.   for(int i = 1; i <= k; i++) {
  95.     int l, a1, x, y, z;
  96.     scanf("%d %d %d %d %d", &l, &a1, &x, &y, &z);
  97.     d[++n] = a1;
  98.     for(int it = 0; it < l - 1; it++) {
  99.       d[n + 1] = ((ll) d[n] * x + y) % z + 1;
  100.       n++;
  101.     }
  102.   }
  103.   for(int i = 1; i <= n; i++) {
  104.     M[p[i]] = max(M[p[i]], d[i]);
  105.   }
  106.   n = 0;
  107.   for(auto x : M)
  108.     a[++n] = {x.first, x.second};
  109.   dp[n + 1] = 0;
  110.   init(1, 1, n);
  111.   update(1, 1, n, n, 0);
  112.   vector < ii > vs;
  113.   vs.push_back({n + 1, 1e9 + 333});
  114.   for(int i = n; i >= 1; i--) {
  115.     dp[i] = 1e18;
  116.     // int mx = 0;
  117.     // for(int j = i; j <= n; j++) {
  118.     //   if(a[j].first - a[i].first > 2 * m)
  119.     //     break;
  120.     //   mx = max(mx, a[j].second);
  121.     //   dp[i] = min(dp[i], dp[j + 1] + mx);
  122.     // }
  123.     while(vs.back().second <= a[i].second) {
  124.       int L = vs.back().first;
  125.       int R = vs[vs.size() - 2].first - 1;
  126.       update(1, 1, n, L, R, -vs.back().second);
  127.       vs.pop_back();
  128.     }
  129.     update(1, 1, n, i, vs.back().first - 1, a[i].second);
  130.     vs.push_back({i, a[i].second});
  131.     int j = lower_bound(a + 1, a + n + 1, ii(a[i].first + m + m + 1, 0)) - a - 1;
  132.     dp[i] = query(1, 1, n, i, j);
  133.     dp[i] += s;
  134.     if(i > 1)
  135.       update(1, 1, n, i - 1, dp[i]);
  136.   }
  137.   printf("%lld\n", dp[1]);
  138. }
  139.  
  140. int main() {
  141.   freopen("in.txt", "r", stdin);
  142.   freopen("out.txt", "w", stdout);
  143.   int tt;
  144.   scanf("%d", &tt);
  145.   for(int t = 1; t <= tt; t++) {
  146.     printf("Case #%d: ", t);
  147.     solve();
  148.   }
  149.   return 0;
  150. }
  151.  
Success #stdin #stdout 0s 4372KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/8w07Sk
language:
C++14 (clang 8.0)
created:
6 years ago
visibility:
public

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!