Submission #974687

#	Time	Username	Problem	Language	Result	Execution time	Memory
974687		NemanjaSo2005	Sky Walking (IOI19_walk)	C++17	0 / 100	690 ms	112304 KiB

walk

#include "walk.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+5;
const int mostint=11;
int N,M;
struct skywalk{
   int l,r,y;
} put[maxn];
struct zgrada{
   int x,y,id;
} niz[maxn];
bool cmpsw(skywalk a,skywalk b){
   return a.y<b.y;
}
bool poy(zgrada a,zgrada b){
   return a.y<b.y;
}
bool pox(zgrada a,zgrada b){
   return a.x<b.x;
}
set<int> S;
vector<pair<int,ll>> graf[12*maxn];
vector<int> presek[maxn];
bool prosli[12*maxn];
ll dist[12*maxn];
priority_queue<pair<ll,int>> PQ;
void Dijkstra(int gde,ll c){
   PQ.push({-c,gde});
   while(PQ.size()){
      int tren=PQ.top().second;
      ll d=-PQ.top().first;
      PQ.pop();
      if(prosli[tren])
         continue;
      prosli[tren]=true;
      dist[tren]=d;
      for(auto x:graf[tren])
         PQ.push({-d-x.second,x.first});
   }
}
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) {
   s++;
   g++;

	N=x.size();
	M=l.size();
	for(int i=1;i<=N;i++){
      niz[i].x=x[i-1];
      niz[i].y=h[i-1];
      niz[i].id=i;
	}
	for(int i=1;i<=M;i++){
      put[i].l=l[i-1]+1;
      put[i].r=r[i-1]+1;
      put[i].y=y[i-1];
	}
	sort(niz+1,niz+1+N,poy);
	sort(put+1,put+1+M,cmpsw);
	int pok=N;
	niz[0].y=0;
	for(int i=M;i>=1;i--){
      while(niz[pok].y>=put[i].y){
         S.insert(niz[pok].id);
         pok--;
      }
      vector<int> V;
      auto it=S.upper_bound(put[i].l-1);
      for(it;it!=S.end();it++){
         if((*it)>put[i].r)
            break;
         V.push_back(*it);
         presek[*it].push_back(i);
      }

  /*    cout<<"PUT "<<put[i].l<<" "<<put[i].r<<" "<<put[i].y<<" SECE"<<endl;
      for(int x:V)
         cout<<x<<" ";
      cout<<endl;
*/

      for(int j=1;j<V.size();j++){
         int pr=V[j-1];
         int tr=V[j];
         ll d=x[tr-1]-x[pr-1];
        // cout<<d<<" ";
         pr=(pr-1)*mostint+presek[pr].size();
         tr=(tr-1)*mostint+presek[tr].size();
         graf[pr].push_back({tr,d});
         graf[tr].push_back({pr,d});
      }
     // cout<<endl;
	}
	for(int i=1;i<=N;i++){
      for(int j=1;j<presek[i].size();j++){
         ll d=put[presek[i][j-1]].y-put[presek[i][j]].y;
         int a=(i-1)*mostint+j;
         int b=(i-1)*mostint+j+1;
         graf[a].push_back({b,d});
         graf[b].push_back({a,d});
      }
	}

	/*for(int i=1;i<=mostint*N;i++){
      cout<<i<<": ";
      for(auto x:graf[i])
         cout<<x.first<<" "<<x.second<<"  ";
      cout<<endl;
	}*/


	Dijkstra(presek[s].size()+(s-1)*mostint,put[presek[s].back()].y);
	ll res=1e18;
	for(int i=0;i<presek[g].size();i++){
      ll d=dist[(g-1)*mostint+i+1];
      d+=put[presek[g][i]].y;
      res=min(res,d);
	}
	return res;
}
/*
7 7
0 8
3 7
5 9
7 7
10 6
12 6
14 9
0 1 1
0 2 6
0 6 8
2 3 1
2 6 7
3 4 2
4 6 5
1 5
*/

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:70:11: warning: statement has no effect [-Wunused-value]
   70 |       for(it;it!=S.end();it++){
      |           ^~
walk.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |       for(int j=1;j<V.size();j++){
      |                   ~^~~~~~~~~
walk.cpp:96:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |       for(int j=1;j<presek[i].size();j++){
      |                   ~^~~~~~~~~~~~~~~~~
walk.cpp:115:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for(int i=0;i<presek[g].size();i++){
      |              ~^~~~~~~~~~~~~~~~~

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