# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
668012 | slo | Walk (CEOI06_walk) | C++14 | 189 ms | 6012 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 ADD=1e6+2;
const int LIM=2e6+7;
struct Rec{
int x1=0, y1=0, x2=0, y2=0;
};
int n, xf, yf;
Rec rec[N];
int bit[LIM];
// bit function
void upd(int i, int val){
for(; i<LIM; i+=i&(-i))
bit[i]+=val;
}
void upd(int l, int r, int v){
upd(l,v); upd(r+1,-v);
}
int calc(int i){
int res=0;
for(; i>0; i-=i&(-i)) res+=bit[i];
return res;
}
//
void read(){
cin>>xf>>yf>>n; yf+=ADD;
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);
rec[i].y1+=ADD, rec[i].y2+=ADD;
}
}
void solve(){
vpii evt;
fore(i,1,n){
evt.pb(mp(rec[i].x1,i));
evt.pb(mp(rec[i].x2+1,-i));
}
sort(all(evt));
ll ans=0;
int xPre=0, xCur=0, yCur=ADD;
rep(i,sz(evt)){
if(xCur==xf && yCur==yf) break;
xCur=evt[i].fi;
int id=abs(evt[i].se);
if(evt[i].se>0) // add
upd(rec[id].y1,rec[id].y2,1);
else
upd(rec[id].y1,rec[id].y2,-1);
// find closest y
int yl=-1, yr=-1;
//
// find left
{
int l=1, r=yf;
while(l<=r){
int m=l+(r-l)/2;
if(calc(m)>0) r=m-1;
else{
yl=m;
l=m+1;
}
}
}
//
//find right
{
int l=yf, r=LIM-1;
while(l<=r){
int m=l+(r-l)/2;
if(calc(m)>0) l=m+1;
else{
yr=m;
r=m-1;
}
}
}
//
int yNxt=yl;
if(abs(yCur-yl)+abs(yf-yl)>abs(yCur-yr)+abs(yf-yr))
yNxt=yr;
ans+=xCur-xPre+abs(yNxt-yCur);
xPre=xCur, yCur=yNxt;
}
cout<<ans;
}
int main(){
fastIO;
read();
solve();
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |