Submission #296691

#	Time	Username	Problem	Language	Result	Execution time	Memory
296691		Leonardo16	Sky Walking (IOI19_walk)	C++14	0 / 100	331 ms	51272 KiB

walk

#include<bits/stdc++.h>
#include "walk.h"
using namespace std;
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
//#pragma GCC option("arch=native","tune=native","no-zero-upper")
//#pragma GCC target("avx2")
//#define int  long long
#define ll long long
#define sz size
#define ull unsigned long long
#define ld long double
#define ii pair<int,int>
#define fst first
#define scd second
#define vi vector<int>
#define vii vector<ii>
#define pb push_back
#define pf push_front
#define fl '\n'
#define el endl
#define all(x) x.begin() , x.end()
#define rall(x) x.rbegin() , x.rend()
/// Functions
#define db(x) cerr << #x << ": " << (x) << '\n';
#define random() __builtin_ia32_rdtsc()
#define lg2(x) 31-__builtin_clz(x)
#define lg2ll(x) 63-__builtin_clzll(x)
#define pi acos(-1)
#define YN(x) cout<<((x)?("YES"):("NO"))<<fl;
#define yn(x) cout<<((x)?("Yes"):("No"))<<fl;
#define des(x,s1,s2,end1,end2) cout<<((x)?(s1):(s2))<<fl;if(x){end1;}else{end2;}
#define precision(x) cout.setf(ios::fixed);cout.precision(x);
/// Red-Black Tree Template
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree < long long ,  null_type ,  less<long long> ,  rb_tree_tag ,  tree_order_statistics_node_update > ordered_set;
//#define less_than(n) order_of_key(n)
//#define en_pos(n) find_by_order(n)
/// Prime numbers  173,179,311,331,737,1009,2011,2027,3079,4001,100003
///=====================================================================
vii G[200005];
struct build{
    int x,h;
    bool operator<(const build &b){
        return x<b.x;
    }
    int id,id1;
    vector<int>cuts;

};

struct walk{
    int y,l,r;
};

map<int,build>bu;

ll dist[200005];

void dijkstra(int s){

    for(int i=0;i<200005;i++){
        dist[i]=1e18;
    }
    dist[s]=0;

    priority_queue< pair<ll,int> >q;
    q.push({0,s});

    while(!q.empty()){
        pair<ll,int> nxt=q.top();q.pop();
        int d=-nxt.fst;
        int u=nxt.scd;
        if(d>dist[u])continue;
//        cout<<u<<" "<<d<<fl;
        for(auto v:G[u]){
//            cout<<u<<"-> "<<v.fst<<fl;
            if(d+v.scd<dist[v.fst]){
                dist[v.fst]=d+v.scd;
                q.push({-dist[v.fst],v.fst});
            }
        }
    }
}


ll min_distance(vi x, vi h, vi l, vi r, vi y, int s, int g) {
	vector<build>v;
	for(int i=0;i<x.sz();i++){
        build b;
        b.x=x[i];
        b.h=h[i];
        b.id=i+1;
        v.pb(b);
        bu[b.x]=b;
	}

	sort(all(v));
	map<int,vi >mp;
	map<int,int>sk;

	for(int i=0;i<v.sz();i++){
        sk[v[i].x]=v[i].h;
        mp[v[i].x].clear();
	}

	for(int i=0;i<l.sz();i++){
        walk w;
        w.l=l[i];
        w.r=r[i];
        w.y=y[i];
        mp[l[i]].pb(y[i]);
        mp[r[i]+1].pb(-y[i]);
	}

	map<int,int >m2;
	int wr=v.sz()+1;

	map<int,ii>prevv;

	for(auto it:mp){
        sort(rall(mp[it.fst]));
//        cout<<"----------> "<<it.fst<<fl;

        for(auto i2:it.scd){
//            cout<<"+"<<i2<<fl;
            if(i2>0){
                m2[i2]++;
            }else{
                if(m2[abs(i2)]==0){prevv[abs(i2)].fst=0;m2.erase(abs(i2));}
            }
        }

        if(sk[it.fst]!=0){
            int prev=0;
            vi tp;

            while(m2.sz()){
                int mi=(*m2.begin()).fst;
                m2.erase(mi);
                tp.pb(mi);

                if(mi<=sk[it.fst]){
//                    cout<<"-->"<<it.fst<<" "<<mi<<fl;

                    build b=bu[it.fst];

                    if(prev==0){
                        G[b.id].pb({wr,mi});
                        G[wr].pb({b.id,mi});

//                        cout<<"--->> "<<it.fst<<" "<<mi<<" "<<b.id<<" "<<wr<<fl;
                    }else{
                        G[wr-1].pb({wr,mi-prev});
                        G[wr].pb({wr-1,mi-prev});
//                        cout<<"--->> "<<it.fst<<" "<<mi<<" "<<wr-1<<" "<<wr<<fl;
                    }
                    if(prevv[mi].fst!=0){

                        G[wr].pb({prevv[mi].fst,it.fst-prevv[mi].scd});
                        G[prevv[mi].fst].pb({wr,it.fst-prevv[mi].scd});

//                        cout<<" --- "<<wr<<" "<<prevv[mi].fst<<" : "<<it.fst-prevv[mi].scd<<fl;
                    }
                    prevv[mi]={wr,it.fst};

                    prev=mi;
                    wr++;

                }else{
                    break;
                }
            }


            for(auto i3:tp){
                m2[i3];
            }
        }
        vector<int>v;

	}

    dijkstra(s+1);

//    for(int i=1;i<=wr;i++){
//        cout<<dist[i]<<fl;
//    }
    if(dist[g+1]==1e18)return -1;
    return dist[g+1];

}

Compilation message (stderr)

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:90:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |  for(int i=0;i<x.sz();i++){
      |              ~^~~~~~~
walk.cpp:103:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<build>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |  for(int i=0;i<v.sz();i++){
      |              ~^~~~~~~
walk.cpp:108:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |  for(int i=0;i<l.sz();i++){
      |              ~^~~~~~~
walk.cpp:109:14: warning: variable 'w' set but not used [-Wunused-but-set-variable]
  109 |         walk w;
      |              ^

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