Submission #1077408

#	Time	Username	Problem	Language	Result	Execution time	Memory
1077408		bleahbleah	Tricks of the Trade (CEOI23_trade)	C++17	10 / 100	8095 ms	19084 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;
   }
   
   private:
      ll sum = 0;
};
 
ll dp[nmax];
 
ll spart[nmax];
ll v[nmax];
 
ll S(int l, int r) { return spart[r] - spart[l - 1]; }
 
namespace DivideM {
   int bestcut[nmax];
   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]);
      }
   }
   
}
 
 
namespace Dividem {
   int bestcut[nmax];
   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]);
      }
   }
   
}
 
 
signed main() {
   cin.tie(0) -> sync_with_stdio(0);
   int n;
   cin >> n >> K;
   for(int i = 1; i <= n; i++) {
      cin >> spart[i];
      spart[i] += spart[i - 1];
   }
   for(int i = 1; i <= n; i++)
      cin >> v[i];
      
   DivideM::bestcut[0] = Dividem::bestcut[0] = 0;
   DivideM::bestcut[n - K + 2] = Dividem::bestcut[n - K + 2] = n;
   DivideM::divide(0, n - K + 2);
   Dividem::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]);
   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;
   
   for(int i = 1; i <= n; i++) {
      if(dp[i] != mx) continue;
      set<int, decltype(cmp)> kth(cmp);
      assert(DivideM::bestcut[i] >= Dividem::bestcut[i]);
      for(int j = i; j < DivideM::bestcut[i]; j++) {
         kth.emplace(j);
      }
      auto repair = [&]() {
         while(sz(kth) > K && v[*kth.begin()] < v[*next(kth.begin())]) {
            kth.erase(kth.begin());
         }
         return;
      };
      for(int j = DivideM::bestcut[i]; j <= DivideM::bestcut[i]; j++) {
         kth.emplace(j);
         repair();
         for(auto x : kth) possible[x] = 1;
      }
      
   }
   
   
   for(int i = 1; i <= n; i++) cout << possible[i];
   cout << '\n';
 
}
 
 
/**
      Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/ 

Compilation message (stderr)

trade.cpp: In function 'void DivideM::divide(ll, ll)':
trade.cpp:82:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:93:17: warning: unused variable 'SA' [-Wunused-variable]
   93 |             int SA = S(mid, atr), SB = 0;
      |                 ^~
trade.cpp: In function 'void Dividem::divide(ll, ll)':
trade.cpp:135:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  135 |       int mid = l + r >> 1;
      |                 ~~^~~
trade.cpp:146:17: warning: unused variable 'SA' [-Wunused-variable]
  146 |             int SA = S(mid, atr), SB = 0;
      |                 ^~
trade.cpp: In function 'int main()':
trade.cpp:207:8: warning: unused variable 'criteriaIL' [-Wunused-variable]
  207 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |        ^~~~~~~~~~
trade.cpp:207:28: warning: unused variable 'criteriaIR' [-Wunused-variable]
  207 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |                            ^~~~~~~~~~
trade.cpp:207:45: warning: unused variable 'criteriaV' [-Wunused-variable]
  207 |    int criteriaIL = n + 1, criteriaIR = -1, criteriaV = inf;
      |                                             ^~~~~~~~~

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