Submission #249619

#	Time	Username	Problem	Language	Result	Execution time	Memory
249619		LittleFlowers__	Sky Walking (IOI19_walk)	C++17	33 / 100	4078 ms	107884 KiB

walk

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);

const long long INF=1e18+10;
const int N=100010;


long long f[N*3];
vector<int> val;
multiset<long long> up[N],dw[N];


vector<int> has[N];

void upd_u(int i,long long j,int t){
    i=lower_bound(all(val),i)-val.begin()+1;
    for(;i;i-=i&-i){
        if(t) up[i].insert(j); else up[i].erase(up[i].find(j));
    }
}
void upd_d(int i,long long j,int t){
    i=lower_bound(all(val),i)-val.begin()+1;
    for(;i<=val.size();i+=i&-i){
        if(t) dw[i].insert(j); else dw[i].erase(dw[i].find(j));
    }
}

long long que_u(int i){
    i=lower_bound(all(val),i)-val.begin()+1;
    long long ret=INF;
    for(;i<=val.size();i+=i&-i) if(up[i].size())
        ret=min(ret,*up[i].begin());
    return ret;
}
long long que_d(int i){
    i=lower_bound(all(val),i)-val.begin()+1;
    long long ret=INF;
    for(;i;i-=i&-i) if(dw[i].size())
        ret=min(ret,*dw[i].begin());
    return ret;
}

map<ii,int> mp;
vector<ii> ad[N*3];

int mask(int i,int h){
    if(mp.count({i,h}))
        return mp[{i,h}];
    return mp[{i,h}]=mp.size();
}

void add(int i,int j,int c){
    //cerr<<i<<" "<<j<<" "<<c<<"\n";
    ad[i].pb({j,c});
    ad[j].pb({i,c});
}

long long min_distance(vector<int> x,vector<int> h,vector<int> l,vector<int> r,vector<int> y,int s,int g){

    if(s==0 && g==x.size()-1){
        val=y, val.pb(0), sort(all(val)), val.erase(unique(all(val)),val.end());

        vector<ii> q;
        forinc(i,1,l.size()){
            q.push_back({l[i-1],-i});
            q.push_back({r[i-1],i});
        }
        q.push_back({0,l.size()+1});
        q.push_back({0,-l.size()-1});
        sort(all(q));
        y.emplace_back();
        x.push_back(x[0]);
        l.push_back(0);
        r.push_back(0);

        long long ret=INF;

        forv(i,q){
            if(i.se<0){ i.se=-i.se;
                i.se--;
                f[i.se]=min(x[l[i.se]]+y[i.se]+que_d(y[i.se]),x[l[i.se]]-y[i.se]+que_u(y[i.se]));
                if(i.se==l.size()-1) f[i.se]=0;
                upd_d(y[i.se],f[i.se]-x[l[i.se]]-y[i.se],1);
                upd_u(y[i.se],f[i.se]-x[l[i.se]]+y[i.se],1);
                if(r[i.se]==x.size()-2)
                    ret=min(ret,f[i.se]+x[r[i.se]]-x[l[i.se]]+y[i.se]);
            } else{
                i.se--;
                upd_d(y[i.se],f[i.se]-x[l[i.se]]-y[i.se],0);
                upd_u(y[i.se],f[i.se]-x[l[i.se]]+y[i.se],0);
            }
        }

        return ret==INF ? -1 : ret;
    } else{
        has[s].push_back(0);
        has[g].push_back(0);

        set<int> st;
        vector<ii> el, q;
        int n=x.size();
        forinc(i,1,n){
            st.insert(i-1);
            el.push_back({h[i-1],i-1});
        }
        sort(all(el));

        forinc(i,1,l.size()){
            q.push_back({y[i-1],i-1});
        }

        sort(all(q));
        int it=0;
        forv(i,q){
            while(el[it].fi<i.fi){
                st.erase(el[it++].se);
            }

            auto j=st.lower_bound(l[i.se]);
            int pre=-1;
            for(;;){
                has[*j].push_back(y[i.se]);
                if(pre>=0)
                    add(mask(*j,y[i.se]),mask(pre,y[i.se]),x[*j]-x[pre]);
                pre=*j;
                if(*j==r[i.se]) break;
                j++;
            }
        }

        forinc(i,0,n-1){
            sort(all(has[i]));
            has[i].erase(unique(all(has[i])),has[i].end());
            forinc(j,1,has[i].size()-1){
                add(mask(i,has[i][j-1]),mask(i,has[i][j]),has[i][j]-has[i][j-1]);
            }
        }

        //gg

        using li=pair<long long,int>;
        priority_queue<li,vector<li>,greater<li>> qq;
        int ss=mask(s,0), ed=mask(g,0);
        qq.push({0,ss});
        reset(f,127);
        f[ss]=0;
        while(q.size()){
            long long c=qq.top().fi; int u=qq.top().se; qq.pop();
            if(u==ed) return c;
            forv(v,ad[u]){
                if(f[v.fi]>c+v.se){
                    f[v.fi]=c+v.se;
                    qq.push({c+v.se,v.fi});
                }
            }
        }
        return -1;
    }
}

Compilation message (stderr)

walk.cpp: In function 'void upd_d(int, long long int, int)':
walk.cpp:38:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i){
          ~^~~~~~~~~~~~
walk.cpp: In function 'long long int que_u(int)':
walk.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=val.size();i+=i&-i) if(up[i].size())
          ~^~~~~~~~~~~~
walk.cpp: In function 'long long int min_distance(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, int, int)':
walk.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(s==0 && g==x.size()-1){
                ~^~~~~~~~~~~~
walk.cpp:97:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(i.se==l.size()-1) f[i.se]=0;
                    ~~~~^~~~~~~~~~~~
walk.cpp:100:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if(r[i.se]==x.size()-2)

• Subtask 1: 0 / 10
• Subtask 2: 0 / 14
• Subtask 3: 15 / 15
• Subtask 4: 18 / 18
• Subtask 5: 0 / 43