Submission #1301991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301991		loom	Tricks of the Trade (CEOI23_trade)	C++20	100 / 100	2977 ms	41924 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], omx[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;
   omx[m] = mx;

   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;
   
   sum = 0;
   in.clear();
   out.clear();
   cl = 1, cr = 1;
   add(1);

   vector<int> vc;
   for(int i = 1; i <= n; i++){
      if(omx[i] == ans) vc.push_back(i);
   }
   vc.push_back(n);

   vector<int> ad[n+1], dl[n+1];

   for(int i = 0; i+1 < vc.size(); i++){
      int l = vc[i];

      for(int r = opt[l]; r <= opt[vc[i+1]]; r++){
         seg(l, r);

         if(sum == ans and r-l+1 >= k){
            int x = *in.begin();
            ad[l].push_back(x);
            dl[r].push_back(x);
         }
      }
   }  

   multiset<int> mn;

   for(int i = 1; i <= n; i++){
      for(int x : ad[i]) mn.insert(x);

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

      for(int x : dl[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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45