Submission #1103844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103844		zNatsumi	Nile (IOI24_nile)	C++17	100 / 100	135 ms	18632 KiB

nile

#include <bits/stdc++.h>

using namespace std;


typedef pair<int, int> ii;
#define ll long long

const int N = 1e5 + 5;
const ll INF = 1e16;

int n, q, pa[N], sz[N], odd_min[N], even_min[N], L[N], R[N];
ll answer[N], res = 0LL;
ii que[N];

struct info{
  int w, a, b;
  info() {}
  info(int w, int a, int b): w(w), a(a), b(b) {}

  friend istream& operator >> (istream& is, info &rhs){
    return is >> rhs.w >> rhs.a >> rhs.b;
  }
  friend ostream& operator << (ostream& os, info rhs){
    return os << "(" << rhs.w << ", " << rhs.a << ", " << rhs.b << ")";
  }
} item[N];

struct Edge{
  int u, v, w;
  Edge() {}
  Edge(int u, int v, ll w): u(u), v(v), w(w) {}

  friend ostream& operator << (ostream &os, Edge &rhs){
    return os << "(" << rhs.u << ", " << rhs.v << ", " << rhs.w << ")";
  }
} edge[2 * N];

struct SegTree{
  ll st[N << 2];

  void build(int tl, int tr, int i){
    st[i] = INF;
    if(tl == tr) return;
    int tm = tl + tr >> 1;
    build(tl, tm, i<<1);
    build(tm + 1, tr, i<<1|1);
  }
  void upd(int pos, int val, int tl, int tr, int i){
    if(tl == tr){
      st[i] = val;
      return;
    }
    int tm = tl + tr >> 1;
    if(pos <= tm) upd(pos, val, tl, tm, i<<1);
    else upd(pos, val, tm + 1, tr, i<<1|1);
    st[i] = min(st[i<<1], st[i<<1|1]);
  }
  int get(int l, int r, int tl, int tr, int i){
    if(r < tl || tr < l || l > r) return INF;
    if(l <= tl && tr <= r) return st[i];
    int tm = tl + tr >> 1;
    return min(get(l, r, tl, tm, i<<1), get(l, r, tm + 1, tr, i<<1|1));
  }
} it;

int fset(int i){ return i == pa[i] ? i : pa[i] = fset(pa[i]); }
void uset(int u, int v){
  int pu = fset(u),
      pv = fset(v);
  if(pu == pv){
    if(u == v - 1) return;
    u += 1;
    if((R[pu] - L[pu] + 1) % 2) res -= min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
    it.upd(u, item[u].a - item[u].b, 1, n, 1);
    if((R[pu] - L[pu] + 1) % 2) res += min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
    return;
  }
  if(sz[pu] % 2) res -= min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
  if(sz[pv] % 2) res -= min(odd_min[pv], it.get(L[pv], R[pv], 1, n, 1));

  if(sz[pu] % 2){
    odd_min[pu] = min(odd_min[pu], even_min[pv]);
    even_min[pu] = min(even_min[pu], odd_min[pv]);
  }else{
    odd_min[pu] = min(odd_min[pu], odd_min[pv]);
    even_min[pu] = min(even_min[pu], even_min[pv]);
  }
  R[pu] = R[pv];
  sz[pu] += sz[pv];

  if(sz[pu] % 2) res += min(odd_min[pu], it.get(L[pu], R[pu], 1, n, 1));
  pa[pv] = pu;
}

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
  n = W.size();
  for(int i = 1; i <= n; i++) item[i] = info(W[i - 1], A[i - 1], B[i - 1]);
  q = E.size();
  for(int i = 1; i <= q; i++) que[i] = make_pair(E[i - 1], i);

  sort(que + 1, que + q + 1);
  for(int i = 1; i <= n; i++) pa[i] = i, sz[i] = 1;

  sort(item + 1, item + n + 1, [](info x, info y){
        return x.w < y.w;
       });

  int ti = 0;
  for(int i = 1; i < n; i++){
    edge[++ti] = Edge(i, i + 1, item[i + 1].w - item[i].w);
    if(i + 2 <= n) edge[++ti] = Edge(i, i + 2, item[i + 2].w - item[i].w);
  }
  for(int i = 1; i <= n; i++){
    odd_min[i] = item[i].a - item[i].b;
    even_min[i] = INF;
    L[i] = i; R[i] = i;
    res += item[i].a;
  }

  sort(edge + 1, edge + ti + 1, [](Edge x, Edge y){
        return make_pair(x.w, abs(x.u - x.v)) < make_pair(y.w, abs(y.u - y.v));
       });

  it.build(1, n, 1);

  for(int i = 1, j = 0; i <= q; i++){
    while(j < ti && edge[j + 1].w <= que[i].first){
      ++j;
      uset(edge[j].u, edge[j].v);
    }
    answer[que[i].second] = res;
  }
  vector<long long> R;
  for(int i = 1; i <= q; i++) R.push_back(answer[i]);
  return R;
}

Compilation message (stderr)

nile.cpp: In member function 'void SegTree::build(int, int, int)':
nile.cpp:45:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
nile.cpp: In member function 'void SegTree::upd(int, int, int, int, int)':
nile.cpp:54:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
nile.cpp: In member function 'int SegTree::get(int, int, int, int, int)':
nile.cpp:60:42: warning: overflow in conversion from 'long long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   60 |     if(r < tl || tr < l || l > r) return INF;
      |                                          ^~~
nile.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:116:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
  116 |     even_min[i] = INF;
      |                   ^~~

• 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