Submission #296698

#TimeUsernameProblemLanguageResultExecution timeMemory
296698Leonardo16Sky Walking (IOI19_walk)C++14
0 / 100
323 ms55916 KiB
#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; map<int,vi >mp; map<int,int>sk; 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(); ll d=-nxt.fst; int u=nxt.scd; if(d>dist[u])continue; for(auto v:G[u]){ 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) { for(int i=0;i<x.sz();i++){ build b; b.x=x[i]; b.h=h[i]; b.id=i+1; bu[b.x]=b; sk[b.x]=b.h; mp[b.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=x.sz()+1; map<int,ii>prevv; for(auto it:mp){ sort(rall(mp[it.fst])); } for(auto it:mp){ // 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}); }else{ G[wr-1].pb({wr,mi-prev}); G[wr].pb({wr-1,mi-prev}); } 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}); } 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:91:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i=0;i<x.sz();i++){
      |              ~^~~~~~~
walk.cpp:101:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i=0;i<l.sz();i++){
      |              ~^~~~~~~
walk.cpp:102:14: warning: variable 'w' set but not used [-Wunused-but-set-variable]
  102 |         walk w;
      |              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...