Submission #258702

#	Time	Username	Problem	Language	Result	Execution time	Memory
258702		TadijaSebez	Sky Walking (IOI19_walk)	C++14	100 / 100	2121 ms	122556 KiB

walk

#include "walk.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define pb push_back
const int N=100050;
const int L=17;
const ll inf=9e18;
int rmq[N][L],lgs[N],n,m;
void BuildST(vi h){
	for(int i=0;i<n;i++)rmq[i][0]=h[i];
	for(int j=1;j<L;j++){
		for(int i=0;i<n-(1<<j)+1;i++){
			rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
		}
	}
	for(int i=2;i<=n;i++)lgs[i]=lgs[i>>1]+1;
}
int Get(int l,int r){
	int k=lgs[r-l+1];
	return max(rmq[l][k],rmq[r-(1<<k)+1][k]);
}
int GetL(int x,int y){
	int top=x,bot=0,mid,ans;
	while(top>=bot){
		mid=top+bot>>1;
		if(Get(mid,x)>=y)ans=mid,bot=mid+1;
		else top=mid-1;
	}
	return ans;
}
int GetR(int x,int y){
	int bot=x,top=n-1,mid,ans;
	while(top>=bot){
		mid=top+bot>>1;
		if(Get(x,mid)>=y)ans=mid,top=mid-1;
		else bot=mid+1;
	}
	return ans;
}
int tot;
map<int,int> idx[N];
void Add(int x,int y){
	if(!idx[x][y])
		idx[x][y]=++tot;
}
vector<pii> E[N*12];
ll dist[N*12];
void AddEdge(int u,int v,int w){
	E[u].pb({v,w});
	E[v].pb({u,w});
}
ll min_distance(vi x,vi h,vi l,vi r,vi y,int s,int g){
	n=x.size();
	m=l.size();
	BuildST(h);
	Add(s,0);
	Add(g,0);
	vector<pii> evs;
	for(int i=0;i<m;i++){
		Add(l[i],y[i]);
		Add(r[i],y[i]);
		if(l[i]<s&&r[i]>s){
			Add(GetL(s,y[i]),y[i]);
			Add(GetR(s,y[i]),y[i]);
		}
		if(l[i]<g&&r[i]>g){
			Add(GetL(g,y[i]),y[i]);
			Add(GetR(g,y[i]),y[i]);
		}
		evs.pb({l[i],y[i]});
		evs.pb({r[i]+1,-y[i]});
	}
	sort(evs.begin(),evs.end());
	map<int,int> bal;
	for(int i=0,j=0;i<n;i++){
		while(j<evs.size()&&evs[j].first==i){
			int y=evs[j].second;
			bal[abs(y)]+=y/abs(y);
			if(!bal[abs(y)])bal.erase(abs(y));
			j++;
		}
		for(auto it=idx[i].begin();it!=idx[i].end();it++){
			auto jt=bal.lower_bound(it->first);
			if(jt!=bal.begin()){
				jt--;
				Add(i,jt->first);
				AddEdge(it->second,idx[i][jt->first],it->first-jt->first);
			}else if(i==s||i==g){
				AddEdge(it->second,idx[i][0],it->first);
			}
		}
	}
	evs.clear();bal.clear();
	for(int i=0;i<m;i++){
		evs.pb({l[i],y[i]});
		evs.pb({r[i],-y[i]});
	}
	sort(evs.begin(),evs.end());
	map<int,pii> las;
	for(int i=0,j=0;i<n;i++){
		for(auto it=idx[i].begin();it!=idx[i].end();it++){
			if(las[it->first].first){
				AddEdge(it->second,las[it->first].first,x[i]-las[it->first].second);
			}
		}
		set<int> pos;
		while(j<evs.size()&&evs[j].first==i){
			int y=evs[j].second;
			bal[abs(y)]+=y/abs(y);
			if(!bal[abs(y)])bal.erase(abs(y));
			pos.insert(abs(y));
			j++;
		}
		for(int y:pos){
			if(bal.find(y)==bal.end())las[y]={0,0};
		}
		for(auto it=idx[i].begin();it!=idx[i].end();it++){
			if(bal.find(it->first)!=bal.end())
				las[it->first]={it->second,x[i]};
		}
	}
	priority_queue<pair<ll,int>> pq;
	for(int i=1;i<=tot;i++)dist[i]=inf;
	dist[idx[s][0]]=0;
	pq.push({0,idx[s][0]});
	while(pq.size()){
		int u=pq.top().second;
		ll d=-pq.top().first;
		pq.pop();
		if(dist[u]!=d)continue;
		for(auto e:E[u]){
			int v,w;tie(v,w)=e;
			if(dist[v]>dist[u]+w){
				dist[v]=dist[u]+w;
				pq.push({-dist[v],v});
			}
		}
	}
	return dist[idx[g][0]]==inf?-1:dist[idx[g][0]];
}

Compilation message (stderr)

walk.cpp: In function 'void BuildST(std::vector<int>)':
walk.cpp:16:41: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
    rmq[i][j]=max(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
                                        ~^~
walk.cpp: In function 'int GetL(int, int)':
walk.cpp:28:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
walk.cpp: In function 'int GetR(int, int)':
walk.cpp:37:10: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   mid=top+bot>>1;
       ~~~^~~~
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:79:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<evs.size()&&evs[j].first==i){
         ~^~~~~~~~~~~
walk.cpp:110:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(j<evs.size()&&evs[j].first==i){
         ~^~~~~~~~~~~
walk.cpp: In function 'int GetL(int, int)':
walk.cpp:32:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ans;
         ^~~
walk.cpp: In function 'int GetR(int, int)':
walk.cpp:41:9: warning: 'ans' may be used uninitialized in this function [-Wmaybe-uninitialized]
  return ans;
         ^~~

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