제출 #1003632

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1003632		AdamGS	Golf (JOI17_golf)	C++17	100 / 100	3562 ms	808852 KiB

golf

#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
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 int LIM=1e5+7, INF=1e9+7;
pair<pair<int,int>,pair<int,int>>T[LIM];
vector<pair<int,pair<int,int>>>P[2];
int odl[10*LIM][2], akt, N=1;
map<int,int>mp;
vector<int>skal;
set<pair<int,int>>tr[1<<21][2];
void upd(int l, int r, int k, pair<int,int>x) {
  if(l>r) return;
  l+=N; r+=N;
  tr[l][k].insert(x);
  tr[r][k].insert(x);
  while(l/2!=r/2) {
    if(l%2==0) tr[l+1][k].insert(x);
    if(r%2==1) tr[r-1][k].insert(x);
    l/=2; r/=2;
  }
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  int x1, y1, x2, y2, n;
  cin >> x1 >> y1 >> x2 >> y2 >> n;
  rep(i, n) cin >> T[i].st.st >> T[i].nd.st >> T[i].st.nd >> T[i].nd.nd;
  rep(xd, 2) {
    vector<pair<pair<int,int>,int>>V;
    rep(i, n) {
      if(T[i].st.st<T[i].nd.st && T[i].st.nd<T[i].nd.nd) {
        V.pb({{T[i].nd.nd, 0}, T[i].st.st});
        V.pb({{T[i].nd.nd, 0}, T[i].nd.st-1});
        V.pb({{T[i].st.nd+1, -1}, T[i].st.st});
        V.pb({{T[i].st.nd+1, -1}, T[i].nd.st-1});
      }
      V.pb({{T[i].st.nd, 2}, T[i].st.st});
      V.pb({{T[i].nd.nd, 2}, T[i].st.st});
    }
    V.pb({{y1, 2}, x1});
    V.pb({{y2, 2}, x2});
    sort(all(V));
    set<int>S;
    S.insert(-INF);
    S.insert(INF);
    for(auto i : V) {
      if(i.st.nd==0) S.erase(i.nd);
      else if(i.st.nd==-1) S.insert(i.nd);
      else {
        auto it=S.lower_bound(i.nd);
        auto b=*it;
        --it;
        auto a=*it;
        P[xd].pb({i.st.st, {a+1, b}});
      }
    }
    rep(i, n) {
      swap(T[i].st.st, T[i].st.nd);
      swap(T[i].nd.st, T[i].nd.nd);
    }
    swap(x1, y1);
    swap(x2, y2);
  }
  skal.pb(x1);
  skal.pb(x2);
  skal.pb(y1);
  skal.pb(y2);
  rep(i, 2) for(auto j : P[i]) {
    skal.pb(j.st);
    skal.pb(j.nd.st);
    skal.pb(j.nd.nd);
  }
  sort(all(skal));
  for(auto i : skal) if(mp.find(i)==mp.end()) mp[i]=akt++;
  x1=mp[x1]; x2=mp[x2]; y1=mp[y1]; y2=mp[y2];
  rep(i, 2) rep(j, P[i].size()) P[i][j]={mp[P[i][j].st], {mp[P[i][j].nd.st], mp[P[i][j].nd.nd]}};
  while(N<akt) N*=2;
  rep(i, 2) {
    rep(j, P[i].size()) {
      upd(P[i][j].nd.st, P[i][j].nd.nd, i, {P[i][j].st, j});
    }
  }
  rep(i, 2) rep(j, P[i].size()) odl[j][i]=INF;
  queue<pair<int,int>>q;
  rep(i, P[0].size()) if(P[0][i].st==y1 && P[0][i].nd.st<=x1 && x1<=P[0][i].nd.nd) {
    odl[i][0]=1;
    q.push({i, 0});
  }
  rep(i, P[1].size()) if(P[1][i].st==x1 && P[1][i].nd.st<=y1 && y1<=P[1][i].nd.nd) {
    odl[i][1]=1;
    q.push({i, 1});
  }
  while(!q.empty()) {
    int a=q.front().st, b=q.front().nd; q.pop();
    int x=P[b][a].st+N;
    while(x>0) {
      while(!tr[x][b^1].empty()) {
        auto it=tr[x][b^1].lower_bound({P[b][a].nd.st, -INF});
        if(it==tr[x][b^1].end()) break;
        auto c=*it;
        if(c.st>P[b][a].nd.nd) break;
        tr[x][b^1].erase(c);
        if(odl[c.nd][b^1]==INF) {
          odl[c.nd][b^1]=odl[a][b]+1;
          q.push({c.nd, b^1});
        }
      }
      x/=2;
    }
  }
  int ans=INF;
  rep(i, P[0].size()) if(P[0][i].st==y2 && P[0][i].nd.st<=x2 && x2<=P[0][i].nd.nd) ans=min(ans, odl[i][0]);
  rep(i, P[1].size()) if(P[1][i].st==x2 && P[1][i].nd.st<=y2 && y2<=P[1][i].nd.nd) ans=min(ans, odl[i][1]);
  cout << ans << '\n';
}

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

golf.cpp: In function 'int main()':
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:81:13: note: in expansion of macro 'rep'
   81 |   rep(i, 2) rep(j, P[i].size()) P[i][j]={mp[P[i][j].st], {mp[P[i][j].nd.st], mp[P[i][j].nd.nd]}};
      |             ^~~
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:84:5: note: in expansion of macro 'rep'
   84 |     rep(j, P[i].size()) {
      |     ^~~
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:88:13: note: in expansion of macro 'rep'
   88 |   rep(i, 2) rep(j, P[i].size()) odl[j][i]=INF;
      |             ^~~
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:90:3: note: in expansion of macro 'rep'
   90 |   rep(i, P[0].size()) if(P[0][i].st==y1 && P[0][i].nd.st<=x1 && x1<=P[0][i].nd.nd) {
      |   ^~~
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:94:3: note: in expansion of macro 'rep'
   94 |   rep(i, P[1].size()) if(P[1][i].st==x1 && P[1][i].nd.st<=y1 && y1<=P[1][i].nd.nd) {
      |   ^~~
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:117:3: note: in expansion of macro 'rep'
  117 |   rep(i, P[0].size()) if(P[0][i].st==y2 && P[0][i].nd.st<=x2 && x2<=P[0][i].nd.nd) ans=min(ans, odl[i][0]);
      |   ^~~
golf.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
golf.cpp:118:3: note: in expansion of macro 'rep'
  118 |   rep(i, P[1].size()) if(P[1][i].st==x2 && P[1][i].nd.st<=y2 && y2<=P[1][i].nd.nd) ans=min(ans, odl[i][1]);
      |   ^~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70