Submission #557247

#	Time	Username	Problem	Language	Result	Execution time	Memory
557247		balbit	Golf (JOI17_golf)	C++14	100 / 100	2634 ms	643420 KiB

golf

#include <bits/stdc++.h>
#define int ll
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<ll, ll>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;



struct seg{
    int l,r,y,id;
};

int IT = 0; // each segment gets assigned an id
int dst[maxn * 20 * 4 * 4];
bool dir[maxn * 20 * 4 * 4];

bool NOWHOR = 0;

struct rect{
    int x1, x2, y1, y2;
};

int Sx, Sy, Tx, Ty;

vector<seg> who;


vector<seg> get(vector<rect> &v) {
    set<int> have; // current y positions
    // scan from left to right along x axis

    struct Ev{
        int x,y;
        int id; // id 1: remove, id 2: ask, id 3: add
        bool operator < (Ev & o) {
            return x != o.x? x < o.x : id < o.id;
        }
    };

    vector<Ev> ev;

    ev.pb({Sx, Sy, 2});
    ev.pb({Tx, Ty, 2});

    for (rect r : v) {
        ev.pb({r.x1, r.y1, 3});
        ev.pb({r.x1, r.y2, 3});

        ev.pb({r.x1, r.y1, 2});
        ev.pb({r.x2, r.y1, 2});

        ev.pb({r.x2, r.y1, 1});
        ev.pb({r.x2, r.y2, 1});
    }

    sort(ALL(ev));

    vector<seg> ret;
    set<pair<pii, int> > seghave;

    for (Ev & e : ev) {
        if (e.id == 1) {
            have.erase(e.y);
        }
        if (e.id == 3) {
            have.insert(e.y);
        }
        if (e.id == 2) {
            auto it = have.lower_bound(e.y);
            int ybig = it==have.end()?iinf : *it;
            int ysmall = it==have.begin()? 0 : *prev(it);
            if (seghave.count({{ysmall, ybig}, e.x})) {
                continue;
            }
            seghave.insert({{ysmall, ybig}, e.x});
            dir[IT] = NOWHOR;
            ret.pb({ysmall, ybig, e.x, IT++});
        }
    }

    return ret;
}



queue<int> qq;

struct smolseg{
    vector<pii> s;
    vector<int> id;

    void build(int o, int l, int r) {
        bug(o,l,r);
        if (l > r) return;
        if (l == r) {
            id[o] = s[l].s;
            return;
        }
        dir[IT] = NOWHOR;
        id[o] = IT++;
        int mid = (l+r)/2;
        build(o*2,l,mid); build(o*2+1, mid+1,r);
    }

    void build(){
        sort(ALL(s));
        id.resize(SZ(s) * 4);
        build(1,0,SZ(s)-1);
    }

    void runupd(int L, int R, int d, int o, int l, int r) {
        if (l > r) return;
        if (s[l].f > R || s[r].f < L) return;
        int mid = (l+r)/2;
        if (s[l].f >= L && s[r].f <= R) {
            if (dst[id[o]] <= d) {
                return;
            }
            dst[id[o]] = d;
            if (l == r) {
                qq.push(id[o]);
                return;
            }
        }
        runupd(L,R,d,o*2,l,mid);
        runupd(L,R,d,o*2+1,mid+1,r);
    }

    void runupd(int L, int R, int d) {
        runupd(L,R,d,1,0,SZ(s)-1);

    }

};

struct STree{
    int MX;
    smolseg s[maxn*4*3]; // y position, index

    void put(int L, int R, pii v, int o=1, int l=0, int r=-1) {
        if (r == -1) r = MX-1;
        if (l > R || r < L) return;
        if (l >= L && r <= R) {
            s[o].s.pb(v); return;
        }
        int mid = (l+r)/2;
        put(L,R,v,o*2,l,mid);
        put(L,R,v,o*2+1,mid+1,r);
    }

    void build(int o, int l, int r){
        s[o].build();
        if (l!=r) {
            int mid = (l+r)/2;
            build(o*2, l,mid);
            build(o*2+1, mid+1,r);
        }
    }

    void run(seg S, int o=1, int l=0, int r=-1) {
        if (r == -1) r = MX-1;
        if (r < S.y || l > S.y) return;
        s[o].runupd(S.l, S.r, dst[S.id]+1);
        if (l == r) return;
        int mid = (l+r)/2;
        run(S,o*2,l,mid); run(S,o*2+1,mid+1,r);
    }
}AA[2]; // this is the big, scary segment tree you were waiting for!!!!!

signed main(){
    IOS();


    cin>>Sx>>Sy>>Tx>>Ty;

    int n; cin>>n;
    vector<rect> v;
    REP(i,n) {
        int x1,x2,y1,y2;
        cin>>x1>>x2>>y1>>y2;
        v.pb({x1,x2,y1,y2});
    }
    NOWHOR = 0;
    vector<seg> gver = get(v); // gver returns vertical lines
    for (auto &r : v) {
        swap(r.x1, r.y1);
        swap(r.x2, r.y2);
    }
    swap(Sx, Sy); swap(Tx, Ty);

    NOWHOR = 1;
    vector<seg> ghor = get(v);

    for (auto &r : v) {
        swap(r.x1, r.y1);
        swap(r.x2, r.y2);
    }
    swap(Sx, Sy); swap(Tx, Ty);

    for (auto s : gver) {
        bug(s.y, s.l, s.r);
    }


    // step 2: compress coordinates
    vector<int> posx, posy;
    for (auto s : gver) {
        posy.pb(s.l);
        posy.pb(s.r);
        posx.pb(s.y);
    }
    for (auto s : ghor) {
        posx.pb(s.l);
        posx.pb(s.r);
        posy.pb(s.y);
    }

    SORT_UNIQUE(posx); SORT_UNIQUE(posy);

    who.resize(IT);

    for (auto &s : gver) {
        s.l = lower_bound(ALL(posy), s.l) - posy.begin();
        s.r = lower_bound(ALL(posy), s.r) - posy.begin();
        s.y = lower_bound(ALL(posx), s.y) - posx.begin();
        who[s.id] = s;
    }
    for (auto &s : ghor) {
        s.l = lower_bound(ALL(posx), s.l) - posx.begin();
        s.r = lower_bound(ALL(posx), s.r) - posx.begin();
        s.y = lower_bound(ALL(posy), s.y) - posy.begin();
        who[s.id] = s;
    }

    Sx = lower_bound(ALL(posx), Sx) - posx.begin();
    Tx = lower_bound(ALL(posx), Tx) - posx.begin();
    Sy = lower_bound(ALL(posy), Sy) - posy.begin();
    Ty = lower_bound(ALL(posy), Ty) - posy.begin();

    // step 3: build the segtree layers

    NOWHOR = 0;

    AA[0].MX = SZ(posy);
    for (auto &s : gver) { // AA[0] stores the vertical ones
        AA[0].put(s.l, s.r, make_pair(s.y, s.id));
    }
    AA[0].build(1,0,SZ(posy)-1);

    NOWHOR = 1;

    AA[1].MX = SZ(posx);
    for (auto &s : ghor) { // AA[1] stores the horizontal ones
        AA[1].put(s.l, s.r, make_pair(s.y, s.id));
    }
    AA[1].build(1,0,SZ(posx)-1);

    // step 4: run the bfs

    memset(dst, 0x3f, sizeof dst);

    for (auto & s : gver) {
        if (s.y == Sx && (s.l <= Sy && Sy <= s.r)) {
            bug(s.id);
            bug(s.y,s.l,s.r,dst[s.id]);
            qq.push(s.id);
            dst[s.id] = 0;
        }
    }

    for (auto & s : ghor) {
        if (s.y == Sy && (s.l <= Sx && Sx <= s.r)) {
            bug(s.id);
            bug("p2", s.y,s.l,s.r,dst[s.id]);
            qq.push(s.id);
            dst[s.id] = 0;
        }
    }

    while (!qq.empty()) {
        int v = qq.front(); qq.pop();
        bug(v, dst[v]);
        bug(dir[v], who[v].l, who[v].r);
        bug(who[v].y);
        AA[dir[v]^1].run(who[v]);
    }

    int re = 0x3f3f3f3f;

    for (auto & s : gver) {
        if (s.y == Tx && (s.l <= Ty && Ty <= s.r)) {
            bug(s.id);
            bug(s.y,s.l,s.r,dst[s.id]);
            MN(re, dst[s.id]);
        }
    }

    for (auto & s : ghor) {
        if (s.y == Ty && (s.l <= Tx && Tx <= s.r)) {
            bug(s.id);
            bug("p2", s.y,s.l,s.r,dst[s.id]);
            MN(re, dst[s.id]);
        }
    }
    cout<<re+1<<endl;
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:9:11: warning: variable 'second' set but not used [-Wunused-but-set-variable]
    9 | #define s second
      |           ^~~~~~
golf.cpp:248:15: note: in expansion of macro 's'
  248 |     for (auto s : gver) {
      |               ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 70 / 70