Submission #974721

#	Time	Username	Problem	Language	Result	Execution time	Memory
974721		NemanjaSo2005	Sky Walking (IOI19_walk)	C++17	15 / 100	140 ms	17656 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
int N,M;
map<int,ll> mapa;
vector<int> poc[maxn],kraj[maxn];
ll getdist(int y,int h){
   auto it=mapa.upper_bound(y-1);
   if(it!=mapa.begin())
      it--;
   if(it!=mapa.begin())
      it--;
   if(it!=mapa.begin())
      it--;
   if(it!=mapa.begin())
      it--;
   ll ans=9e18;
   int br=10;
   for(it;it!=mapa.end();it++){
      br--;
      if(br==0)
         break;
      if((it->first)>h)
         break;
      ans=min(ans,(it->second)+abs(y-(it->first)));
   }
   if(ans==9e18)
      return -1;
   return ans;
}
ll min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g) {
   N=x.size();
	M=l.size();
	for(int i=0;i<M;i++){
      poc[l[i]].push_back(y[i]);
      kraj[r[i]].push_back(y[i]);
	}
	for(int x:poc[0])
      mapa[x]=x;
   for(int i=1;i<N-1;i++){
      if(mapa.size()==0)
         return -1;
      vector<pair<int,ll>> V;
      for(int y:poc[i]){
         ll d=getdist(y,h[i]);
         if(d==-1)
            break;
         V.push_back({y,d});
      }
      for(int x:kraj[i])
         mapa.erase(x);
      for(auto x:V)
         mapa[x.first]=x.second;
   }
   if(mapa.size()==0)
      return -1;
   ll res=9e18;
   for(auto it=mapa.begin();it!=mapa.end();it++)
      res=min(res,(it->first)+(it->second));
	return res+x.back()-x[0];
}

Compilation message (stderr)

walk.cpp: In function 'long long int getdist(int, int)':
walk.cpp:21:8: warning: statement has no effect [-Wunused-value]
   21 |    for(it;it!=mapa.end();it++){
      |        ^~

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