Submission #1114861

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114861		epicci23	Carnival Tickets (IOI20_tickets)	C++17	11 / 100	27 ms	37968 KiB

tickets

#include "bits/stdc++.h"
#include "tickets.h"
#define ll long long
#define all(v) v.begin() , v.end()
#define sz(a) (ll)a.size()
using namespace std;

const ll N = 3e6 + 5;
const ll LOG = 21;

ll fw[N],fw2[N];

inline void add(ll c,ll u,ll u2){
  for(;c<N;c+=c&-c){
    fw[c]+=u;
    fw2[c]+=u2;
  }
}

inline ll query(ll k,ll res=0,ll p=0){
  for(ll i=LOG-1;i>=0;i--){
    if(fw2[p+(1LL<<i)]<=k){
      p+=(1LL<<i);
      k-=fw2[p+(1LL<<i)];
      res+=fw[p];
    }
  }
  return res;
}

ll find_maximum(int _k, vector<vector<int>> _x){
  
  ll n=sz(_x),m=sz(_x[0]),k=_k;
  ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;

  vector<vector<int>> ANS(n,vector<int>(m,-1));

  for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) ar[i][j] = _x[i-1][j-1];

  for(ll i=1;i<=n;i++){
    l[i]=1;
    r[i]=m;
  }

  for(ll i=0;i<k;i++){

    vector<array<ll,3>> events;
    ll mx = -1 , best = -1;

    for(ll j=1;j<=n;j++){
      events.push_back({ar[j][l[j]],0,j});
      events.push_back({ar[j][r[j]],1,j});
    }

    sort(all(events));
    ll sumi = 0, art = n, eks = 0;
    for(ll j=1;j<=n;j++) sumi += ar[j][r[j]];
    
    vector<array<ll,2>> zip;
    for(ll j=1;j<=n;j++) zip.push_back({ar[j][l[j]]+ar[j][r[j]],j});
    sort(all(zip));
    zip.erase(unique(all(zip)),zip.end());
    
    auto get_ind = [&](array<ll,2> val){
     ll it = lower_bound(all(zip),val) - zip.begin();
     return n - it;
    };

    for(auto x:events){
      ll ekle = ar[x[2]][r[x[2]]]+ar[x[2]][l[x[2]]];
      if(x[1] == 0){        
        art--;
        sumi -= ekle;
        add(get_ind({ekle,x[2]}),ekle,1);
      }
      else{
        eks++;
        sumi -= ar[x[2]][l[x[2]]];
        add(get_ind({ekle,x[2]}),-ekle,-1);
      }
      if(art>n/2 || eks>n/2) continue;
      ll hm = sumi + query(n/2 - art);
      if(hm > mx){
        mx = hm;
        best = x[0];
      }
    }
  
    vector<array<ll,2>> best_choice;
    ll left = n/2;
    for(ll j=1;j<=n;j++){
      if(ar[j][r[j]]<best){
        ans-=ar[j][l[j]];
        ANS[j-1][l[j]-1]=i;
        l[j]++;
      }
      else if(ar[j][l[j]]>best){
        ans+=ar[j][r[j]];
        ANS[j-1][r[j]-1]=i;
        r[j]--;
        left--;
      }
      else{
        ans-=ar[j][l[j]];
        best_choice.push_back({ar[j][l[j]]+ar[j][r[j]],j});
      }
    }

    sort(all(best_choice));
    if(left>sz(best_choice)) while(1){}

    while(left--){
      auto T = best_choice.back();
      best_choice.pop_back();
      ans+=T[0];
      ANS[T[1]-1][r[T[1]]-1]=i;
      r[T[1]]--;
    }
    while(!best_choice.empty()){
      auto T = best_choice.back();
      best_choice.pop_back();
      ANS[T[1]-1][l[T[1]]-1]=i;
      l[T[1]]++;
    }
  }
  allocate_tickets(ANS);
  return ans;
}




/*void _(){
  ll n,m,k;
  cin >> n >> m >> k;
  ll ar[n+5][m+5],l[n+5],r[n+5],ans=0;

  for(ll i=1;i<=n;i++) for(ll j=1;j<=m;j++) cin >> ar[i][j];

  for(ll i=1;i<=n;i++){
    l[i] = 1;
    r[i] = m;
  }

  for(ll i=0;i<k;i++){

    vector<array<ll,3>> events;
    ll mx = -1 , best = -1;

    for(ll j=1;j<=n;j++){
      events.push_back({ar[j][l[j]],0,j});
      events.push_back({ar[j][r[j]],1,j});
    }

    sort(all(events));
    ll sumi = 0, art = n, eks = 0;
    for(ll j=1;j<=n;j++) sumi += ar[j][r[j]];
    
    vector<array<ll,2>> zip;
    for(ll j=1;j<=n;j++) zip.push_back({ar[j][l[j]]+ar[j][r[j]],j});
    sort(all(zip));
    zip.erase(unique(all(zip)),zip.end());
    
    auto get_ind = [&](array<ll,2> val){
     ll it = lower_bound(all(zip),val) - zip.begin();
     return n - it;
    };

    for(auto x:events){
      ll ekle = ar[x[2]][r[x[2]]]+ar[x[2]][l[x[2]]];
      if(x[1] == 0){        
        art--;
        sumi -= ekle;
        add(get_ind({ekle,x[2]}),ekle,1);
      }
      else{
        eks++;
        sumi -= ar[x[2]][l[x[2]]];
        add(get_ind({ekle,x[2]}),-ekle,-1);
      }
      if(art>n/2 || eks>n/2) continue;
      ll hm = sumi + query(n/2 - art);
      if(hm > mx){
        mx = hm;
        best = x[0];
      }
    }
    
    assert(best!=-1);

    vector<array<ll,2>> best_choice;
    ll left = n/2;
    for(ll j=1;j<=n;j++){
      if(ar[j][r[j]]<best){
        ans-=ar[j][l[j]];
        //cout << "l sec " << j << '\n';
        l[j]++;
      }
      else if(ar[j][l[j]]>best){
        ans+=ar[j][r[j]];
        r[j]--;
        //cout << "r sec " << j << '\n';
        left--;
      }
      else{
        ans-=ar[j][l[j]];
        best_choice.push_back({ar[j][l[j]]+ar[j][r[j]],j});
      }
    }
    sort(all(best_choice));
    while(left--){
      auto T = best_choice.back();
      best_choice.pop_back();
      ans+=T[0];
      //cout << "r sec bruh " << T[1] << '\n';
      r[T[1]]--;
    }
    while(!best_choice.empty()){
      auto T = best_choice.back();
      best_choice.pop_back();
      //cout << "l sec " << T[1] << '\n';
      l[T[1]]++;
    }

    //cout << best << ' ' << ans << '\n';
  }

  cout << ans << '\n';
}

ll32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  ll tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}*/

• Subtask 1: 11 / 11
• Subtask 2: 0 / 16
• Subtask 3: 0 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 23
• Subtask 7: 0 / 10