제출 #987226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
987226		AdamGS	Sky Walking (IOI19_walk)	C++17	33 / 100	1591 ms	134916 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=1e18+7;
const int LIM=1e5+7;
vector<pair<ll,ll>>V[10*LIM];
set<pair<ll,ll>>S;
map<pair<ll,ll>,ll>mp;
ll tr[4*LIM], odl[10*LIM], n, N=1, akt;
void upd(int l, int r, ll x) {
  l+=N; r+=N;
  tr[l]=max(tr[l], x);
  tr[r]=max(tr[r], x);
  while(l/2!=r/2) {
    if(l%2==0) tr[l+1]=max(tr[l+1], x);
    if(r%2==1) tr[r-1]=max(tr[r-1], x);
    l/=2; r/=2;
  }
}
ll cnt(int v) {
  v+=N;
  ll ans=tr[v];
  while(v) {
    ans=max(ans, tr[v]);
    v/=2;
  }
  return ans;
}
void kraw(pair<ll,ll>a, pair<ll,ll>b) {
  if(mp.find(a)==mp.end()) {
    mp[a]=akt++;
    S.insert({a.nd, a.st});
  }
  if(mp.find(b)==mp.end()) {
    mp[b]=akt++;
    if(S.find({b.nd, b.st})==S.end() && b.nd!=0) {
      auto it=S.lower_bound({b.nd, b.st});
      if(it!=S.end()) {
        auto x=*it;
        if(x.st==b.nd) kraw(b, {x.nd, x.st});
      }
      if(it!=S.begin()) {
        --it;
        auto x=*it;
        if(x.st==b.nd) kraw(b, {x.nd, x.st});
      }
    }
    S.insert({b.nd, b.st});
  }
  ll o=abs(a.st-b.st)+abs(a.nd-b.nd);
  V[mp[a]].pb({mp[b], o});
  V[mp[b]].pb({mp[a], o});
}
ll min_distance(vector<int>x, vector<int>h, vector<int>l, vector<int>r, vector<int>y, int s, int g) {
  n=x.size();
  while(N<n) N*=2;
  vector<pair<ll,pair<ll,ll>>>P;
  rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
  mp[{x[s], 0}]=0;
  mp[{x[g], 0}]=1;
  akt=2;
  sort(all(P));
  for(auto i : P) {
    kraw({x[i.nd.st], i.st}, {x[i.nd.nd], i.st});
    kraw({x[i.nd.st], i.st}, {x[i.nd.st], cnt(i.nd.st)});
    kraw({x[i.nd.nd], i.st}, {x[i.nd.nd], cnt(i.nd.nd)});
    upd(i.nd.st, i.nd.nd, i.st);
  }
  rep(i, akt+1) odl[i]=INF;
  priority_queue<pair<ll,ll>>q;
  q.push({0, 0});
  while(!q.empty()) {
    ll o=-q.top().st, p=q.top().nd; q.pop();
    if(odl[p]<=o) continue;
    odl[p]=o;
    for(auto i : V[p]) q.push({-o-i.nd, i.st});
  }
  if(odl[1]==INF) return -1;
  return odl[1];
}

컴파일 시 표준 에러 (stderr) 메시지

walk.cpp: In function 'll min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
walk.cpp:64:3: note: in expansion of macro 'rep'
   64 |   rep(i, l.size()) P.pb({y[i], {l[i], r[i]}});
      |   ^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43