Submission #363966

#	Time	Username	Problem	Language	Result	Execution time	Memory
363966		denkendoemeer	Golf (JOI17_golf)	C++14	100 / 100	3926 ms	574712 KiB

golf

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int inf=1e9;
struct rec
{
    int tip,x,l,r;
    rec(int t,int y,int a,int b):tip(t),x(y),l(a),r(b){}
};
struct comp
{
    vector<int>aux;
    void add(int x)
    {
        aux.push_back(x);
    }
    void build()
    {
        sort(aux.begin(),aux.end());
        aux.erase(unique(aux.begin(),aux.end()),aux.end());
    }
    int poz(int x)
    {
        return lower_bound(aux.begin(),aux.end(),x)-aux.begin()+1;
    }
    int sz()
    {
        return aux.size();
    }
}x3,y3;
bool ok[400005];
int dist[400005];
queue<int>q;
struct ain
{
    set<pair<int,int>>aint[800005];
    ain(){}
    void add(int nod,int st,int dr,int poz)
    {
        st+=400000;
        dr+=400000;
        while(st<=dr){
            if (st%2==1)
                aint[st++].insert({nod,poz});
            if (dr%2==0)
                aint[dr--].insert({nod,poz});
            st=st/2;
            dr=dr/2;
        }
    }
    void rem(int nod,int st,int dr,int poz)
    {
        nod+=400000;
        while(nod){
            for(auto it=aint[nod].lower_bound({st,-inf});it!=aint[nod].end() && it->first<=dr;aint[nod].erase(it++)){
                int nr=it->second;
                if (ok[nr]==0){
                    ok[nr]=1;
                    dist[nr]=poz+1;
                    q.push(nr);
                }
            }
            nod=nod/2;
        }
    }
}ai[2];
vector<rec>r;
int xa[100005],ya[100005],xb[100005],yb[100005];
vector<pair<int,int>>add[400005],del[400005];
vector<int>fir,last;
int n,sx,sy,ex,ey;
void build(int tip)
{
    int i;
    for(i=1;i<=n;i++)
    add[xa[i]].push_back({ya[i],yb[i]}),del[xb[i]].push_back({ya[i],yb[i]});
    set<pair<int,int>>st;
    st.insert({1,1});
    st.insert({y3.sz(),y3.sz()});
    for(i=1;i<=x3.sz();i++){
        for(auto it:del[i]){
            auto it2=st.find(it),l=it2,dr=it2;
            l--;
            dr++;
            r.push_back(rec(tip,i,l->second,dr->first));
            st.erase(it2);
        }
        if (sx==i){
            auto it=st.lower_bound({sy,-inf}),st=it;
            st--;
            fir.push_back(r.size());
            r.push_back(rec(tip,i,st->second,it->first));
        }
        if (ex==i){
            auto it=st.lower_bound({ey,-inf}),st=it;
            st--;
            last.push_back(r.size());
            r.push_back(rec(tip,i,st->second,it->first));
        }
        for(auto it:add[i]){
            st.insert(it);
            auto it2=st.find(it),st=it2,dr=it2;
            st--;
            dr++;
            r.push_back(rec(tip,i,st->second,dr->first));
        }
    }
    for(i=1;i<=x3.sz();i++)
        add[i].clear(),del[i].clear();
    for(i=1;i<=n;i++)
        swap(xa[i],ya[i]),swap(xb[i],yb[i]);
    swap(sx,sy);
    swap(ex,ey);
    swap(x3,y3);
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int i;
    scanf("%d%d%d%d%d",&sx,&sy,&ex,&ey,&n);
    x3.add(0);
    x3.add(inf);
    x3.add(sx);
    x3.add(ex);
    y3.add(0);
    y3.add(inf);
    y3.add(sy);
    y3.add(ey);
    for(i=1;i<=n;i++)
        scanf("%d%d%d%d",&xa[i],&xb[i],&ya[i],&yb[i]),x3.add(xa[i]),x3.add(xb[i]),y3.add(ya[i]),y3.add(yb[i]);
    x3.build();
    y3.build();
    sx=x3.poz(sx);
    ex=x3.poz(ex);
    sy=y3.poz(sy);
    ey=y3.poz(ey);
    for(i=1;i<=n;i++)
        xa[i]=x3.poz(xa[i]),xb[i]=x3.poz(xb[i]),ya[i]=y3.poz(ya[i]),yb[i]=y3.poz(yb[i]);
    build(0);
    build(1);
    for(i=0;i<r.size();i++)
        ai[r[i].tip].add(r[i].x,r[i].l,r[i].r,i);
    for(auto it:fir){
        if (r[it].tip==0){
            if (ex==r[it].x && ey>=r[it].l && ey<=r[it].r){
                printf("1\n");
                return 0;
            }
        }
        else{
            if (ey==r[it].x && ex>=r[it].l && ex<=r[it].r){
                printf("1\n");
                return 0;
            }
        }
        q.push(it);
        ok[it]=1;
    }
    while(q.size()){
        int nod=q.front();
        q.pop();
        ai[1-r[nod].tip].rem(r[nod].x,r[nod].l,r[nod].r,dist[nod]);
    }
    int ans=inf;
    for(auto it:last)
        if (ok[it])
            ans=min(ans,dist[it]);
    printf("%d\n",ans+1);
return 0;
}

Compilation message (stderr)

golf.cpp: In function 'int main()':
golf.cpp:142:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<rec>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for(i=0;i<r.size();i++)
      |             ~^~~~~~~~~
golf.cpp:121:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  121 |     scanf("%d%d%d%d%d",&sx,&sy,&ex,&ey,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
golf.cpp:131:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |         scanf("%d%d%d%d",&xa[i],&xb[i],&ya[i],&yb[i]),x3.add(xa[i]),x3.add(xb[i]),y3.add(ya[i]),y3.add(yb[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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