fork download
copy 
  1. // ROOT : DRAGON3012009 : Wa In Real Life
  2. #include <bits/stdc++.h>
  3. #define ll long long
  4. #define el "\n"
  5. #define _ROOT_ int main()
  6. #define FOR(i,l,r) for(int i = l ; i <= r ; i ++)
  7. #define FORD(i,r,l) for(int i = r ; i >= l ; i --)
  8. #define REP(i, a ) for(int i = 0 ; i < a ; i ++ )
  9. #define fi first
  10. #define se second
  11. #define M 1000000007
  12. #define MAXN 1000010
  13. #define INF (1ll<<60)
  14. #define NAME "ORDER"
  15. #define compare(v) sort((v).begin(), (v).end()); (v).erase(unique((v).begin(), (v).end()), (v).end());
  16. using namespace std;
  17.  
  18. const ll MOD[] = {(ll)1e9 + 2277, (ll)1e9 + 5277, (ll)1e9 + 8277, (ll)1e9 + 9277, (ll) 1e9 + 7 };
  19. const ll NMOD = 1;
  20.  
  21. ll q, n;
  22. ll a[MAXN], b[MAXN], c[MAXN];
  23. ll wa1[MAXN], wb1[MAXN], wc1[MAXN], wa[MAXN], wb[MAXN], wc[MAXN];
  24. ll cnt[MAXN], posA[MAXN], posB[MAXN], f[MAXN], posF[MAXN];
  25. ll swA[MAXN], swB[MAXN], swC[MAXN];
  26. ll x, y, z;
  27.  
  28. ll u[MAXN], v[MAXN];
  29. ll res[MAXN];
  30.  
  31. void prepare(){
  32.     REP(i, MAXN) {
  33.         posA[i] = MAXN;
  34.         posB[i] = MAXN;
  35.     }
  36.     FORD(i, n - 1, 0) {
  37.         posA[a[i]] = i;
  38.         posB[b[i]] = i;
  39.     }
  40.  
  41.     x = n; y = n; z = n;
  42.     FOR(i, 0, n) {
  43.         if(i == n || cnt[a[i]]) {
  44.             x = i;
  45.             REP(j, i) cnt[a[j]]--;
  46.             break;
  47.         }
  48.         cnt[a[i]] ++ ;
  49.     }
  50.     FOR(i, 0, n) {
  51.         if(i == n || cnt[b[i]]) {
  52.             y = i;
  53.             REP(j, i) cnt[b[j]]--;
  54.             break;
  55.         }
  56.         cnt[b[i]] ++ ;
  57.     }
  58.     FOR(i, 0, n) {
  59.         if(i == n || cnt[c[i]]) {
  60.             z = i;
  61.             REP(j, i) cnt[c[j]]--;
  62.             break;
  63.         }
  64.         cnt[c[i]] ++ ;
  65.     }
  66.  
  67.     ll tmp = y;
  68.     FOR(i, 0, x) {
  69.         f[i] = tmp;
  70.         if(i < n) {
  71.             tmp = min(tmp, posB[a[i]]);
  72.         }
  73.     }
  74.     FOR(i, 0, x) posF[f[i]] = i;
  75.     FORD(i, n - 1, 0) {
  76.         posF[i] = max(posF[i], posF[i + 1]);
  77.     }
  78.  
  79.     ll pA = x, pB = y;
  80.     FOR(i, 0, z) {
  81.         u[i] = pA;
  82.         v[i] = pB;
  83.         if(i == n || cnt[c[i]]) {
  84.             REP(j, i) cnt[c[j]] -- ;
  85.             break;
  86.         }
  87.         cnt[c[i]] ++ ;
  88.         pA = min(pA, posA[c[i]]);
  89.         pB = min(pB, posB[c[i]]);
  90.     }
  91. }
  92.  
  93. void solve_query(bool first = false) {
  94.     ll sumA = 0, sumB = 0, sumC = 0;
  95.     FOR(i, 1, n) {
  96.         sumA += wa[i - 1];
  97.         sumB += wb[i - 1];
  98.         sumC += wc[i - 1];
  99.         swA[i] = max(swA[i - 1], sumA);
  100.         swB[i] = max(swB[i - 1], sumB);
  101.         swC[i] = max(swC[i - 1], sumC);
  102.     }
  103.     if(first) {
  104.         prepare();
  105.     }
  106.     ll l = x, r = 0;
  107.     FORD(i, z, 0) {
  108.         res[i] = res[i + 1];
  109.         while(r <= x && r <= u[i]) {
  110.             if(l < r) res[i] = max(res[i], swA[r] + swB[f[r]]);
  111.             ++r;
  112.         }
  113.         while(l >= 0 && f[l] <= v[i]){
  114.             if (l < r) res[i] = max(res[i], swA[l] + swB[f[l]]);
  115.             --l;
  116.         }
  117.         if(v[i] <= f[u[i]]){
  118.             res[i] = max(res[i], swA[u[i]] + swB[v[i]]);
  119.         } else {
  120.             res[i] = max(res[i], swA[posF[v[i]]] + swB[v[i]]);
  121.         }
  122.     }
  123.     ll ans = -INF;
  124.     FOR(i, 0, z){
  125.         res[i] += swC[i];
  126.         ans = max(ans, res[i]);
  127.     }
  128.     cout << ans << el;
  129. }
  130.  
  131. void init() {
  132.     cin >> q;
  133.     cin >> n;
  134.  
  135.     REP(i, n) cin >> a[i];
  136.     REP(i, n) cin >> wa[i];
  137.     REP(i, n) cin >> b[i];
  138.     REP(i, n) cin >> wb[i];
  139.     REP(i, n) cin >> c[i];
  140.     REP(i, n) cin >> wc[i];
  141.     REP(i, n){
  142.         wa1[i] = wa[i];
  143.         wb1[i] = wb[i];
  144.         wc1[i] = wc[i];
  145.     }
  146. }
  147.  
  148. void solve() {
  149.     solve_query(true);
  150.     FOR(cnt, 2, q) {
  151.         ll e, s;
  152.         cin >> e >> s;
  153.         REP(i, n) {
  154.             wa[i] = (((wa1[i] + (1 << 20)) ^ e) + s) % (1 << 21) - (1 << 20);
  155.             wb[i] = (((wb1[i] + (1 << 20)) ^ e) + s) % (1 << 21) - (1 << 20);
  156.             wc[i] = (((wc1[i] + (1 << 20)) ^ e) + s) % (1 << 21) - (1 << 20);
  157.         }
  158.         solve_query();
  159.     }
  160. }
  161.  
  162. _ROOT_ {
  163. //        freopen(NAME".INP", "r", stdin);
  164. //        freopen(NAME".OUT", "w", stdout);
  165.     ios_base::sync_with_stdio(0);
  166.     cin.tie(0);
  167.     cout.tie(0);
  168.     int t = 1;
  169.     while(t--) {
  170.         init();
  171.         solve();
  172.     }
  173.     return (0&0);
  174. }
  175.  
Success #stdin #stdout 0.01s 32244KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/0MgQoo
language:
C++14 (gcc 8.3)
created:
2 hours 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!