Submission #1301966

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301966		loom	Tricks of the Trade (CEOI23_trade)	C++20	55 / 100	3180 ms	25236 KiB

trade

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define inf (int)2e18
#define nl '\n'

const int N = 250005;
int k, cl, cr, sum, ans = -inf;
int c[N], s[N], opt[N];
multiset<int> in, out;

void add(int i){
   sum -= c[i];
   int x = s[i]; 
   auto it = in.begin();

   if(in.size() < k){
      in.insert(x);
      sum += x;
   }
   else if(x > *it){
      sum -= *it;
      out.insert(*it);
      in.erase(it);
      in.insert(x);
      sum += x;
   }
   else{
      out.insert(x);
   }
}

void del(int i){
   sum += c[i];
   int x = s[i];

   if(out.find(x) != out.end()){
      out.erase(out.find(x));
   }
   else{
      in.erase(in.find(x));
      sum -= x;

      if(!out.empty()){
         auto it = prev(out.end());

         sum += *it;
         in.insert(*it);
         out.erase(it);
      }
   }
}

void seg(int l, int r){
   while(cl < l){
      del(cl);
      cl++;
      
      if(cl > cr){
         cr++;
         add(cr);
      }
   }
   while(cl > l){
      cl--;
      add(cl);
   }
   while(cr < r){
      cr++;
      add(cr);
   }
   while(cr > r){
      del(cr);
      cr--;
   }
}

void solve(int l, int r, int opl, int opr){
   if(l > r) return;
   int m = (l+r)/2;

   seg(m, max(m, opl));
   int mx = -inf, op = opr;

   if(cr-m+1 >= k){
      mx = sum;
      op = cr;
   }
   
   while(cr < opr){
      cr++;
      add(cr);

      if(cr-m+1 >= k and mx < sum){
         mx = sum;
         op = cr;
      }
   }

   ans = max(ans, mx);
   opt[m] = op;

   solve(l, m-1, opl, op);
   solve(m+1, r, op, opr);
}

void solve(){
   int n;
   cin>>n>>k;

   for(int i = 1; i <= n; i++) cin>>c[i];
   for(int i = 1; i <= n; i++) cin>>s[i];

   cl = 1, cr = 1;
   add(1);

   solve(1, n, 1, n);
   cout<<ans<<nl;

   vector<int> rem[n+1];
   multiset<int> mn;
   opt[n+1] = n;
   
   sum = 0;
   in.clear();
   out.clear();
   cl = 1, cr = 1;
   add(1);

   for(int i = 1; i <= n; i++){
      for(int j = opt[i]; j <= opt[i+1]; j++){
         seg(i, j);

         if(sum == ans and j-i+1 >= k){
            int x = *in.begin();
            mn.insert(x);
            rem[j].push_back(x);
         }
      }

      cout<<(!mn.empty() and s[i] >= *mn.begin());

      for(int x : rem[i]) mn.erase(mn.find(x));
   }  
}

signed main(){
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);cout.tie(NULL);

   int t = 1;
   //cin>>t;
   while(t--) solve();

   return 0;
}

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