Submission #1103796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103796		VinhLuu	Nile (IOI24_nile)	C++17	100 / 100	135 ms	49872 KiB

nile

#include <bits/stdc++.h>
#define ll long long
#define all(vin) vin.begin(), vin.end()
using namespace std;
 
typedef tuple<ll,ll,ll> tp;
const int N = 2e5 + 5;
const int oo = 2e9;
 
ll n, q, W[N], a[N], b[N], d[N], c[N], s[N], le[N], ri[N], w[2][N], kq[N], idx[N];
 
int fin_left(int u){
  return le[u] == u ? u : le[u] = fin_left(le[u]);
}
 
int fin_right(int u){
  return ri[u] == u ? u : ri[u] = fin_right(ri[u]);
}
 
vector<int> open[N], bridge[N];
struct ST{
  ll st[N << 1];
 
  void re(int sz){
    for(int i = 1; i <= 2 * sz; i ++) st[i] = oo;
  }
 
  void update(int i,ll x){
    i += n - 1;
    st[i] = x;
    while(i > 1){
      i /= 2;
      st[i] = min(st[i << 1], st[i << 1|1]);
    }
  }
 
  ll get(int l,int r){
    if(l > r) return oo;
    r++;
    ll ret = oo;
    for(l += n - 1, r += n - 1; l < r; l /= 2, r /= 2){
      if(l & 1) ret = min(ret, st[l ++]);
      if(r & 1) ret = min(ret, st[-- r]);
    }
    return ret;
  }
} T[2], tree[2];
 
vector<long long> calculate_costs(
    vector<int> _W, vector<int> A,
    vector<int> B, vector<int> E){
  n = (int)_W.size();
 
  T[0].re(n);
  T[1].re(n);
  tree[0].re(n);
  tree[1].re(n);
 
  for(int i = 1; i <= n; i ++){
    W[i] = _W[i - 1];
    a[i] = A[i - 1];
    b[i] = B[i - 1];
    idx[i] = i;
  }
 
  sort(idx + 1, idx + n + 1, [&](int x,int y){return W[x] > W[y];});
 
 
  ll ans = 0;
 
  for(int id = 1; id <= n; id ++){
    int i = idx[id];
    tree[id % 2].update(id, a[i] - b[i]);
    ans += a[i];
    s[id] = s[id - 1] + b[i];
    w[0][id] = w[1][id] = a[i];
    le[id] = id, ri[id] = id;
  }
  q = (int)E.size();
 
  for(int i = 1; i <= q; i ++){
    d[i] = E[i - 1];
    c[i] = i;
  }
  sort(c + 1, c + q + 1, [&](int x,int y){return d[x] < d[y];});
 
 
  for(int id = 1; id < n; id ++){
    int i = idx[id], nxt = idx[id + 1];
    int l = 1, r = q, mid, pos = q + 1;
    while(l <= r){
      mid = (l + r) / 2;
      if(d[c[mid]] >= W[i] - W[nxt]){
        pos = mid;
        r = mid - 1;
      }else l = mid + 1;
    }
    if(pos != q + 1){
      open[pos].push_back(id);
    }
  }
 
  for(int id = 2; id < n; id ++){
    int _left = idx[id - 1], _right = idx[id + 1];
    int l = 1, r = q, mid, pos = q + 1;
    while(l <= r){
      mid = (l + r) / 2;
      if(d[c[mid]] >= W[_left] - W[_right]){
        pos = mid;
        r = mid - 1;
      }else l = mid + 1;
    }
    if(pos != q + 1){
      bridge[pos].push_back(id);
    }
  }
 
 
  for(int k = 1; k <= q; k ++){
    for(auto id : bridge[k]){
      int j = idx[id];
      T[id % 2].update(id, a[j] - b[j]);
      int _left = fin_left(id);
      int _right = fin_right(id);
      ans = ans - w[0][_left];
      ll val = 0;
      if((_right - _left + 1) % 2){
        int tc = _left % 2;
        val = s[_right] - s[_left - 1] + min(tree[tc].get(_left, _right), T[tc ^ 1].get(_left, _right));
      }else val = s[_right] - s[_left - 1];
      ans += val;
      w[0][_left] = w[1][_right] = val;
    }
    for(auto j : open[k]){
      int _right = fin_right(j + 1);
      int _left = fin_left(j);
      ans = ans - w[0][j + 1] - w[1][j];
      ll val = 0;
      int tc = _left % 2;
      if((_right - _left + 1) % 2){
          val = s[_right] - s[_left - 1] + min(tree[tc].get(_left, _right), T[tc ^ 1].get(_left, _right));;
      }else val = s[_right] - s[_left - 1];
      ans += val;
      w[1][_right] = w[0][_left] = val;
      ri[j] = j + 1;
      le[j + 1] = j;
    }
    kq[c[k]] = ans;
  }
 
  vector<ll> _ans;
  for(int i = 1; i <= q; i ++) _ans.push_back(kq[i]);
  return _ans;
}
 
//
//signed main(){
//  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//  #define task "v"
//  if(fopen(task ".inp","r")){
//    freopen(task ".inp","r",stdin);
//    freopen(task ".ans","w",stdout);
//  }
//
//  vector<int> _W, _A, _B;
//
//  cin >> n;
//
//  for(int i = 1; i <= n; i ++){
//    int x, y, z; cin >> x >> y >> z;
//    _W.push_back(x);
//    _A.push_back(y);
//    _B.push_back(z);
//  }
//  vector<int> _E;
//  int q;  cin >> q;
//  for(int i = 1; i <= q; i ++){
//    int x; cin >> x;
//    _E.push_back(x);
//  }
//  vector<long long> _ans = calculate_costs(_W, _A, _B, _E);
//  for(auto j : _ans) cout << j << "\n";
//
//}

• 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