fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdint.h>
  4.  
  5. class Crypto {
  6. public:    
  7.     Crypto() {
  8.         sm = cnt = 0;
  9.         seed();
  10.     }
  11.  
  12.     int decode(int z) {
  13.         z ^= next();
  14.         z ^= (next() << 8);
  15.         z ^= (next() << 16);
  16.         z ^= (next() << 22);
  17.         return z;
  18.     }
  19.  
  20.     void query(long long z) {
  21.         const long long B = 425481007;
  22.         const long long MD = 1000000007;
  23.         cnt++;
  24.         sm = ((sm * B % MD + z) % MD + MD) % MD;
  25.         seed();
  26.     }
  27. private: 
  28.     long long sm;
  29.     int cnt;
  30.  
  31.     uint8_t data[256];
  32.     int I, J;
  33.  
  34.     void swap_data(int i, int j) {
  35.         uint8_t tmp = data[i];
  36.         data[i] = data[j];
  37.         data[j] = tmp;    
  38.     }
  39.  
  40.     void seed() {
  41.         uint8_t key[8];
  42.         for (int i = 0; i < 4; i++) {
  43.             key[i] = (sm >> (i * 8));
  44.         }
  45.         for (int i = 0; i < 4; i++) {
  46.             key[i+4] = (cnt >> (i * 8));
  47.         }
  48.  
  49.         for (int i = 0; i < 256; i++) {
  50.             data[i] = i;
  51.         }
  52.         I = J = 0;
  53.  
  54.         int j = 0;
  55.         for (int i = 0; i < 256; i++) {
  56.             j = (j + data[i] + key[i%8]) % 256;
  57.             swap_data(i, j);
  58.         }
  59.     }
  60.  
  61.     uint8_t next() {
  62.         I = (I+1) % 256;
  63.         J = (J + data[I]) % 256;
  64.         swap_data(I, J);
  65.         return data[(data[I] + data[J]) % 256];
  66.     }
  67. };
  68.  
  69. int mod;
  70.  
  71. // 500*100000*8 -> 381MB
  72. struct dp_stack {
  73.   long long dp[100001][500];
  74.   int w[100000];
  75.   int v[100000];
  76.   int sp;
  77. };
  78. dp_stack dp0, dp1;
  79.  
  80. void to(long long *x, long long y) {
  81.   if (*x < y) *x = y;
  82. }
  83.  
  84. int add(int x, int y) {
  85.   x += y;
  86.   if (x >= mod) x -= mod;
  87.   return x;
  88. }
  89.  
  90. void push(dp_stack *dp, int w, int v) {
  91.   for (int i = 0; i < mod; i++) {
  92.     dp->dp[dp->sp + 1][i] = dp->dp[dp->sp][i];
  93.   }
  94.   w %= mod;
  95.   for (int i = 0; i < mod; i++) {
  96.     to(&dp->dp[dp->sp + 1][add(i, w)], dp->dp[dp->sp][i] + v);
  97.   }
  98.   dp->w[dp->sp] = w;
  99.   dp->v[dp->sp] = v;
  100.   dp->sp++;
  101. }
  102.  
  103. int peek_w(dp_stack *dp) {
  104.   return dp->w[dp->sp - 1];
  105. }
  106.  
  107. int peek_v(dp_stack *dp) {
  108.   return dp->v[dp->sp - 1];
  109. }
  110.  
  111. void pop(dp_stack *dp) {
  112.   dp->sp--;
  113. }
  114.  
  115. int get_size(dp_stack *dp) {
  116.   return dp->sp;
  117. }
  118.  
  119. long long merge(long long *L, long long *R, int l, int r) {
  120.   static int qpos[500];
  121.   static long long qval[500];
  122.   int ql = mod;
  123.   int qr = mod;
  124.   int k = mod + r;
  125.   long long ans = -1;
  126.   for (int i = 0; i < mod; i++) {
  127.     while (k > mod + l - i) {
  128.       k--;
  129.       while (ql < qr && qval[ql] <= R[k % mod]) ql++;
  130.       qpos[ql - 1] = k;
  131.       qval[ql - 1] = R[k % mod];
  132.       ql--;
  133.     }
  134.     while (ql < qr && qpos[qr - 1] >= mod + r - i) qr--;
  135.     if (ql < qr) {
  136.       to(&ans, L[i] + qval[qr - 1]);
  137.     }
  138.   }
  139.   return ans;
  140. }
  141.  
  142. int main() {
  143.   int q;
  144.   scanf("%d\n%d", &mod, &q);
  145.   Crypto c;
  146.   for (int i = 1; i < mod; i++) {
  147.     dp0.dp[0][i] = -1e18;
  148.     dp1.dp[0][i] = -1e18;
  149.   }
  150.   while (q--) {
  151.     int t, w, v, l, r;
  152.     scanf("%d %d %d %d %d", &t, &w, &v, &l, &r);
  153.     t = c.decode(t);
  154.     w = c.decode(w);
  155.     v = c.decode(v);
  156.     l = c.decode(l);
  157.     r = c.decode(r);
  158.     if (t == 1) {
  159.       push(&dp0, w, v);
  160.     } else {
  161.       if (get_size(&dp1) == 0) {
  162.         while (get_size(&dp0) > 0) {
  163.           push(&dp1, peek_w(&dp0), peek_v(&dp0));
  164.           pop(&dp0);
  165.         }
  166.       }
  167.       pop(&dp1);
  168.     }
  169.     long long ans = merge(dp0.dp[dp0.sp], dp1.dp[dp1.sp], l, r + 1);
  170.     c.query(ans);
  171.     printf("%lld\n", ans);
  172.   }
  173. }
  174.  
Success #stdin #stdout 0s 798208KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/DIMvq1
language:
C++14 (gcc 8.3)
created:
5 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!