#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)
#define forw(i,l,r) for(int i=l; i<r; i++)
#define fore(i,l,r) for(int i=l; i<=r; i++)
#define forb(i,r,l) for(int i=r; i>=l; i--)
#define rep(i,n) forw(i,0,n)
#define Pi acos(-1.0)
#define mp make_pair
#define ins insert
#define fi first
#define se second
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define sz(a) (a.size())
#define all(a) a.begin(), a.end()
#define numZeroBitStart(x) (__builtin_clz(x))
#define numZeroBitEnd(x) (__builtin_ctz(x))
#define numOneBit(x) (__builtin_popcount(x))
#define parityOfNumOneBit(x) (__builtin_parity(x))
typedef long long ll;
typedef unsigned long long int ull;
typedef pair<int,int> pii;
typedef pair<int,ll> pill;
typedef pair<ll,int> plli;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
template <class X, class Y>
bool maximize(X &x, const Y &y){
X eps=1e-9;
if(x+eps<y){
x=y; return true;
}
return false;
}
template <class X, class Y>
bool minimize(X &x, const Y &y){
X eps=1e-9;
if(x>y+eps){
x=y; return true;
}
return false;
}
/*-----------------MAIN PROGRAM-----------------*/
const int N=1e5+7;
const int INF=1e9+7;
struct Rec{
int x1=0, y1=0, x2=0, y2=0;
};
int n, xf, yf;
Rec rec[N];
void read(){
cin>>xf>>yf>>n;
fore(i,1,n){
cin>>rec[i].x1>>rec[i].y1>>rec[i].x2>>rec[i].y2;
if(rec[i].y1>rec[i].y2) swap(rec[i].y1,rec[i].y2);
}
}
void solve(){
vpii evt;
fore(i,1,n) evt.pb(mp(rec[i].x1,i));
sort(all(evt));
int xPre=0;
set<pill> active;
active.ins(mp(0,0));
rep(i,sz(evt)){
const int xCur=evt[i].fi-1;
if(xCur>=xf) break;
const int& id=evt[i].se;
auto itl=active.lower_bound(mp(rec[id].y1,-INF));
auto itr=active.lower_bound(mp(rec[id].y2+1,-INF));
stack<pill> rem;
for(auto it=itl; it!=itr; it++)
rem.push(*it);
if(rem.empty()) continue;
pill lhs, rhs=rem.top();
while(!rem.empty()){
active.erase(active.find(rem.top()));
if(sz(rem)==1) lhs=rem.top();
rem.pop();
}
lhs.se+=(lhs.fi-(rec[id].y1-1))+xCur-xPre;
lhs.fi=rec[id].y1-1;
rhs.se+=(rec[id].y2+1-rhs.fi)+xCur-xPre;
rhs.fi=rec[id].y2+1;
active.ins(lhs), active.ins(rhs);
xPre=xCur;
}
ll ans=xf-xPre;
auto it=active.lower_bound(mp(yf,-INF));
int add=(it->se)+(it->fi)-yf;
if(it!=active.begin()){
it--;
minimize(add,(it->se)+yf-(it->fi));
}
ans+=add;
cout<<ans;
}
int main(){
fastIO;
read();
solve();
return 0;
}
Compilation message
walk.cpp: In function 'void solve()':
walk.cpp:5:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
5 | #define forw(i,l,r) for(int i=l; i<r; i++)
| ^
walk.cpp:8:18: note: in expansion of macro 'forw'
8 | #define rep(i,n) forw(i,0,n)
| ^~~~
walk.cpp:81:5: note: in expansion of macro 'rep'
81 | rep(i,sz(evt)){
| ^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Found length 97, official output says 89. |
| 2 |
Incorrect |
0 ms |
212 KB |
Found length 1017, official output says 1190. |
| 3 |
Incorrect |
0 ms |
212 KB |
Found length 129010, official output says 160150. |
| 4 |
Incorrect |
1 ms |
340 KB |
Found length 94944, official output says 126772. |
| 5 |
Incorrect |
47 ms |
2760 KB |
Found length 71263101, official output says 175579. |
| 6 |
Incorrect |
14 ms |
1112 KB |
Found length 215588, official output says 218042. |
| 7 |
Incorrect |
27 ms |
1752 KB |
Found length 36194, official output says 109253. |
| 8 |
Incorrect |
43 ms |
3028 KB |
Found length 9792, official output says 16349. |
| 9 |
Incorrect |
55 ms |
2952 KB |
Found length 7870343, official output says 217249. |
| 10 |
Incorrect |
58 ms |
2952 KB |
Found length 12212900, official output says 196657. |
