Submission #912671

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
912671	2024-01-19T17:42:42 Z	cadmiumsky	Sightseeing in Kyoto (JOI22_kyoto)	C++17	Compilation error	0 ms	0 KB

kyoto

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int inf = 1e9 + 5;

auto compare_frac = [](pii a, pii b) -> bool { return (ll)a.first * b.second < (ll)b.first * a.second; };
auto convoluted_cmpfrac = [](pair<pii,int> a, pair<pii,int> b) -> bool { return compare_frac(a.first, b.first); };

struct Turneu {
  
  set<int> appears;
  int *a;
  
  set<pair<pii, int>, decltype(convoluted_cmpfrac)> heap;
  
  int n;
  
  template<class iteratorlmao>
  void insertIt(iteratorlmao it) {
    if(*next(it) == n + 1 || *it == -1) return;
    cerr << *it << '\t' << a[*next(it)] << ' ' << a[*it] << '\n';
    heap.emplace(pii{a[*next(it)] - a[*it], *next(it) - *it}, *it);
  }
  
  template<class iteratorlmao>
  void eraseIt(iteratorlmao it) {
    if(*next(it) == n + 1 || *it == -1) return;
    heap.erase(heap.find(pair<pii,int>{pii{a[*next(it)] - a[*it], *next(it) - *it}, *it}));
  }
  
  
  void init(int _n, int *v) {
    n = _n;
    a = v;
    
    appears.insert(-1);
    appears.insert(n + 1);
    
    for(int i = 1; i <= n; i++)
      insertIt(prev(appears.insert(i).first));
      
    heap.emplace(pii{inf, 1}, -1);
  }
  
  void erase(int p) {
    cerr << "stergem " << p << "\n--\n";
    
    auto it = appears.find(p);
    
    eraseIt(it);
    eraseIt(prev(it));
    
    auto nvit = prev(it);
    appears.erase(it);
    insertIt(nvit);
  }
};

const int nmax = 1e5 + 5;

int A[nmax], B[nmax];

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int H, W;
  cin >> H >> W;
  
  for(int i = 1; i <= H; i++) cin >> A[i];
  for(int i = 1; i <= W; i++) cin >> B[i];
  
  Turneu linii, coloane;
  
  linii.init(H, A);
  coloane.init(W, B);
  
  ll cost = 0;
  int x = 1, y = 1;
  
  auto move_col = [&]() {
    int nvy = *next(coloane.appears.begin());
    
    cost += (ll)(nvy - y) * A[x];
    y = nvy;
  };
  
  auto move_row = [&]() {
    int nvx = *next(linii.appears.begin());
    
    cost += (ll)(nvx - x) * B[y];
    x = nvx;
  };
  
  while(x != H || y != W) {
    
    auto [Ax, Ay] = linii.heap.begin() -> first;
    auto [Bx, By] = coloane.heap.begin() -> first;
    
    //cerr << Ax << "/" << Ay << '\t' << Bx << "/" << By << '\n';
    
    if(compare_frac(linii.heap.begin() -> first, coloane.heap.begin() -> first))
      cerr << "1\n",
      linii.erase(linii.heap.begin() -> second);
    else
      cerr << "2\n",
      coloane.erase(coloane.heap.begin() -> second);
    
    move_col(); // gen, merge sa le fac pe ambele albeit e retardat
    move_row();
  }
  
  cout << cost << '\n';
}

/**
  Anul asta nu se da centroid
  -- Rugaciunile mele
*/

Compilation message

kyoto.cpp: In function 'int main()':
kyoto.cpp:105:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  105 |     auto [Ax, Ay] = linii.heap.begin() -> first;
      |          ^~~~~~~~
kyoto.cpp:106:10: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
  106 |     auto [Bx, By] = coloane.heap.begin() -> first;
      |          ^~~~~~~~
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from kyoto.cpp:1:
/usr/include/c++/10/bits/stl_tree.h: In instantiation of 'std::_Rb_tree_key_compare<_Key_compare>::_Rb_tree_key_compare() [with _Key_compare = <lambda(std::pair<std::pair<int, int>, int>, std::pair<std::pair<int, int>, int>)>]':
/usr/include/c++/10/bits/stl_tree.h:688:22:   required from 'std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_Rb_tree_impl<_Key_compare, <anonymous> >::_Rb_tree_impl() [with _Key_compare = <lambda(std::pair<std::pair<int, int>, int>, std::pair<std::pair<int, int>, int>)>; bool <anonymous> = false; _Key = std::pair<std::pair<int, int>, int>; _Val = std::pair<std::pair<int, int>, int>; _KeyOfValue = std::_Identity<std::pair<std::pair<int, int>, int> >; _Compare = <lambda(std::pair<std::pair<int, int>, int>, std::pair<std::pair<int, int>, int>)>; _Alloc = std::allocator<std::pair<std::pair<int, int>, int> >]'
/usr/include/c++/10/bits/stl_tree.h:935:7:   required from here
/usr/include/c++/10/bits/stl_tree.h:149:24: error: use of deleted function '<lambda(std::pair<std::pair<int, int>, int>, std::pair<std::pair<int, int>, int>)>::<lambda>()'
  149 |       : _M_key_compare()
      |                        ^
kyoto.cpp:17:28: note: a lambda closure type has a deleted default constructor
   17 | auto convoluted_cmpfrac = [](pair<pii,int> a, pair<pii,int> b) -> bool { return compare_frac(a.first, b.first); };
      |                            ^