Submission #1067530

#TimeUsernameProblemLanguageResultExecution timeMemory
1067530jamjanekSky Walking (IOI19_walk)C++17
33 / 100
4083 ms111936 KiB
#include "walk.h" #include<bits/stdc++.h> using namespace std; vector<int>l,r,y,x,h; const int base = 1<<17; int drzewo[2*base]; int wiekszeL(int x, int val){ x+=base; while(drzewo[x]<val && x&(x-11)){ if(x%2==1)x/=2; else x--; } if(drzewo[x]>=val){ while(x<base) if(drzewo[x*2+1]>=val) x=x*+1; else x=x*2; return x-base; } else return -1; } int wiekszeR(int x, int val){ while(x<(int)h.size()){ if(h[x]>=val)break; x++; } return x; } int tree[2*base]; void ustaw(int w, int l, int p, int a, int b, int v){ if(a<=l && p<=b){ tree[w] = v; return; } if(b<l || p<a)return; if(tree[w]!=-1) tree[w*2] = tree[w*2+1] = tree[w]; ustaw(w*2, l, (l+p)/2, a, b, v); ustaw(w*2+1, (l+p)/2+1, p, a, b, v); tree[w] = -1; } int odczyt(int w){ int res = -1; w+=base; while(w>0){ if(tree[w]!=-1) res = tree[w]; w/=2; } return res; } void dodaj(int a, int b, int h){ l.push_back(a); r.push_back(b); y.push_back(h); } vector<pair<int,long long>>graf[700010]; long long dist[700010]; bool odw[700010]; map<pair<int,int>,int>mapa; long long odl(pair<int,int>a, pair<int,int>b){ return abs(a.second-b.second); } long long odl1(pair<int,int>a, pair<int,int>b){ return abs(x[a.first]-x[b.first]); } map<int,vector<pair<int,int>>>poziomy; long long min_distance(vector<int> X, vector<int> H, vector<int> L, vector<int> R, vector<int> Y, int s, int g) { x = X; h = H; // podzielic kazda pozioma // dla kazdej poziomej wyznaczyc pozioma w dol z obu koncy vector<tuple<int,int,int,int>>przedzialy; int n = x.size(); int m = L.size(); int i; for(i=0;i<n;i++) drzewo[i+base]=h[i]; for(i=base-1;i>0;i--) drzewo[i]=max(drzewo[i*2], drzewo[i*2+1]); if(s>g)swap(s,g); for(i=0;i<m;i++){ poziomy[Y[i]].push_back({L[i],R[i]}); if(L[i]<s && R[i]>g){ // printf("%d 3\n", i); dodaj(L[i],s,Y[i]); dodaj(s,g,Y[i]); dodaj(g,R[i],Y[i]); } else if(L[i]<s && R[i]>s){ // printf("%d 2\n", i); dodaj(L[i],s,Y[i]); dodaj(s,R[i],Y[i]); } else if(g<R[i] && L[i]<g){ // printf("%d 2\n", i); dodaj(L[i],g,Y[i]); dodaj(g,R[i],Y[i]); } else{ // printf("%d 1\n"); dodaj(L[i],R[i],Y[i]); } } m = l.size(); //for(i=0;i<m;i++)printf("%d %d %d %d\n", y[i], l[i], r[i], i);printf("\n"); for(i=0;i<m;i++) przedzialy.push_back({y[i],l[i],r[i],0}); sort(przedzialy.begin(), przedzialy.end()); for(i=0;i<m;i++) get<3>(przedzialy[i]) = i; for(i=0;i<n;i++)tree[i+base] = -1; for(i=base-1;i>0;i--) tree[i] = -1; ustaw(1, 0,base-1,s,s,0); ustaw(1, 0,base-1,g,g,0); mapa[{s,0}]=0; mapa[{g,0}]=1; for(auto j: przedzialy){ auto [Y,L,R,i] = j; int a = wiekszeR(L, Y); if(a<=R){ int b = odczyt(a); if(b!=-1 && mapa.find({a, b})==mapa.end()) mapa[{a,b}] = mapa.size(); if(mapa.find({a, Y})==mapa.end()) mapa[{a,Y}] = mapa.size(); } a = wiekszeL(R,Y); if(a>=L){ int b = odczyt(a); if(b!=-1 &&mapa.find({a, b})==mapa.end()) mapa[{a,b}] = mapa.size(); if(mapa.find({a, Y})==mapa.end()) mapa[{a,Y}] = mapa.size(); } ustaw(1, 0, base-1, L, R, Y); /* for(int ij=0;ij<2;ij++){ int a = odczyt(ij?R:L); int s = (a-2)/2; b = i*2+2+ij; // if(ij==0)printf("LEWY: %d %d(%d)\n", b, a,s); // else printf("PRAWY: %d %d(%d)\n", b, a,s); if(a==-1)continue; if(a==0 || a==1){ graf[b].push_back({a,Y}); graf[a].push_back({b,Y}); } else{ long long d; d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<1>(przedzialy[s])]); graf[b].push_back({a, d}); graf[a].push_back({b, d}); d=Y-get<0>(przedzialy[s])+abs(x[ij?R:L]-x[get<2>(przedzialy[s])]); graf[b].push_back({a^1, d}); graf[a^1].push_back({b, d}); } } graf[b].push_back({b-1, abs(x[L]-x[R])}); graf[b-1].push_back({b, abs(x[L]-x[R])}); ustaw(1, 0, base-1, L, R, b-1);*/ // printf("%d %d %d: %d %d\n", y[i], l[i], r[i], b-1, b); }/* for(i=0;i<(int)przedzialy.size()*2+2;i++){ printf("%d: ", i); for(auto j: graf[i]) printf("%d-%d ", j.first, j.second); printf("\n"); }*/ vector<pair<pair<int,int>,int>>wartosci; for(auto j=mapa.begin();j!=mapa.end();j++){ auto xd = *j; wartosci.push_back({xd.first, xd.second}); auto next = j; next++; if(next==mapa.end())break; if((*next).first.first==(*j).first.first){ graf[(*next).second].push_back({(*j).second, odl((*j).first, (*next).first)}); graf[(*j).second].push_back({(*next).second, odl((*j).first, (*next).first)}); } } for(auto &j: poziomy){ auto &vec = j.second; vector<pair<int,int>>dobre; sort(vec.begin(), vec.end()); int koniec = (*vec.begin()).second, pocz = (*vec.begin()).first; for(auto k: vec){ if(k.first<=koniec) koniec = max(k.second, koniec); else{ // printf("%d %d\n", pocz, koniec); dobre.push_back({pocz, koniec}); pocz = k.first; koniec = k.second; } } dobre.push_back({pocz,koniec}); // for(auto ij: vec)printf("%d %d, ", ij.first, ij.second);printf("dsad\n"); vec = dobre; // for(auto ij: dobre)printf("%d %d, ", ij.first, ij.second);printf("\n"); } mapa.clear(); for(auto j:wartosci) mapa[{j.first.second,j.first.first}]=j.second; for(auto j=mapa.begin();j!=mapa.end();j++){ if((*j).first.first==0)continue; auto next = j; next++; if(next==mapa.end())break; if((*next).first.first==(*j).first.first){ int a =(*j).first.second, b = (*next).first.second; auto &pom = poziomy[(*j).first.first]; if(upper_bound(pom.begin(), pom.end(), make_pair(a,1000000000))==upper_bound(pom.begin(), pom.end(), make_pair(b,1000000000))){ graf[(*next).second].push_back({(*j).second, x[(*next).first.second]-x[(*j).first.second]}); graf[(*j).second].push_back({(*next).second, x[(*next).first.second]-x[(*j).first.second]}); } } }/* for(auto j: wartosci)printf("%d %d %d\n", j.second, j.first.first, j.first.second); for(i=0;i<10;i++){ printf("%d: ", i); for(auto j: graf[i])printf("%d-%d ", j.first,j.second);printf("\n"); }*/ priority_queue<pair<long long, int>>kolejka; dist[0] = 1; kolejka.push({-1,0}); while(kolejka.size()){ auto a = kolejka.top(); //printf("%lld %d %d\n", -a.first, a.second); kolejka.pop(); if(odw[a.second])continue; odw[a.second]=1; for(auto j: graf[a.second]){ if(dist[j.first]==0 || dist[j.first]>dist[a.second]+j.second){ dist[j.first]=dist[a.second]+j.second; kolejka.push({-dist[j.first], j.first}); } } } return dist[1]-1; }
#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...