Submission #1103837

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1103837	2024-10-22T01:36:28 Z	zNatsumi	Nile (IOI24_nile)	C++17	Compilation error	0 ms	0 KB

nile

#include <bits/stdc++.h>

using namespace std;

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

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

int n, q, pa[N], sz[N], tot[N], odd_min[N], even_min[N], L[N], R[N], res = 0, answer[N];
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, int w): u(u), v(v), w(w) {}

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

struct SegTree{
  int 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;
}

int _N, _Q;
vector<int> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E){
  n = _N;
  for(int i = 1; i <= n; i++){
    item[i].a = A[i - 1];
    item[i].b = B[i - 1];
    item[i].w = W[i - 1];
  }
  q = _Q;
  for(int i = 1; i <= q; i++){
    que[i].first = E[i - 1];
    que[i].second = 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 x.w < y.w;
       });

//  for(int i = 1; i <= n; i++) cout << item[i] << "\n"; cout << "\n";
//  for(int i = 1; i <= ti; i++) cout << edge[i] << "\n"; cout << "\n";

  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<int> R;
  for(int i = 1; i <= n; i++) R.push_back(answer[i]);
  return R;
}


//int32_t main() {
//  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]));
//  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;
//}

Compilation message

nile.cpp: In member function 'void SegTree::build(long long int, long long int, long long int)':
nile.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
nile.cpp: In member function 'void SegTree::upd(long long int, long long int, long long int, long long int, long long int)':
nile.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
nile.cpp: In member function 'long long int SegTree::get(long long int, long long int, long long int, long long int, long long int)':
nile.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
/usr/bin/ld: /tmp/cce84dXA.o: in function `main':
grader.cpp:(.text.startup+0x300): undefined reference to `calculate_costs(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status