Submission #651779

#	Time	Username	Problem	Language	Result	Execution time	Memory
651779		pauloamed	Jakarta Skyscrapers (APIO15_skyscraper)	C++14	57 / 100	1100 ms	144656 KiB

skyscraper

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

const int MAXN = 30002;

const int ZERO = 0;
const int INF = INT_MAX;

vector<int> p2bs[MAXN];
vector<pair<int,int>> p2d[MAXN];
vector<int> col2p[MAXN];

vector<int> powers;
int p2id[MAXN];
int get_id(int x){ return p2id[x+1]; }

const int BLOCK = 1000;
int ans1[BLOCK][MAXN];
vector<pair<int,int>> ans2[MAXN];

// void print(){
//   for(int i = 0; i < MAXN; ++i){
//     if(ans[i].empty()) continue;
//     cout << i << ":\n";
//     for(auto [x, val] : ans[i]){
//       cout << "\t" << x << ": " << val << "\n";
//     }
//   }
//   cout << "================\n";
// }

int& ans_at(int p, int x){
  int id = get_id(p);
  if(id < BLOCK) return ans1[id][x];
  else{
    return lower_bound(ans2[id].begin(), ans2[id].end(), make_pair(x, ZERO))->second;
  }
}

vector<pair<int,int>> p_cnt;

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;
    p2bs[p].push_back(b);
  }

  for(int p = 1; p < MAXN; ++p){
    map<int, int> D;

    sort(p2bs[p].begin(), p2bs[p].end());
    p2bs[p].erase(unique(p2bs[p].begin(), p2bs[p].end()), p2bs[p].end());

    queue<int> q;
    for(auto b : p2bs[p]){
      col2p[b].push_back(p);
      q.push(b);
      D[b] = 0;
    }
    p2bs[p].clear();

    while(q.size()){
      auto x = q.front(); q.pop();

      if(x - p >= 0 && D.count(x - p) == 0){
        D[x - p] = D[x] + 1;
        q.push(x - p);
      }
      if(x + p < n && D.count(x + p) == 0){
        D[x + p] = D[x] + 1;
        q.push(x + p);
      }
    }

    vector<pair<int,int>> v;
    for(auto [a, b] : D){
      v.push_back({a, b});
    }
    if(D.size()){
      p_cnt.push_back({D.size(), p});
      p2d[p] = move(v);
    }
  }

  p_cnt.push_back({n, -1});
  sort(p_cnt.rbegin(), p_cnt.rend());
  for(int i = 0; i < p_cnt.size(); ++i){
    p2id[p_cnt[i].second+1] = i;
  }


  for(int i = 0; i < BLOCK; ++i){
    for(int j = 0; j < n; ++j){
      ans1[i][j] = INF;
    }
  }

  for(int i = 0; i + 1 < MAXN; ++i){
    int id = get_id(i);
    if(id >= BLOCK){
      for(auto [a, _] : p2d[i]){
        ans2[id].push_back({a, INF});
      }
    }
  }

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

  priority_queue<Node> pq;
  deque<Node> q;
  for(int i = (B[0] % P[0]); i < n; i += P[0]){
    int dist = abs(i - B[0]) / P[0];
    pq.push({-1, i, ans_at(-1, i) = dist});
  }

  // print();

  while(pq.size() + q.size() > 0){
    auto qry_p2d = [&](int p, int x){
      return lower_bound(p2d[p].begin(), p2d[p].end(), make_pair(x, ZERO))->second;
    };

    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};
        
        if(d == 0) q.push_front(X);
        else if(d == 1) q.push_back(X);
        else pq.push(X);
      }
    };


    Node nxt;
    {     
      if(q.empty()){
        nxt = pq.top();
        pq.pop();
      }else if(pq.empty()){
        nxt = q.front();
        q.pop_front();
      }else{
        if(q.front().cost <= pq.top().cost){
          nxt = q.front();
          q.pop_front();
        }else{
          nxt = pq.top();
          pq.pop();
        }
      }
    }
    auto [i, x, cost] = nxt;
    if(cost > ans_at(i, x)) continue;

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

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

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

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

    // print();
  }

  // print();
  cout << ((ans1[get_id(-1)][B[1]] == INF)? -1 : ans1[get_id(-1)][B[1]]) << "\n";
}

Compilation message (stderr)

skyscraper.cpp: In function 'int32_t main()':
skyscraper.cpp:84:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   84 |     for(auto [a, b] : D){
      |              ^
skyscraper.cpp:95:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   for(int i = 0; i < p_cnt.size(); ++i){
      |                  ~~^~~~~~~~~~~~~~
skyscraper.cpp:109:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  109 |       for(auto [a, _] : p2d[i]){
      |                ^
skyscraper.cpp:167:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  167 |     auto [i, x, cost] = nxt;
      |          ^

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