oj.uz

답안 #1103838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1103838 2024-10-22T01:42:53 Z zNatsumi 나일강 (IOI24_nile) C++17
0 / 100
 43 ms 18760 KB 
#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[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;
}

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

//
//int 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(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:55:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   55 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
nile.cpp: In member function 'int SegTree::get(int, int, int, int, int)':
nile.cpp:61:42: warning: overflow in conversion from 'long long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
   61 |     if(r < tl || tr < l || l > r) return INF;
      |                                          ^~~
nile.cpp:63:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |     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:135:19: warning: overflow in conversion from 'long long int' to 'int' changes value from '10000000000000000' to '1874919424' [-Woverflow]
  135 |     even_min[i] = INF;
      |                   ^~~

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 12880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #1
0.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 13136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 43 ms 17792 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 18760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 13136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 13136 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 31 ms 18760 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 10 ms 12880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -