Submission #652258

#	Time	Username	Problem	Language	Result	Execution time	Memory
652258		pauloamed	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1094 ms	154724 KiB

skyscraper

#include<bits/stdc++.h>
using namespace std;

#define int long long


  struct Node{
    int i, x;
    // se i == -1, eh col
    int cost;
    bool operator<(const Node &n) const{
      return cost > n.cost;
    }
  };

namespace smallpq{
  const int MAXV = 1e5;
  
  queue<Node> q[MAXV];
  int tot_in[MAXV];
  int tot_out[MAXV];

  class QComp{ public:
    bool operator()(int a, int b){
      return q[a].front() < q[b].front();
    }
  };

  int _size = 0;
  priority_queue<int, vector<int>, QComp> pq;

  int size() { return _size; }

  void push(Node x, int w) {
    q[w].push(move(x));
    if(++tot_in[w] - tot_out[w] == 1) pq.push(w);
    _size++;
  }
  
  Node top() { return q[pq.top()].front(); }
  void pop() {
    auto w = pq.top(); pq.pop();
    q[w].pop();
    if(q[w].size()) pq.push(w);
    tot_out[w]++;
    _size--;
  }
};

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 30010;


vector<int> col2i[MAXN];
vector<int> ans[MAXN];

int ps[MAXN];

int x2j(int id, int x){
  int p = ps[id];
  return x / p;
}

int& ans_at(int i, int x){
  if(i == -1)
    return ans[i + 1][x];
  else
    return ans[i + 1][x2j(i, x)];
}

map<pair<int,int>, vector<int>> pb2bs;

int32_t main(){
  cin.tie(NULL)->sync_with_stdio(false);

  int n, m; cin >> n >> m;

  int B[2], P[2];
  cin >> B[0] >> P[0];
  cin >> B[1] >> P[1];

  for(int i = 2; i < m; ++i){
    int b, p; cin >> b >> p;
    pb2bs[make_pair(p, b % p)].push_back(b);
  }

  ans[0] = vector<int>(n, INT_MAX);
  int id = 0;
  for(auto [pb, bs] : pb2bs){
    auto [p, b] = pb;
    ps[id] = p;

    for(int j = b; j < n; j += p){
      ans[id+1].push_back(INT_MAX);
    }

    for(auto bb : bs){
      col2i[bb].push_back(id);
    }

    id++;
  }



  for(int i = (B[0] % P[0]); i < n; i += P[0]){
    int dist = abs(i - B[0]) / P[0];
    smallpq::push({-1, i, ans_at(-1, i) = dist}, dist);
  }

  // print();

  while(smallpq::size() > 0){
    auto maybe_update = [&](int p, int x, int val, int d){
      if(ans_at(p, x) > val){
        Node X = {p, x, ans_at(p, x) = val};
        smallpq::push(X, d);
      }
    };

    auto [i, x, cost] = smallpq::top();
    smallpq::pop();
    if(cost > ans_at(i, x)) continue;

    // cout << i << " " << x << " " << cost << "\n";

    if(i == -1){
      for(auto i : col2i[x]){
        maybe_update(i, x, cost, 0);
      }
    }else{
      // sou power i na coluna x
      maybe_update(-1, x, cost, 0);

      if(x + ps[i] < n){
        maybe_update(i, x + ps[i], cost + 1, 1);
      }

      if(x - ps[i] >= 0){
        maybe_update(i, x - ps[i], cost + 1, 1);
      }
    }

    // print();
  }

  cout << ((ans_at(-1, B[1]) == INT_MAX)? -1 : ans_at(-1, B[1])) << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:91:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   91 |   for(auto [pb, bs] : pb2bs){
      |            ^
skyscraper.cpp:92:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |     auto [p, b] = pb;
      |          ^
skyscraper.cpp:123:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  123 |     auto [i, x, cost] = smallpq::top();
      |          ^

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 14 / 14
• Subtask 4: 21 / 21
• Subtask 5: 0 / 43