이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |