Submission #1003618

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003618		AdamGS	Golf (JOI17_golf)	C++17	30 / 100	10020 ms	30360 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];
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);
  }
  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();
    rep(i, P[b^1].size()) if(odl[i][b^1]==INF && P[b][a].nd.st<=P[b^1][i].st && P[b^1][i].st<=P[b][a].nd.nd
        && P[b^1][i].nd.st<=P[b][a].st && P[b][a].st<=P[b^1][i].nd.nd) {
      odl[i][b^1]=odl[a][b]+1;
      q.push({i, b^1});
    }
  }
  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';
}

Compilation message (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:55:13: note: in expansion of macro 'rep'
   55 |   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:57:3: note: in expansion of macro 'rep'
   57 |   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:61:3: note: in expansion of macro 'rep'
   61 |   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:67:5: note: in expansion of macro 'rep'
   67 |     rep(i, P[b^1].size()) if(odl[i][b^1]==INF && P[b][a].nd.st<=P[b^1][i].st && P[b^1][i].st<=P[b][a].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:74:3: note: in expansion of macro 'rep'
   74 |   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:75:3: note: in expansion of macro 'rep'
   75 |   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: 0 / 70