Submission #1239713

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239713		yuichiro17	Nile (IOI24_nile)	C++20	100 / 100	143 ms	15044 KiB

nile

#include "nile.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct segtree{
  int n;
  vector<int>tree;
  segtree(int n,vector<int>&v):n(n),tree(2*n){
    for(int i=n;i<2*n;i++){
      tree[i]=v[i-n];
    }
    for(int i=n-1;i>0;i--){
      tree[i]=min(tree[2*i],tree[2*i+1]);
    }
  }
  void update(int pos,int val){
    tree[pos+=n]=val;
    for(pos/=2;pos>0;pos/=2){
      tree[pos]=min(tree[2*pos],tree[2*pos+1]);
    }
  }
  int query(int l,int r){
    int ans=2e9;
    for(l+=n,r+=n;l<r;l/=2,r/=2){
      if(l%2)ans=min(ans,tree[l++]);
      if(r%2)ans=min(ans,tree[--r]);
    }
    return ans;
  }
};

std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A, std::vector<int> B, std::vector<int> E) {
  int n=W.size(),q=E.size();
  vector<ll>res(q);

  ll ans=0;
  for(int i:A)ans+=i;

  vector<pair<int,int>>a(n);
  for(int i=0;i<n;i++){
    a[i]={W[i],A[i]-B[i]};
  }
  sort(a.begin(),a.end());

  vector<pair<int,int>>diff(n-1);
  for(int i=0;i<n-1;i++){
    diff[i]={a[i+1].first-a[i].first,i};
  }
  sort(diff.begin(),diff.end());
  reverse(diff.begin(),diff.end());

  vector<pair<int,int>>diff2(n-2);
  for(int i=0;i<n-2;i++){
    diff2[i]={a[i+2].first-a[i].first,i};
  }
  sort(diff2.begin(),diff2.end());
  reverse(diff2.begin(),diff2.end());

  vector<int>v1(n,2e9),v2(n,2e9);
  for(int i=0;i<n;i++){
    if(i%2){
      v1[i]=a[i].second;
    }else{
      v2[i]=a[i].second;
    }
  }
  segtree seg1(n,v1),seg2(n,v2);

  vector<pair<int,int>>e(q);
  for(int i=0;i<q;i++){
    e[i]={E[i],i};
  }
  sort(e.begin(),e.end());

  set<int>s;
  for(int i=0;i<=n;i++)s.insert(i);

  for(int _=0;_<q;_++){
    int d=e[_].first;
    vector<int>update;
    while(!diff.empty()&&diff.back().first<=d){
      auto it=s.upper_bound(diff.back().second);
      it--;
      diff.pop_back();
      update.push_back(*it);
      if((*next(it)-*it)%2){
        if(*it%2){
          ans-=seg1.query(*it,*next(it));
        }else{
          ans-=seg2.query(*it,*next(it));
        }
      }
      if((*next(next(it))-*next(it))%2){
        if(*next(it)%2){
          ans-=seg1.query(*next(it),*next(next(it)));
        }else{
          ans-=seg2.query(*next(it),*next(next(it)));
        }
      }
      if((*next(next(it))-*it)%2){
        if(*it%2){
          ans+=seg1.query(*it,*next(next(it)));
        }else{
          ans+=seg2.query(*it,*next(next(it)));
        }
      }
      s.erase(next(it));
    }
    while(!diff2.empty()&&diff2.back().first<=d){
      pair<int,int>p=diff2.back();
      diff2.pop_back();
      auto it=s.upper_bound(p.second+1);
      it--;
      if((*next(it)-*it)%2){
        if(*it%2){
          ans-=seg1.query(*it,*next(it));
        }else{
          ans-=seg2.query(*it,*next(it));
        }
      }
      if(p.second%2){
        seg1.update(p.second+1,a[p.second+1].second);
      }else{
        seg2.update(p.second+1,a[p.second+1].second);
      }
      if((*next(it)-*it)%2){
        if(*it%2){
          ans+=seg1.query(*it,*next(it));
        }else{
          ans+=seg2.query(*it,*next(it));
        }
      }
    }
    res[e[_].second]=ans;
  }
  return res;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 13 / 13
• Subtask 3: 17 / 17
• Subtask 4: 11 / 11
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15
• Subtask 7: 18 / 18