Submission #1077552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077552		bleahbleah	Tricks of the Trade (CEOI23_trade)	C++17	50 / 100	7697 ms	39916 KiB

trade

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;
 
using ll = long long;
using ld = long double;
 
#define int ll
#define sz(x) ((int)(x).size())
 
using pii = pair<int,int>;
using tii = tuple<int,int,int>;
 
const int nmax = 25e4 + 5;
 
int K;
 
const ll inf = 1e18;
 
struct KthHeap {
   multiset<int> outside, inside;
   void repair() {
      while(sz(inside) > K) {
         int x = *inside.begin();
         inside.erase(inside.find(x));
         outside.insert(x);
         sum -= x;
      }
      while(sz(inside) < K && sz(outside)) {
         int x = *outside.rbegin();
         outside.erase(outside.find(x));
         inside.insert(x);
         sum += x;
      }
      while(sz(inside) && sz(outside) && *inside.begin() < *outside.rbegin()) {
         int x = *outside.rbegin(), y = *inside.begin();
         outside.erase(outside.find(x));
         inside.erase(inside.find(y));
         outside.emplace(y);
         inside.emplace(x);
         sum += x - y;
      }
      return;
   }
   void erase(int x) {
      if(outside.find(x) != outside.end())
         outside.erase(outside.find(x));
      else if(inside.find(x) != inside.end())
         inside.erase(inside.find(x)), sum -= x;
      else assert(false);
      repair();
   }
   void insert(int x) {
      outside.emplace(x);
      repair();
   }
   ll query() {
      repair();
      if(sz(inside) < K) return -inf;
      return sum;
   }
   void clear() { inside.clear(); outside.clear(); }
   
   private:
      ll sum = 0;
};
 
int bestcut[nmax];
ll dp[nmax];
 
ll spart[nmax];
ll SS[nmax];
ll v[nmax];
ll V[nmax];
 
ll S(int l, int r) { return spart[r] - spart[l - 1]; }
 
namespace Divide {
   KthHeap hint;
   
   void divide(int l, int r) {
      if(l + 1 == r) return;
      int optl = bestcut[l], optr = bestcut[r];
      
      int mid = l + r >> 1;
      if(r <= optl) {
         for(int i = mid; i < r; i++) hint.insert(v[i]);
         ll best = hint.query() - S(mid, optl);
         int atr = optl;
         for(int i = optl + 1; i <= optr; i++) {
            hint.insert(v[i]);
            if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
         }
         bestcut[mid] = atr, dp[mid] = best;
         if(atr - mid + 1 == K) {
            int SA = S(mid, atr), SB = 0;
            for(int i = mid; i <= atr; i++) SB += v[i];
         }
         
         for(int i = optl + 1; i <= optr; i++) hint.erase(v[i]);
         divide(l, mid);
         for(int i = mid; i < r; i++) hint.erase(v[i]);
         for(int i = optl + 1; i <= atr; i++) hint.insert(v[i]);
         divide(mid, r);
         for(int i = optl + 1; i <= atr; i++) hint.erase(v[i]);
      }
      else {
         int border = max(mid - 1, optl);
         for(int i = mid; i <= border; i++) hint.insert(v[i]);
         ll best = hint.query() - S(mid, border), atr = border;
         for(int i = border + 1; i <= optr; i++) {
            hint.insert(v[i]);
            if(hint.query() - S(mid, i) >= best) tie(best, atr) = make_pair(hint.query() - S(mid, i), i);
         }
         
         bestcut[mid] = atr, dp[mid] = best;
         
         for(int i = optr; i > border; i--) hint.erase(v[i]);
         divide(l, mid);
         for(int i = mid; i <= border; i++) hint.erase(v[i]);
         for(int i = r; i <= atr; i++) hint.insert(v[i]);
         divide(mid, r);
         for(int i = r; i <= atr; i++) hint.erase(v[i]);
      }
   }
   
}
 
 
vector<int> solve(int n, bool first = 1) {
   Divide::hint.clear();
   for(int i = 1; i <= n; i++) spart[i] = SS[i] + spart[i - 1], dp[i] = -inf, bestcut[i] = 0;
   bestcut[0] = 0;
   bestcut[n - K + 2] = n;
   Divide::divide(0, n - K + 2);
   ll mx = -inf;
   
   vector<int> possible(n + 1);
   
   
   for(int i = 1; i <= n - K + 1; i++) 
      mx = max(mx, dp[i]);
   if(first)
      cout << mx << '\n';
   
   auto cmp = [&](int a, int b) { return (v[a] < v[b] || (v[a] == v[b] && a < b)); };
   set<int, decltype(cmp)> inside(cmp), outside(cmp);
   
   int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
   
   KthHeap forchristsake;
   
   
   for(int i = 1; i <= n; i++) {
      //cerr << i << ' ' << bestcut[i] << ' ' << forchristsake.query() << '\t';
      //for(auto x : forchristsake.inside) cerr << x << ' ';
      //for(auto x : forchristsake.outside) cerr << x << ' ';
      //cerr << '\n';
      
      for(int j = bestcut[i - 1] + 1; j <= bestcut[i]; j++) {
         forchristsake.insert(v[j]);
         inside.insert(j);
         while(sz(inside) > K && [&]() {
           auto it = inside.begin(), it2 = next(it);
            return v[*it] < v[*it2];
         }()) {
            auto t = *inside.begin();
            if(t <= criteriaIR && v[t] >= criteriaV) possible[t] = 1;
            inside.erase(inside.begin());
            outside.insert(t);
         }
         //cerr << '\t' << i << ' ' << j << ' ' << forchristsake.query() << ' ' << S(i, j) << '\n';
         if(forchristsake.query() - S(i, j) == mx) {            
            criteriaIR = bestcut[i];
            criteriaV = v[*inside.begin()];
         }
      }
      if(dp[i] == mx) {
         criteriaIR = bestcut[i];
         criteriaV = v[*inside.begin()];
         //for(auto x : inside) cerr << x << ' ';
         //cerr << '\n';
         //cerr << criteriaIR << ' ' << criteriaV << '\n';
      }
      
      forchristsake.erase(v[i]);
      if(inside.count(i)) {
         if(criteriaIR >= i && v[i] >= criteriaV) possible[i] = 1;
         inside.erase(i); 
      }
      else if(outside.count(i)) outside.erase(i);
      while(sz(inside) < K && sz(outside)) {
         int a = *outside.rbegin();
         outside.erase(a);
         inside.insert(a);
      }
   }
   
   while(!inside.empty()) {
      int t = *inside.begin();
      //cerr << t << ' ' << (t <= criteriaIR && v[t] >= criteriaV) << '\n';
      if(t <= criteriaIR && v[t] >= criteriaV) possible[t] = 1;
      inside.erase(inside.begin());
   }
   for(int i = n; i > 0; i--) spart[i] -= spart[i - 1];
   
   return possible;
}
 
signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n >> K;
   for(int i = 1; i <= n; i++) {
      cin >> SS[i];
   }
   for(int i = 1; i <= n; i++)
      cin >> v[i], V[i] = v[i];
   //auto T = solve(n, 1);
   reverse(SS + 1, SS + n + 1);
   reverse(V + 1, V + n + 1);
   for(int i = 1; i <= n; i++) v[i] = V[i];
   auto T1 = solve(n, 1);
   for(int i = 1; i <= n; i++) cout << (T1[n - i + 1]);
   cout << '\n';
    
 
}

Compilation message (stderr)

trade.cpp: In function 'void Divide::divide(ll, ll)':
trade.cpp:85:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:96:17: warning: unused variable 'SA' [-Wunused-variable]
   96 |             int SA = S(mid, atr), SB = 0;
      |                 ^~
trade.cpp: In function 'std::vector<long long int> solve(ll, bool)':
trade.cpp:149:8: warning: unused variable 'criteriaIL' [-Wunused-variable]
  149 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |        ^~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 5 / 10
• Subtask 2: 5 / 10
• Subtask 3: 5 / 10
• Subtask 4: 10 / 25
• Subtask 5: 25 / 45