Submission #668265

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
668265	2022-12-03T12:45:39 Z	slo	Walk (CEOI06_walk)	C++14	0 / 100	58 ms	3028 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 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)){
      |     ^~~

Subtask #1

0 / 100.0

#	Verdict	Execution time	Memory	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.