Submission #1148016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1148016		idiotcomputer	Golf (JOI17_golf)	C++20	30 / 100	4301 ms	369364 KiB

golf

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define pii pair<int,int>
#define f first
#define s second
#define sz(x) (int) (x).size()
#define arr array


const int mxN = 1e5+5;
const int mX = 2*mxN+5;
int n;
set<pii> ht[4*mX+5];
set<pii> vt[4*mX+5];

void add(set<pii> st[4*mxN+5], int tl, int tr, pii v, int l, int r, int idx){
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr){ st[idx].insert(v); return; }
    int m = (l+r)/2;
    add(st,tl,tr,v,l,m,2*idx+1);
    add(st,tl,tr,v,m+1,r,2*idx+2);
}

//0 = lb, 1 = ub
int q1(set<pii> st[4*mxN+5], int t, int v, bool w, int l, int r, int idx){
    if (r < t || l > t) return w ? mX : -1;
    if (st[idx].begin()->f != -1) st[idx].insert({-1,0});
    if (st[idx].rbegin()->f != mX) st[idx].insert({mX,0});
    int res = w ? (*(st[idx].lower_bound({v,-1}))).f : (*(prev(st[idx].upper_bound({v,-1})))).f;
    if (l == r) return res;
    int m = (l+r)/2;
    res = w ? min(res, min(q1(st,t,v,w,l,m,2*idx+1), q1(st,t,v,w,m+1,r,2*idx+2))) : max(res, max(q1(st,t,v,w,l,m,2*idx+1), q1(st,t,v,w,m+1,r,2*idx+2)));
    return res;
}

bool vis[4*mxN];
int dis[4*mxN];

queue<int> act;

void q2(set<pii> st[4*mxN+5], int t, int vl, int vr, int vidx, int l, int r, int idx){
    if (l > t || r < t) return;
    auto it = st[idx].lower_bound({vl,-1});
    while (it != st[idx].end() && it->f <= vr){
        if (vis[it->s]){ it++; st[idx].erase(prev(it)); continue;}
        vis[it->s] = 1;
        act.push(it->s);
        dis[it->s] = dis[vidx]+1;
        it++;
        st[idx].erase(prev(it));
    }
    if (l == r) return;
    int m = (l+r)/2;
    q2(st,t,vl,vr,vidx,l,m,2*idx+1);
    q2(st,t,vl,vr,vidx,m+1,r,2*idx+2);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int s,t,u,v;
    cin >> s >> t >> u >> v;

    vector<int> ax;
    vector<int> ay;
    ax.pb(s), ax.pb(u);
    ay.pb(t), ay.pb(v);

    cin >> n;
    vector<arr<int,4>> all(n);
    for (int i = 0; i < n; i++){
        cin >> all[i][0] >> all[i][1] >> all[i][2] >> all[i][3];
        ax.pb(all[i][0]), ax.pb(all[i][1]);
        ay.pb(all[i][2]), ay.pb(all[i][3]);
    }

    sort(ax.begin(), ax.end());
    sort(ay.begin(), ay.end());

    map<int,int> ix;
    map<int,int> iy;
    int last = -1;
    int cnt = -1;
    for (int i = 0; i < sz(ax); i++){
        if (ax[i] == last) continue;
        cnt++;
        last = ax[i];
        ix[last] = cnt;
    }

    int nx = cnt+1;
    last = - 1;
    cnt = -1;
    for (int i = 0; i < sz(ay); i++){
        if (ay[i] == last) continue;
        cnt++;
        last = ay[i];
        iy[last] = cnt;
    }
    int ny = cnt+1;

    cnt = 0;
    vector<int> vs[nx];
    vector<int> hs[ny];
    for (int i = 0; i < n; i++){
        all[i][0] = ix[all[i][0]], all[i][1] = ix[all[i][1]];
        all[i][2] = iy[all[i][2]], all[i][3] = iy[all[i][3]];
        //cout << all[i][0] << " " << all[i][1] << " " << all[i][2] << " " << all[i][3] << '\n';
        vs[all[i][0]].pb(all[i][2]), vs[all[i][1]].pb(all[i][2]);
        hs[all[i][2]].pb(all[i][0]), hs[all[i][3]].pb(all[i][0]);
        add(ht, all[i][0]+1, all[i][1]-1, {all[i][2], 0}, 0, nx-1, 0);
        add(ht, all[i][0]+1, all[i][1]-1, {all[i][3], 0}, 0, nx-1, 0);
        add(vt, all[i][2]+1, all[i][3]-1, {all[i][0], 0}, 0, ny-1, 0);
        add(vt, all[i][2]+1, all[i][3]-1, {all[i][1], 0}, 0, ny-1, 0);
    }
    s = ix[s], t = iy[t], u = ix[u], v = iy[v];
   // cout << s << " " << t << " " << u << " " <<  v << '\n';
    //cout << nx << " " << ny << '\n';
    vs[s].pb(t), vs[u].pb(v);
    hs[t].pb(s), hs[v].pb(u);

    vector<arr<int,3>> s1[nx];
    vector<arr<int,3>> s2[ny];

   // return 0;
    int sv,sh,ev,eh;
    vector<arr<int,3>> allr;
    for (int i = 0; i < nx; i++){
        sort(vs[i].begin(), vs[i].end());
        last = -1;
      //  for (int c : vs[i]) cout << c << " ";
      //  cout << '\n';
       // continue;
        for (int j = 0; j < sz(vs[i]); j++){
            if (vs[i][j] <= last) continue;
            int l = q1(ht, i, vs[i][j], 0,0, nx-1,0);
            int r = q1(ht, i, vs[i][j],1,0,nx-1,0);
            s1[i].pb({l,r,cnt});
            allr.pb({l,r,i});
            last = r;
            if (i == s && l <= t && r >= t) sv = cnt;
            if (i == u && l <= v && r >= v) ev = cnt;
            cnt++;
        }
    }
   // return 0;

    int vsc = cnt;
   // cout << '\n';
    for (int i = 0; i < ny; i++){
        sort(hs[i].begin(), hs[i].end());
        last = -1;
      //  for (int c : hs[i]) cout << c << " ";
      //  cout << '\n';
        for (int j = 0; j < sz(hs[i]); j++){
            if (hs[i][j] <= last) continue;
            int l = q1(vt, i, hs[i][j], 0,0, ny-1,0);
            int r = q1(vt, i, hs[i][j],1,0,ny-1,0);
            s2[i].pb({l,r,cnt});
            allr.pb({l,r,i});
            last = r;
            if (i == t && l <= s && r >= s) sh = cnt;
            if (i == v && l <= u && r >= u) eh = cnt;
            cnt++;
        }
    }
  //  return 0;
    for (int i = 0; i <4*mxN+5; i++) ht[i].clear(), vt[i].clear();
    for (int i = 0; i < nx; i++) for (int j = 0; j < sz(s1[i]); j++){
        add(vt, s1[i][j][0], s1[i][j][1], {i,s1[i][j][2]}, 0, ny-1,0);
    }

    for (int i = 0; i < ny; i++) for (int j = 0; j < sz(s2[i]); j++){
        add(ht, s2[i][j][0], s2[i][j][1], {i,s2[i][j][2]}, 0, nx-1,0);
    }

    memset(vis,0,sizeof(vis));
    memset(dis,0,sizeof(dis));

    act.push(sh);
    act.push(sv);
    vis[sh] = 1;
    vis[sv] = 1;
   // return 0;
//   cout << vsc << ',' << sz(allr) << '\n';
  //  for (int i = 0; i < sz(allr); i++) cout << allr[i][0] << ',' << allr[i][1] << ',' << allr[i][2] << '\n';

    while (sz(act)){
        int cc = act.front();
        act.pop();
     //   cout << cc << " ";
        if (cc >= vsc){
            q2(vt,allr[cc][2],allr[cc][0],allr[cc][1],cc,0,ny-1,0);
        } else {
            q2(ht,allr[cc][2],allr[cc][0],allr[cc][1],cc,0,nx-1,0);
        }
    }
  //  cout << '\n';

    cout << min(dis[ev], dis[eh])+1 << '\n';
    return 0;
}

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