Submission #1248305

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248305		meisgood	Nile (IOI24_nile)	C++20	38 / 100	122 ms	31688 KiB

nile

#include <bits/stdc++.h>
using namespace std ;
#define ll long long
// #define test
#ifndef test
#include "nile.h"
#endif
////////////////////////////////////////////////////////////////////////
ll gp[100003] ;
ll gpmn[100003] ;
ll gpmx[100003] ;
ll gpsz[100003] ;
ll nwt[100003] ;
ll tt=0 ;
struct SEGT {
  ll seg[400003] ;
  void build(){
    for (int i = 0 ; i < 400003 ; i ++) seg[i]=LLONG_MAX/2 ;
  }
  void upd(ll id,ll l,ll r,ll x,ll v){
    if (l==r&&l==x) seg[id]=min(seg[id],v) ;
    else if (l>x||r<x) ;
    else {
      ll md=(l+r)/2 ;
      upd(id*2,l,md,x,v) ;
      upd(id*2+1,md+1,r,x,v) ;
      seg[id]=min(seg[id*2],seg[id*2+1]) ;
    }
  }
  ll qq(ll id,ll l,ll r,ll ql,ll qr){
    if (ql<=l&&r<=qr) return seg[id] ;
    else if (l>qr||r<ql) return LLONG_MAX/2 ;
    else {
      ll md=(l+r)/2 ;
      return min(qq(id*2,l,md,ql,qr),qq(id*2+1,md+1,r,ql,qr)) ;
    }
  }
} sgt[2],sgtst[2] ;
ll N ;
ll fnd(ll x){
  ll a=gpmn[x],b=gpmx[x] ;
  if ((b-a+1)%2==0) return 0ll ;
  else {
    ll mn=LLONG_MAX/2ll ;
    mn=min(mn,sgt[a%2].qq(1,1,N,a+1,b+1)) ;
    mn=min(mn,sgtst[(a+1)%2].qq(1,1,N,a+1,b+1)) ;
    return mn ;
  }
}
ll dsu(ll x){
  if (x==gp[x]) return x ;
  gp[x]=dsu(gp[x]) ;
  return gp[x] ;
}
void merge(ll a,ll b){
  a=dsu(a),b=dsu(b) ;
  tt-=nwt[a] ;
  tt-=nwt[b] ;
  gp[b]=a ;
  gpsz[a]+=gpsz[b] ;
  gpmn[a]=min(gpmn[a],gpmn[b]) ;
  gpmx[a]=max(gpmx[a],gpmx[b]) ;
  nwt[a]=fnd(a) ;
  tt+=nwt[a] ;
}
std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a,
                                       std::vector<int> b, std::vector<int> e) {
  vector <ll> W ;
  vector <ll> A ;
  vector <ll> B ;
  vector <ll> E ;
  for (auto x : w) W.push_back(x) ;
  for (auto x : a) A.push_back(x) ;
  for (auto x : b) B.push_back(x) ;
  for (auto x : e) E.push_back(x) ;
  ll Q = (ll)E.size();
  N=W.size() ;
  sgt[0].build() ;
  sgt[1].build() ;
  sgtst[0].build() ;
  sgtst[1].build() ;
  std::vector<long long> R(Q, 0);
  ll i,j ;
  vector <pair<ll,ll>> qs ;
  for (i = 0 ; i < Q ; i ++){
    qs.push_back({E[i],i}) ;
  }
  sort(qs.begin(),qs.end()) ;
  vector <pair<ll,ll>> v ;
  for (i = 0 ; i < N ; i ++){
    tt+=A[i] ;
    v.push_back({W[i],A[i]-B[i],}) ;
  }
  sort(v.begin(),v.end()) ;
  for (i = 0 ; i < N ; i ++){
    gp[i]=i ;
    gpmn[i]=i ;
    gpmx[i]=i ;
    gpsz[i]=1 ;
    sgt[i%2].upd(1,1,N,i+1,v[i].second) ;
    nwt[i]=v[i].second ;
  }
  vector<pair<ll,ll>> vv ;
  vector<pair<ll,ll>> vv2 ;
  for (i = 0 ; i < N-1 ; i ++){
    vv.push_back({v[i+1].first-v[i].first,i}) ;
  }
  for (i = 0 ; i < N-2 ; i ++){
    vv2.push_back({v[i+2].first-v[i].first,i+1}) ;
  }
  sort(vv.begin(),vv.end()) ;
  sort(vv2.begin(),vv2.end()) ;
  ll nw=0 ;
  ll nw2=0 ;
  for (i = 0 ; i < Q ; i ++){
    ll x=qs[i].first ;
    while (nw2<vv2.size()&&vv2[nw2].first<=x){
      sgtst[vv2[nw2].second%2].upd(1,1,N,vv2[nw2].second+1,v[vv2[nw2].second].second) ;
      nw2++ ;
    }
    while (nw<vv.size()&&vv[nw].first<=x){
      merge(vv[nw].second,vv[nw].second+1) ;
      nw++ ;
    }
    R[qs[i].second]=tt ;
  }
  return R;
}

////////////////////////////////////////////////////////////////////////
#ifdef test
//grader{
// #include "nile.h"
#include <cassert>
#include <cstdio>
#include <vector>

int main() {
  int N;
  assert(1 == scanf("%d", &N));
  std::vector<int> W(N), A(N), B(N);
  for (int i = 0; i < N; i++)
    assert(3 == scanf("%d%d%d", &W[i], &A[i], &B[i]));
  int Q;
  assert(1 == scanf("%d", &Q));
  std::vector<int> E(Q);
  for (int j = 0; j < Q; j++)
    assert(1 == scanf("%d", &E[j]));
  fclose(stdin);

  std::vector<long long> R = calculate_costs(W, A, B, E);

  int S = (int)R.size();
  for (int j = 0; j < S; j++)
    printf("%lld\n", R[j]);
  fclose(stdout);

  return 0;
}

//grader}
#endif

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