Submission #912709

#	Time	Username	Problem	Language	Result	Execution time	Memory
912709		cadmiumsky	Sightseeing in Kyoto (JOI22_kyoto)	C++17	10 / 100	2012 ms	16372 KiB

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) || (!compare_frac(a.first, b.first) && !compare_frac(b.first, a.first) && a.second < b.second); };

struct Turneu {
  
  set<int> appears;
  int *a;
  
  set<pair<pii, int>, decltype(convoluted_cmpfrac)> heap;
  Turneu(): heap(convoluted_cmpfrac) {;}
  
  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';
    
    cerr << "inseram\n";
    cerr << a << '\t' << *it << ", " << *next(it) << '\t';
    cerr << a[*next(it)] - a[*it] << ' ' << *next(it) - *it << '\t' << *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;
    cerr << a << '\t' << *it << ' ' << *next(it) << '\t';
    cerr << a[*next(it)] - a[*it] << ' ' << *next(it) - *it << '\t' << *it << '\n' << "iata ";
    heap.erase(heap.find(pair<pii,int>{pii{a[*next(it)] - a[*it], *next(it) - *it}, *it}));
    cerr << "ca nu-i aici greseala\n";
  }
  
  
  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, 0}, -1);
  }
  
  void erase(int p) {
    assert(p > -1);
    
    cerr << "stergem " << p << "\n--\n";
    
    auto it = appears.find(p);
    
    eraseIt(it);
    eraseIt(prev(it));
    
    auto nvit = prev(it);
    appears.erase(it);
    cerr << *nvit << '\n';
    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
*/

• Subtask 1: 10 / 10
• Subtask 2: 0 / 30
• Subtask 3: 0 / 60