Submission #1118436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118436		fryingduc	Nile (IOI24_nile)	C++17	100 / 100	90 ms	13492 KiB

nile

#include "bits/stdc++.h"
using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#include "nile.h"
#define debug(...)
#endif

const int maxn = 1e5 + 5;
const int inf = 1e9;
int n, q;

long long ans;

struct info { 
  int w, a, b;
} a[maxn];
pair<int, int> que[maxn];

struct dsu {
  int n;
  vector<int> left_most;
  vector<int> lab;
  vector<int> odd;
  vector<int> even;
  vector<int> temp_even, temp_odd;
  
  void resize(int &sz) {
    left_most.resize(sz + 1);
    even.resize(sz + 1);
    odd.resize(sz + 1);
    temp_even.resize(sz + 1);
    temp_odd.resize(sz + 1);
  }
  dsu() {}
  dsu(int n) : n(n), lab(n + 1, -1) {
    resize(n);
    for(int i = 1; i <= n; ++i) {
      left_most[i] = i;
      even[i] = inf;
      temp_even[i] = temp_odd[i] = inf;
      odd[i] = a[i].a - a[i].b;
    }
  }
  int find(int u) {
    return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  }
  void refine(int u, int v) {
    if(left_most[u] < left_most[v]) {
      if(lab[u] & 1) {
        swap(odd[v], even[v]);
        swap(temp_odd[v], temp_even[v]);
      }
    }
    else {
      if(lab[v] & 1) {
        swap(odd[u], even[u]);
        swap(temp_odd[u], temp_even[u]);
      }
    }
  }
  void join(int u, int v) {
    u = find(u), v = find(v);
    if(u == v) return;
    if(lab[u] > lab[v]) swap(u, v);
    
    if(lab[u] & 1) {
      ans -= min(odd[u], temp_even[u]);
    }
    if(lab[v] & 1) {
      ans -= min(odd[v], temp_even[v]);
    }
    
    refine(u, v);
    
    even[u] = min(even[u], even[v]);
    odd[u] = min(odd[u], odd[v]);
    left_most[u] = min(left_most[u], left_most[v]);
    temp_odd[u] = min(temp_odd[u], temp_odd[v]);
    temp_even[u] = min(temp_even[u], temp_even[v]);
    
    lab[u] += lab[v];
    lab[v] = u;
    if(lab[u] & 1) {
      ans += min(odd[u], temp_even[u]);
    }
  }
  void make(int u) {
    int val = a[u].a - a[u].b;
    int root = find(u);
    if((u - left_most[root] + 1) & 1) {
      temp_odd[root] = min(temp_odd[root], val);
    }
    else {
      if(lab[root] & 1) {
        ans -= min(odd[root], temp_even[root]);
      }
      temp_even[root] = min(temp_even[root], val);
      if(lab[root] & 1) {
        ans += min(odd[root], temp_even[root]);
      }
    }
  }
} d;
vector<long long> solve() {
  for(int i = 1; i <= n; ++i) {
    ans += a[i].a;
  } 
  sort(que + 1, que + q + 1);
  sort(a + 1, a + n + 1, [](const info &x, const info &y) -> bool {
    return x.w < y.w;
  });
  vector<pair<int, int>> diff;
  vector<pair<int, int>> diff_mid;
  for(int i = 2; i <= n; ++i) {
    diff.push_back(make_pair(a[i].w - a[i - 1].w, i));
    if(i < n) {
      diff_mid.push_back(make_pair(a[i + 1].w - a[i - 1].w, i));
    }
  }
  debug(ans);
  sort(diff.begin(), diff.end(), greater<pair<int, int>>());
  sort(diff_mid.begin(), diff_mid.end(), greater<pair<int, int>> ());
  
  d = dsu(n);
  
  vector<long long> res(q);
  
  for(int i = 1; i <= q; ++i) {
    while(!diff.empty() and diff.back().first <= que[i].first) {
      d.join(diff.back().second - 1, diff.back().second);
      diff.pop_back();
    }
    while(!diff_mid.empty() and diff_mid.back().first <= que[i].first) {
      d.make(diff_mid.back().second);
      diff_mid.pop_back();
    }
    
    res[que[i].second - 1] = ans;
  }
  
//  for(int i = 0; i < q; ++i) {
//    cout << res[i] << '\n';
//  }

  return res;
}
vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
  n = (int)W.size();
  for(int i = 0; i < n; ++i) {
    a[i + 1].w = W[i];
    a[i + 1].a = A[i];
    a[i + 1].b = B[i];
  }
  q = (int)E.size();
  for(int i = 0; i < q; ++i) {
    que[i + 1] = make_pair(E[i], i + 1);
  }
  
  return solve();
}

• 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