Submission #668012

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668012	2022-12-02T14:29:02 Z	slo	Walk (CEOI06_walk)	C++14	0 / 100	189 ms	6012 KB

walk

#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;
}

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:104:5: note: in expansion of macro 'rep'
  104 |     rep(i,sz(evt)){
      |     ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	340 KB	Found length 138, official output says 89.
2	Incorrect	1 ms	328 KB	Found length 3244, official output says 1190.
3	Incorrect	1 ms	596 KB	Found length 754653, official output says 160150.
4	Incorrect	2 ms	596 KB	Found length 396917, official output says 126772.
5	Incorrect	158 ms	5952 KB	Found length 336580099, official output says 175579.
6	Incorrect	43 ms	2396 KB	Found length 8031736, official output says 218042.
7	Incorrect	94 ms	3364 KB	Found length 1724815, official output says 109253.
8	Incorrect	189 ms	6012 KB	Found length 484804, official output says 16349.
9	Incorrect	167 ms	5948 KB	Found length 2840199, official output says 217249.
10	Incorrect	173 ms	5960 KB	Found length 5746890, official output says 196657.