fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int N, K, Q;
  5. vector<int> values(1), weights(1), changes;
  6. map< int, vector<int> > queries;
  7. vector<long long> answers;
  8.  
  9. struct segment { int l, r, v, w; };
  10.  
  11. void evolve(vector<int> &knapsack, int v, int w) {
  12. 	for (int k=K; k>=w; --k) knapsack[k] = max( knapsack[k], v + knapsack[k-w] );
  13. }
  14.  
  15. long long output(const vector<int> &knapsack) {
  16.     long long answer = 0;
  17.     for (int k=K; k>=1; --k) answer = (answer*10000019 + knapsack[k]) % 1000000007;
  18.     return answer;
  19. }
  20.  
  21. void solve(int lo, int hi, const vector<segment> &segments, vector<int> knapsack) {
  22.     if (hi-lo <= 1) return;
  23.  
  24.     // find all segments we can already add to knapsack
  25.     vector<segment> remains;
  26.     for (const auto &seg : segments) {
  27.         if (seg.l <= lo && seg.r >= hi-1) {
  28.             evolve( knapsack, seg.v, seg.w );
  29.         } else {
  30.             remains.push_back(seg);
  31.         }
  32.     }
  33.  
  34.     // solve for med if needed
  35.     int med = (lo+hi) / 2;
  36.     if (queries.count(med)) {
  37.         vector<int> med_knapsack = knapsack;
  38.         for (const auto &seg : remains) {
  39.             if (seg.l < med && seg.r >= med) {
  40.                 evolve( med_knapsack, seg.v, seg.w );
  41.             }
  42.         }
  43.         long long curr = output(med_knapsack);
  44.         for (int q : queries[med]) answers[q] = curr;
  45.     }
  46.  
  47.     // make recursive calls
  48.     vector<segment> left, right;
  49.     for (const auto &seg : remains) {
  50.         if (seg.l < med) left.push_back(seg);
  51.         if (seg.r > med) right.push_back(seg);
  52.     }
  53.     solve( lo, med, left, knapsack );
  54.     solve( med, hi, right, knapsack );
  55. }
  56.  
  57. int main() {
  58.     cin >> N >> K;
  59.     for (int n=0; n<N; ++n) {
  60.         int v, w; cin >> v >> w;
  61.         values.push_back(v);
  62.         weights.push_back(w);
  63.         changes.push_back( +(n+1) );
  64.     }
  65.     cin >> Q;
  66.     for (int q=0; q<Q; ++q) {
  67.         int t; cin >> t;
  68.         if (t == 1) {
  69.             int v, w; cin >> v >> w;
  70.             values.push_back(v);
  71.             weights.push_back(w);
  72.             changes.push_back( +(values.size()-1) );
  73.         }
  74.         if (t == 2) {
  75.             int x; cin >> x;
  76.             changes.push_back( -x );
  77.         }
  78.         if (t == 3) {
  79.             queries[ changes.size() ].push_back(q);
  80.         }
  81.     }
  82.  
  83.     answers.resize(Q,-1);
  84.  
  85.     N = values.size();
  86.     vector<int> starts(N), ends(N,-1);
  87.     for (unsigned i=0; i<changes.size(); ++i)
  88.     	if (changes[i]>0) starts[changes[i]]=i; else ends[-changes[i]]=i;
  89.     for (int n=1; n<=N; ++n) if (ends[n]==-1) { ends[n] = changes.size(); changes.push_back(-n); }
  90.  
  91.     vector<segment> segments;
  92.     for (int n=1; n<N; ++n) segments.push_back( { starts[n], ends[n], values[n], weights[n] } );
  93.  
  94.     for (int q : queries[ changes.size() ]) answers[q] = 0;
  95.  
  96.     solve( 0, changes.size(), segments, vector<int>(K+1,0) );
  97.  
  98.     for (auto a : answers) if (a != -1) cout << a << endl;
  99. }
Success #stdin #stdout 0s 3424KB
comments (?)
stdin
copy 
3 10
30 4
60 6
5 1
9
3
1 42 5
1 20 3
3
2 2
2 4
3
1 40 6
3
stdout
copy 
556674384
168191145
947033915
181541912
https://ideone.com/h6Bb0c
language:
C++14 (gcc 8.3)
created:
8 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!