Submission #1117210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117210		thelegendary08	Nile (IOI24_nile)	C++17	100 / 100	148 ms	51776 KiB

nile

#include "nile.h"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define vi vector<ll>
#define pb push_back
#define f0r(i,n) for(int i = 0; i<n;i++)
#define pii pair<ll,ll>
using namespace std;
//using namespace __gnu_pbds;

const int mxn = 100005;
vector<vi> tree(mxn*4, vi(4, 4e18));
//good, odd
//good, even
//bad, odd
//bad, even
int n;
void upd(int k, ll x, int t){
  k += n;
  tree[k][t] = x;
  for(k /= 2; k>=1; k/=2){
    tree[k][t] = min(tree[k*2][t], tree[k*2+1][t]);
  }
}
ll quer(int l, int r, int t){
  l += n;
  r += n;
  ll ret = 4e18;
  while(l <= r){
    if(l % 2 == 1){
      if(ret > tree[l][t]){
        ret = tree[l][t];
      }
      l++;
    }
    if(r % 2 == 0){
      if(ret > tree[r][t]){
        ret = tree[r][t];
      }
      r--;
    }
    l/=2;
    r/=2;
  }
  return ret;
}
vi sz(mxn, 1);
vi par(mxn, 0);
vector<pair<ll,ll>>rng(mxn);
vi anst(mxn);
ll ca = 0;
int get(int x){
  while(par[x] != x)x = par[x];
  return x;
}
pair<ll,ll> mrg(pii a, pii b){
  if(a > b)swap(a, b);
  return {a.first, b.second};
}
void unite(int a, int b){
  //cout<<a<<' '<<b<<'\n';
  a = get(a);
  b = get(b);
  if(sz[a] < sz[b])swap(a, b);
  par[b] = a;
  sz[a] += sz[b];
  ca -= anst[a];
  ca -= anst[b]; 
  //cout<<anst[a]<<' '<<anst[b]<<'\n';
  rng[a] = mrg(rng[a], rng[b]);
  //cout<<rng[a].first<<' '<<rng[a].second<<'\n';
  //ca += (sz[a] % 2);
  int l = rng[a].first;
  int r = rng[a].second;
  if((r - l + 1) % 2 == 0)anst[a] = 0;
  else{
    if(l % 2 == 1){
      anst[a] = min(quer(l, r, 0), quer(l, r, 3));
    }
    else anst[a] = min(quer(l, r, 1), quer(l, r, 2));
  }
  //cout<<anst[a]<<'\n';
  ca += anst[a];
  //cout<<ans[a]<<' '<<ans[b]<<' '<<(sz[a] % 2)<<'\n';
  //ans[a] = (sz[a] % 2);
  //cout<<a<<' '<<ans[a]<<'\n';
  //cout<<'\n';
}

std::vector<long long> calculate_costs(std::vector<int> w, std::vector<int> a,
                                       std::vector<int> b, std::vector<int> e) {
  int q = e.size();
  n = w.size();
  f0r(i, n){
    par[i] = i;
    rng[i] = {i,i};
  }
  
  vi ans(q, 0);
  vector<pair<ll,ll>>quers;
  f0r(i, q)quers.pb({e[i], i});
  sort(quers.begin(), quers.end());
  
  ll s=0;
  f0r(i,n)s += b[i];
  vi c(n);
  f0r(i, n){
    c[i] = a[i] - b[i];
  }
  ca = 0;
  f0r(i, n)ca += c[i];
  //cout<<ca<<'\n';
  vector<pair<ll,ll>>tmp;
  f0r(i,n){
    tmp.pb({w[i], c[i]});
  }
  sort(tmp.begin(), tmp.end());
  f0r(i, n){
    w[i] = tmp[i].first;
    c[i] = tmp[i].second;
  }
  f0r(i, n)anst[i] = c[i];
  //for(auto u : c)cout<<u<<' ';
  //cout<<'\n';
  vector<pair<ll,ll>>connectors;
  f0r(i, n-1){
    connectors.pb({w[i+1] - w[i], i});
  }
  sort(connectors.begin(), connectors.end());
  vector<pair<ll,ll>>mids;
  for(int i = 1; i<n-1; i++){
    mids.pb({w[i+1] - w[i-1], i});
  }
  sort(mids.begin(), mids.end());

  vector<pair<pair<int,int>,int>>ranges;
  f0r(i,n)ranges.pb({{i,i}, c[i]});
  int p1 = 0;
  int p2 = 0;
  f0r(i, n){
    if(i % 2 == 1){
      upd(i, c[i], 0);
    }
    else upd(i, c[i], 1);
  }
  f0r(tt, q){
    ll k = quers[tt].first;
    //cout<<k<<'\n';
    while(p2 < n-2 && k >= mids[p2].first){
      int dex = mids[p2].second;
      if(dex % 2 == 1){
        upd(dex, c[dex], 2);
      }
      else{
        upd(dex, c[dex], 3);
      }
      
      int parr = get(dex);
      if(anst[parr] > c[dex]){
        ca -= anst[parr];
        ca += c[dex];
        anst[parr] = c[dex];
      }
      
      p2++;
    }
    while(p1 < n-1 && k >= connectors[p1].first){
      int dex = connectors[p1].second;
      /*
      int l = 0; int r = ranges.size();
      while(l < r){
        int mid = (l + r)/2;
        if(ranges[mid].first.first < )
      }
      */
      unite(dex, dex + 1);
      p1++;
    }
    //cout<<ca<<'\n';

    
    /*
    ll curans = 0;
    ll cs = 0;
    vector<pair<int,int>>ranges;
    f0r(j, n-1){
      if(w[j+1] - w[j] > k){
        ranges.pb({cs, j});
        cs = j+1;
      }
    }
    ranges.pb({cs, n-1});
    //for(auto u : ranges)cout<<u.first<<' '<<u.second<<'\n';
    f0r(i, ranges.size()){
      int l = ranges[i].first;
      int r = ranges[i].second;
      if((r - l + 1) % 2 == 1){
        ll cur = 4e18;
        for(int j = l; j<=r; j++){
          if((j - l) % 2 == 0)cur = min(cur, c[j]);
          else{
            if(w[j+1] - w[j-1] <= k)cur = min(cur, c[j]);
          }
        }
        //cout<<cur<<"cur"<<'\n';
        curans += cur;
      }
      
      
      

    }
    */
    ans[tt] = s + ca;
    //cout<<ca<<'\n';
    //cout<<'\n';
  }
  vi anss(q);
  f0r(i,q){
    anss[quers[i].second] = ans[i];
  }
  return anss;
}

• 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