제출 #1003632

#제출 시각아이디문제언어결과실행 시간메모리
1003632AdamGSGolf (JOI17_golf)C++17
100 / 100
3562 ms808852 KiB
#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]);
      |   ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...